0

is there any bit trick to check wheather a number can be expressed as sum of x powers of 2? example: x=3 n=21 the numbers are 16,4,1 if n=30 it should be false because there are no 3 powers of two to repreasent 30

Abdelrahman Yousf
  • 15
  • 1
  • 4
  • 2
    If all the powers of 2 must be different, then n is a sum of x powers of 2 iff there are x set bits in the binary expansion of n. – dmuir Jul 02 '21 at 17:25
  • what if they don't have to be different ? – Abdelrahman Yousf Jul 02 '21 at 18:46
  • 3
    Your question appears to be about maths rather than programming; you might get better answers at a maths site rather than a programming one. I think my comment could be taken further: if there are more than x set bits in the binary expansion or n, then n cannot be expressed as a sum of x powers or 2, even if they are allowed to be the same. On the other hand, if for example n = 9 = 2^3 + 2^0 (two set bits) we could write this as 2^2 + 2^2 + 2^0 as required. Good luck. – dmuir Jul 02 '21 at 19:05
  • thanks that really helped after some experiments i found that the least x should be the number of set bits if there are less than that it cannot be and the max x should the number of bits wheather it's set or unset because you always can add 2^0 as much as you want – Abdelrahman Yousf Jul 02 '21 at 19:57

1 Answers1

2

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.

Socowi
  • 22,529
  • 3
  • 25
  • 46