0342. 4的幂 #

• 标签：位运算、递归、数学
• 难度：简单

题目大意 #

给定一个整数 n，判断 n 是否是 4 的幂次方，如果是的话，返回 True。不是的话，返回 False。

解题思路 #

通过循环可以直接做。但有更好的方法。

n 如果是 4 的幂次方，那么 n 肯定是 2 的幂次方，2 的幂次方二进制表示只含有一个 1，可以通过 n & (n - 1) 将 n 的最后位置上 的 1 置为 0，通过判断 n 是否满足 n & (n - 1) == 0 来判断 n 是否是 2 的幂次方。

若根据上述判断，得出 n 是 2 的幂次方，则可以写为：$n = x^{2k}$ 或者 $n = x^{2k+1}$。如果 n 是 4 的幂次方，则 $n = 2^{k}$。

下面来看一下 $2^{2x}、2^{2x}+1$ 的情况：

• $(2^{2x} % 3) = (4^x % 3) = ((3+1)^x % 3) == 1$
• $(2^{2x+1} % 3) = ((24^x) % 3) = ((2(3+1)^x) % 3) == 2$

则如果 n % 3 == 1，则 n 为 4 的幂次方。

代码 #

1
2
3

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & (n-1)) == 0 and (n-1) % 3 == 0