Sunday, October 3, 2010

Given a number is power of 2?

Write 1 line code to find whether a number is a power of 2 or not?

Approach:
To clear the rightmost bit of a number the below utility can be used
n = n & (n-1) (Since n-1 turns off the right most bit and turns on all the bit lower than the rightmost bit)

Now to find the number is power of 2 or not is trivial
if n & (n-1) == 0
but there is a catch for the number of 0 :)
so a simple one liner code will be
return n && !(n & (n - 1));

1. for(i=0,c=0;n >> i;i++)c+=(n>>i)&1;

//if c = 1, the no. is a power of 2.

2. @jainendra ... no loops also ... O(1) solution

3. This comment has been removed by the author.

4. if(((n-1)|n)==n*2-1)printf("power of 2");

5. if(n&(-n) == n)
then power of 2
else not.

6. return (n & (n-1) == 0);

it is "O(1)" even though theoretically this takes O(log n), because any of these operations (bitwise and, equality, etc) take at most (number of bits of n) steps.

7. @jainendra, banka, imavalon .... correct !!!