# Interview Questions

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; }