0342. 4的幂.md

0342. 4的幂

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

题目链接

• 0342. 4的幂 - 力扣

题目大意

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

解题思路

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

$n$ 如果是 $4$ 的幂次方，那么 $n$ 肯定是 $2$ 的幂次方，$2$ 的幂次方二进制表示只含有一个 $1$，可以通过 $n \text{ & } (n - 1)$ 将 $n$ 的最后位置上 的 $1$ 置为 $0$，通过判断 $n$ 是否满足 $n \text { & } (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} \mod 3) = (4^x \mod 3) = ((3+1)^x \mod 3) == 1$
• $(2^{2x+1} \mod 3) = ((2 \times 4^x) \mod 3) = ((2 \times (3+1)^x) \mod 3) == 2$

则如果 $n \mod 3 == 1$，则 $n$ 为 $4$ 的幂次方。

代码

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