Tutorials - Power of Two Challenge Solution

Solution to Power of Two Challenge

A power of two will look like this in memory:

01000000

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:

01000001

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.