Power of 2 or not ?

How to find a number is power of 2 or not ?

bool IsPowerOfTwo(unsigned long x)
{
    return (x != 0) && (x & (x - 1)) == 0);
}

Explanation:

The above function returns bool (true/false) and accepts one incoming parameter of type unsigned long (x, in this case). Lets take an example, that someone has passed value 4 to the function like:

bool b = IsPowerOfTwo(4);

Now replace each occurance of x with 4:

return (4 != 0) && ((4 & (4-1)) == 0); 


We already know (4 != 0) , so the evaluation of the expression is true.


((4 & (4-1)) == 0)  translates to:


((4 & (3)) == 0) 


But what exactly is  4&3 ? The binary representation of 4 is 100 and of 3 is 011. The & operation says that if both values are equal to 1, then the result is 1. Otherwise it is 0.

100
011
----
000

The result is simply 0. So we go back and look at what our return statement now translates to:

return (4 != 0) && ((4 & 3) == 0);

Which translates now to:

return true && (0 == 0);

return true && true;

We all know that true && true is simply true, and this shows that for our example, 4 is a power of 2.