# Interview Questions

# Check if number is a power of 2

- June 12, 2012
- Posted by: Kamal Rawat
- Category: Algorithms C C++

How will you check if a number if a power of two or not?

For example: 4, 8, 1024 etc are powers of two. But 6, 40, 95 etc are not

### Solution:

**Method-1: Take log to the base 2**

This is pure mathematical solution to the problem. If log_{2}(n) is integer than n is a power of 2, else not.

**Method-2: Keep dividing by 2**

Keep dividing the number by two, i.e, do n = n/2 iteratively until n becomes 1. In any iteration, if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes 1 then it is a power of 2.

/** Check if a number is a power of 2 or not. * IF n is power of 2, return 1, else return 0. */ int powerOfTwo(int n) { if(n==0) { return 0; } while(n != 1) { n = n/2; if(n%2 != 0 && n != 1){ return 0; } } return 1; }

**Method-3: Use Bitwise operators**

This uses two facts:

- If the number is a power of two, then only 1 bit will be set in its binary representation.
- If we subtract 1 from a number which is power of 2, then all the bits after the set-bit (there is only one set bit as per point-1) will become set and the set bit will be unset. i.e:

N = 4, 000100 N-1 = 3, 000011 N = 16, 010000 N-1 = 15, 001111

Hence, If a number is a power of 2 then

N & (N-1)

Will be zero.

The only exception to above rule is when N is Zero. It will give zero as a power of two, which actually is not. Hence, in the check, we can see this explicitly.

/** Check if a number is a power of 2 or not. * IF n is power of 2, return 1, else return 0. */ int powerOfTwo(int n) { return n && (!(n & (n-1))); }