Leetcode-342: Power of Four

[zeqing-guo]

Description

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?

My Solution

代码的run time是2ms，时间复杂度是，空间复杂度是。

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

Analysis

If a number is power of four, it needs to meet the following condition:

1. The number is positive integer -> num > 0
2. Given the binary form of the number: 1(1), 100(4), 10000(16), ..., the position of 1 is in 0x55555555(010101...0101) -> (0x55555555 & num) == num
3. There is only one 1 in the binary form of the number -> (num & (num - 1)) == 0