Power of Four

Problem

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4x.

Follow up: Could you solve it without loops/recursion?

Constraints

• -231 <= n <= 231 - 1

Solution

The problem Power of Four can be solved using bit manipulation. First, given number can be checked if it is a power of two using the same bitwise technique n & (n-1) == 0 from Power of Two. Next, by using a bitwise and operator to exclude 22k-1 where k = 1, 2, ..., 15, given number can be checked if it is a power of four.

Implementation

class Solution
{
  public:
    bool isPowerOfFour(int n)
    {
        // 00101010101010101010101010101010(2) == 715827882
        return n > 0 && (n & n - 1) == 0 && (n & 715827882) == 0;
    }
};