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:

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: