Check if number is a power of 2

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₂(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:

1. If the number is a power of two, then only 1 bit will be set in its binary representation.
2. 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)));
    }