Code.Fu: Quickly testing if a positive integer is a power of 2.

If you are a graphics programmer you will often need to test if an integer is a power of 2. To do this you can exploit a neat trick using binary arithmetic. This trick will work with all positive integers.

Lets say the number you are testing is 4. Take a look at the simple binary arithmetic below:


  4 --> 0100‬ (binary)
- 1 --> 0001
------------------
  3 --> 0011

  4 --> 0100
& 3 --> 0011
------------------
  0 --> 0000

In short, you subtract 1 from the number and do a binary ‘AND’ of the result and the original number. If the number is a power of two, the result you get will always be 0.  The only exception is 0 itself, which will return 0 in the above operation. Depending on your application you may or may not want that.

C/C++:

#define bool int /*remove this line for C++*/

bool is_powof_2(int x)
{ 
  return ((x & (x-1)) == 0);
}

bool is_powof_2_excl_0(int x)
{ 
  return (x != 0) && ((x & (x-1)) == 0);
}

Python:

def is_powof_2(x):
	return ((x & (x-1)) == 0)

def is_powof_2_excl_0(x):
	return (x != 0) and ((x & (x-1)) == 0)

Leave a Reply