Coding Away

Sometimes it is useful to find out if a particular integer represents a power of two. You can find that out with a simple trick.

A power of two in binary is represented by a all zeros, except for a single one. For example 00010000 is a power of two (2^4).
In fact you can calculate the n-th power of 2 with:

int power2(int n)
{
     return (1<

If you subtract one from a power of two, you obtain a number which binary representation is a sequence of ones. Example in binary:

00010000 - 1 = 00001111

If you take this number and perform a logical AND with the original power of two you obtain a flat zero!
Example:

00010000 &
00001111
———
00000000

If you have any other number that is not a power of two, this doesn’t work anymore and you’d never obtain a zero.
For example let’s take 18, which is not a power of two.

18 in binary is 00010010
00010010 - 1 = 00010001

00010010 &
00010001 =
———
00010000

Another example. Let’s take 14 which is another number that is not a power of two:

14 in binary is 00001110
00001110 - 1 = 00001101

00001101 &
00001110 =
———
00001100

In general you’ll find that the result of (X-1)&X always contains at least a one… unless X is a power of two! Cool!

For this simple reason you can find out if an integer is a power of two with something like:

boolean isPowerOf2(int x)
{
    return ((x-1) & x)==0;
}

Enjoy!

This entry was posted on Saturday, January 27th, 2007 at 2:21 am and is filed under Programming, Algorithms, Level: Easy. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.