### 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.

## No comments:

## Post a Comment