题目描述

给定一个int型整数，请判断它是不是4的整数次幂。

进一步： 能否不使用递归和循环？

样例1

给定 16；
返回 true；

样例2

给定 5；
返回 false；

算法

(数论) $O(1)$

这道题目类似于LeetCode 326. Power of Three。

$n$ 是4的整数次幂，等价于 $n$ 是平方数，且 $n$ 的质因子只有2。

int范围内，2的最大的整数次幂是 $2^{30}$，所以 $n$ 的质因子只有2，等价于 $n$ 能整除 $2^{30}$。

时间复杂度分析：只有常数次计算，所以时间复杂度是 $O(1)$。

C++ 代码

class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num <= 0) return false;
        int t = sqrt(num);
        return t * t == num && ((1 << 30) % num) == 0;
    }
};