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