# 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:

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

#### Approach 3: Bit Manipulation

Let's first check if num is a power of two: x > 0 and x & (x - 1) == 0.

Now the problem is to distinguish between even powers of two (when xx is a power of four) and odd powers of two (when xx is not a power of four). In binary representation both cases are single 1-bit followed by zeros.

What is the difference? In the first case (power of four), 1-bit is at even position: bit 0, bit 2, bit 4, etc. In the second case, at odd position.
Hence power of four would make a zero in a bitwise AND with number (101010...10)_2(101010...10)2​:
class Solution {
public boolean isPowerOfFour(int num) {
return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0xaaaaaaaa) == 0);
}
}

#### Approach 4: Bit Manipulation + Math

Let's first check if xx is a power of two: x > 0 and x & (x - 1) == 0. Now one could be sure that x = 2^ax=2a. Though xx is a power of four only if aa is even.

Next step is to consider both cases a = 2ka=2k and a = 2k + 1a=2k+1, and to compute xx modulo after division by three:

(2^{2k} \mod 3) = (4^k \mod 3) = ((3 + 1)^k \mod 3) = 1(22kmod3)=(4kmod3)=((3+1)kmod3)=1

((2^{2k + 1}) \mod 3) = ((2 \times 4^k) \mod 3) = ((2 \times(3 + 1)^k) \mod 3) = 2((22k+1)mod3)=((2×4k)mod3)=((2×(3+1)k)mod3)=2

If xx is a power of two and x % 3 == 1, then xx is a power of four

class Solution {
public boolean isPowerOfFour(int num) {
return (num > 0) && ((num & (num - 1)) == 0) && (num % 3 == 1);
}
}