暴力解法

• 比较所有4的幂
• 因为指数增长很快，在有限的范围内也不会太花时间
• 在当前范围内4的幂最大值为1073741824

class Solution {
    public boolean isPowerOfFour(int n) {
        int temp = 1;
        if(n<0||n>1_073_741_824)return false;
        while(temp<=n){
            if(n==temp)return true;
            temp<<=2;
        }
        return false;
    }
}

时间复杂度	空间复杂度
O(log(n))	O(1)

解法2

• 根据P231学会了如何判断2的幂
• 观察可知，4的幂是在2的幂基础上，1只出现在奇数位上

• 可以先判断是否是2的幂，然后构造一个偶数位全为1的数进行&运算，结果为0就是4的幂

class Solution {
    public boolean isPowerOfFour(int n) {
       int mask = 0xAAAAAAAA;
    return (n>0&&(n&(n-1))==0)&&(n&mask)==0;
    }
}

时间复杂度	空间复杂度
O(1)	O(1)

解法3

• 在2的幂基础上mod3==1

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

时间复杂度	空间复杂度
O(1)	O(1)

不过看起来求模运算不是什么好主意