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