Leetcode: 342. Power of Four

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

Example:
Given num = 16, return true. Given num = 5, return false.

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

Credits:
Special thanks to @yukuairoy for adding this problem and creating all test cases.

Solution:
The simple idea of this question is, if the number of a power of 4, first of all, it must be powe of 2. There is an easy way to check if a number is a power of 2. 

Secondly, if a number of is power of 4, it must be 4^k = n, which is equal to 2^(2 * k) = n. That means, the only "1" bit must be in the even position, e.g., 0, 2, 4, 6, 8. Therefore, we can check the position of the 1 bit and see if it is in the even position.

Code (Java):

public class Solution {
    public boolean isPowerOfFour(int num) {
        
        if (num <= 0) {
            return false;
        }
        
        if ((num & (num - 1)) != 0) {
            return false;
        }
        
        // check if the '1' bit is on the even position
        int pos = 0;
        int mask = 1;
        for (int i = 0; i < 31; i++) {
            if ((num & mask) == 1) {
                break;
            }
            num = (num >> 1);
            pos++;
        }
        
        return pos % 2 == 0;
    }
}

A better solution:
In the above solution, we use a loop to check the position of the "1" bit. Actually, there is no need of this. We can just check if num & (0x55555555) != 0. That is because if the number is a power of 2, there must be only one "1" bit and that "1" bit must be in the even position of the number. For Hex number 0x55555555, the binary representation is 0101 0101 0101, i.e., the bit 1 must be in the even position. In other words, if the bit 1 (and the only bit 1) is in the odd position, the result of  (num & 0x55555555) must be equal to zero. 

Code (Java):

public class Solution {
    public boolean isPowerOfFour(int num) {
        
        if (num <= 0) {
            return false;
        }
        
        if ((num & (num - 1)) != 0) {
            return false;
        }
        
        // check if the '1' bit is on the even position
        return (num & 0x55555555) != 0;
    }
}