Search code examples
algorithmmathbinarybit-manipulation

Check whether a number can be expressed as sum of x powers of two

Is there a bit trick to check whether a number can be expressed as sum of x powers of 2?

Example: For x=3 n=21, the numbers are 16, 4, and 1. If n=30, it should be false, because there are no 3 powers of two to represent 30.

Solution

  • For a number n …

    • … the minimum x is the number of 1-bits in n. This number is called popcount(n).
      Example: The binary number 0b1011 needs at least popcount(0b1011)=3 powers of two to be summed up (0b1000+0b0010+0b0001).
    • … the maximum x is n. Because 1 is a power of two you can add 1 n times to get n.

    Now comes the hard question. What if x is between popcount(n) and n?
    As it turns out, all of these x are possible. To build a sum of x powers of two …

    • start at the shortest sum (the binary representation of n)
    • If you have less than x addends, split any addend that is bigger than 1 into two addends, increasing the number of addends by one. This can be done until you arrive at x=n.

    Example: Can 11=0b1011 be expressed as a sum of x=7 powers of two?

    Yes, because popcount(n)=3 <= x=7 <= n=11.

    To build a sum with x=7 powers of two we use
    11 = 0b1011 = 0b1000+0b10+0b1 | only 3 addends, so split one
    = (0b100+0b100)+0b10+0b1 | only 4 addends, so split another one
    = ((0b10+0b10)+0b100)+0b10+0b1 | only 5 addends, so split another one
    = (((0b1+0b1)+0b10)+0b100)+0b10+0b1 | only 6 addends, so split another one
    = (((0b1+0b1)+(0b1+0b1))+0b100)+0b10+0b1 | 7 addends, done

    Implementation

    To implement the check »can n can be expressed as sum of x powers of two?« use

    isSumOfXPowersOfTwo(n, x) {
   return x<=n && x>=popcount(n).
}

    For efficient bit-twiddling implementations of popcount see this question. Some processors even have an instruction for that.