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