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.

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.