Tutorials - Power of Two Challenge Solution

Solution to Power of Two Challenge

A power of two will look like this in memory:
a string of zeros, with a lone one. Now, if you subtract 1 from a power of two, you'll get, with all numbers in binary:
01000000 - 00000001 = 00111111
a string of ones!

If you take the bitwise AND of the two values, you get 0.

In binary:
01000000 & 00111111 = 00000000
On the other hand, if you don't have a power of two, you'll have at least one additional 1:
When you subtract 1, you'll still have at least one "on" bit (with a value of 1) in the same position as before, so taking the bitwise AND of the two numbers will not result in a string of 0s:
01000001 - 00000001 = 01000000
01000000 & 01000001 = 01000000
So to tell if an integer is a power of two:
int is_power(int x)
    return !((x-1) & x);
Note that we have to use the logical NOT, !, instead of the bitwise complement since the bitwise complement will not negate non-zero values; it just flips bits.