Power of 2 - Bit Operations

A smart way to determine if a number is a power of 2 using bit operations[1] :

If x is a power of 2, then the binary representation of x looks like :

10000000

Consequently,

x - 1 = 10000000 - 00000001 = 01111111

If we take the bitwise AND of x and x-1, we get 0.

x & (x - 1) = 10000000 & 01111111 = 00000000

On the other hand, if x is not a power of 2, the change in the bits caused by subtracting 1 will only propagate as far as the least significant bit which is set to 1 i.e. the first 1 from the right. Bits to the left to this bit will not be affected. As a result, the most significant bit which is set to 1 i.e the first 1 from the left remains unchanged in x - 1. So, x & (x-1) will not be equal to zero because they have at least one common bit set to 1.

 Here's an example:

x = 10000100

x-1 = 10000100 - 00000001 = 10000011

x & (x - 1) = 10000100 & 10000011 = 10000000

Note that 0 is incorrectly detected as a power of 2 by this algorithm. As a result, one must first check whether x is non-zero.

The following code snippet implements the algorithm :

	bool is_power_of_two(int n){
	return x && !(x & (x - 1));
	}

view raw power_of_two.cpp hosted with ❤ by GitHub

[1] - http://www.cprogramming.com/tutorial/powtwosol.html