Saturday, December 5, 2009

Code to check if an integer is a power of 2 or not in a single line

Problem
Check if integer is power of 2 or not
FOLLOW UP - Preferable solution to get it in 1 line.

Solution

Method1
All power of two numbers have only one bit set. So count the no. of set bits and if you get 1 then number is a power of 2. We have discussed how to count number of bits set here.

Method 2
Note that the bit pattern of a power of two is of the form 10...0 and that of a number just one less is 011...1. Hence if we have & operator between the 2, we will get 0.We have discussed the solution here. Also, as 0 is not in power of 2, we have to explicitly check if n is greater than 0.

C code : 

bool isPowerOfTwo(int n)
{
    return (n > 0) && ((n & (n - 1)) == 0);
}

Method 3 - Complement and compare

C code

bool isPow2 = ((x & ~(x-1))==x)? x : 0;



Method 4

C code 
bool isPowerOfTwo(int i){
   return i>0 && ((i & -i) == i);
}


Method 5 - Shift right
private static bool IsPowerOfTwo(ulong number)
{
    while (number != 0)
    {
        if (number == 1)
            return true;

        if ((number & 1) == 1)
            // number is an odd number and not 1 - so it's not a power of two.
            return false;

        number = number >> 1;
    }
    return false;
}

Method 6 - Divide the number by 2 until it becomes 0
bool isPowerOfTwo(int n)
{
  if (n == 0)
    return 0;
  while (n != 1)
  {
    if (n%2 != 0)
      return 0;
    n = n/2;
  }
  return 1;
}

Method 7 -Take log of number and check if it is integer
A simple method for this is to simply take the log of the number on base 2 and if you get an integer then number is power of 2.

FOLLOW UP - Clearly Method 2,3 and 4 one-liners and are using bit hacks.

Please share if you have some method not covered above.







0 comments:

Post a Comment