# 342. Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

Input: 16
Output: true

Example 2:

Input: 5
Output: false

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

# Solution

Approach 1: Loop.

Approach 2: Bit manipulation.

# Code (Python)

Approach 1:

Approach 2:

# Code (C++)

Approach 1:

// Loop.
class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num <= 0)
            return false;
        while (num > 1)
        {
            if (num % 4 != 0)
                return false;
            num /= 4;
        }
        return true;
    }
};

Approach 2:

// 4^n == 2^n * 2^n.
class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num <= 0)
            return false;
        int numSqrt = std::sqrt(num);
        return numSqrt * numSqrt == num &&
               (numSqrt & (numSqrt - 1)) == 0;
    }
};

// 0x55555555 == 0b1010101010101010101010101.
class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num <= 0)
            return false;
        return (num & (num - 1)) == 0 &&
            (num & 0x55555555) != 0;
    }
};