PHP – Finding If a Number Is a Power of 2

You need refresh yourself on how binary works. 5 is not represented as 0001 1111 (5 bits on), it's represented as 0000 0101 (2^2 + 2^0), and 4 is likewise not 0000 1111 (4 bits on) but rather 0000 0100 (2^2). The numbers you wrote are actually in unary.

Wikipedia, as usual, has a pretty thorough overview.

You can test if a positive integer n is a power of 2 with something like

(n & (n - 1)) == 0

If n can be non-positive (i.e. negative or zero) you should use

(n > 0) && ((n & (n - 1)) == 0)

If n is truly a power of 2, then in binary it will look like:

10000000...

so n - 1 looks like

01111111...

and when we bitwise-AND them:

  10000000...
& 01111111...
  -----------
  00000000...

Now, if n isn't a power of 2, then its binary representation will have some other 1s in addition to the leading 1, which means that both n and n - 1 will have the same leading 1 bit (since subtracting 1 cannot possibly turn off this bit if there is another 1 in the binary representation somewhere). Hence the & operation cannot produce 0 if n is not a power of 2, since &ing the two leading bits of n and n - 1 will produce 1 in and of itself. This of course assumes that n is positive.

This is also explained in "Fast algorithm to check if a positive number is a power of two" on Wikipedia.

Quick sanity check:

for (int i = 1; i <= 100; i++) {
    if ((i & (i - 1)) == 0)
        System.out.println(i);
}

1
2
4
8
16
32
64