Check if number is a power of 4

Give a method to find whether an integer is a power of 4 or not.

Solution

The classic (mathematical) solution to this is check the log-to-the-base-4 of the number, if it is an integer, then the number is a power of 4, else not.

IF log4(n) is an integer THEN n is a power of 4

The above logic applies to any k. i.e to check if a number is a power of k, see if log to the base k of the number is an integer or not.

Using Bitwise operator:

In this case we use the check of power-of-2 to check for power-of-4. A number n is a power is a power of 4 if, either it is zero, or:

• There is only one bit set in its binary representation (check for power of 2), and
• Number of bits towards the right of set bit is even.

For example:

64 (000…01000000)

has EVEN number of bits (6 - marked in red) on the right of set bit. Power of 4.

32 (000…00100000)

has ODD number of bits (5 - marked in red) on the right of set bit. NOT power of 4.

Code:

A C-language function to check the power of 4 can be implemented as below:

    /** Returns 1 if n is power of 4, else 0 */
    int powerOfFour(unsigned int n)
    {
        // Check for power of 2
        if ( n && !(n & (n-1)) )
        {
            int count = 0;
            // Count 0 bits after set bit
            while(n > 1)
            {
                n  >>= 1;
                count ++;
            }
            // If count is even return 1 else 0
            return (count%2 == 0);
        }
        // If not a power of 2
        return 0;
    }