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));

7 comments :

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

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

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

    ReplyDelete
  3. This comment has been removed by the author.

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

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

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

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

    ReplyDelete