LeetCode 342. 4的幂

2022-01-12 HGNULB 约 8 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 342. 4的幂

题意分析

判断一个 32 位有符号整数是否等于 $4^x$，其中 x 是非负整数，返回布尔值。

输入范围是完整的 int，也就是说负数和 0 都会作为输入出现。由于任何非负指数的 4 的幂都是正数，负数和 0 必须直接判否，这是第一道闸门。

题目明确提出「能否不使用循环或递归」，这句追问把期待的解法从「反复除以 4」推向了「对二进制表示做一次性判定」。也就是说，出题人想看的是你能不能把「是 4 的幂」翻译成一组位模式约束。

值域上限是 $2^{31}-1$，所以合法答案只有 16 个：$4^0 = 1$ 到 $4^{15} = 1073741824$。判定的目标就是精确地把这 16 个数从 43 亿个整数中挑出来。

边界包括：n = 1（$4^0$，必须返回真）；n = 0 和一切负数（返回假）；以及 2 的奇数次幂如 2、8、32，它们是 2 的幂但不是 4 的幂，正是最容易被漏掉的一类反例。

解法：位运算判定

核心思路

朴素做法是不断把 n 除以 4，只要还能整除就继续，最后看是否恰好剩下 1。它正确且只需十几步，但用到了循环，与题目「不用循环或递归」的追问不符，且需要小心处理 n <= 0 和不能整除时的提前退出。

换成位视角。$4^x = 2^{2x}$，所以每个 4 的幂在二进制下都只有一个 1，且这个 1 位于偶数下标（从最低位记为第 0 位算起：$4^0 = 1$ 的 1 在第 0 位，$4^1 = 4$ 在第 2 位，$4^2 = 16$ 在第 4 位，依此类推）。

反过来，「只有一个 1 且该 1 落在偶数下标」这个条件也充分：设唯一的 1 在第 $2k$ 位，则 n $= 2^{2k} = 4^k$。所以判定被精确拆成三条相互独立的检查：

第一条，n > 0。这排除了 0 和全部负数；同时也保证了后面两条检查不会被符号位干扰。

第二条，n 的二进制中恰好有一个 1，用经典恒等式 (n & (n - 1)) == 0 判定。它成立的原因是：减一会把最低位的 1 翻成 0、并把它右边的所有 0 翻成 1，其余高位不变；因此按位与之后，最低位的那个 1 必然消失，而其他 1 全部保留。结果为 0 当且仅当原本就只有那一个 1。这一步筛出的是所有 2 的幂。

第三条，这个 1 落在偶数下标上，用掩码 0x55555555 判定。该常数的二进制是 0101...0101，即第 0、2、4、…、30 位为 1。既然第二条已经保证 n 只有一个 1，那么 (n & 0x55555555) != 0 就等价于「那唯一的 1 恰好命中了掩码中的某一位」，也就是落在偶数下标上。这一步把 2 的奇数次幂（2、8、32、…）剔除掉。

三条检查全过就是 4 的幂，全程无循环无递归，只有常数次算术和位运算。

解题步骤

先判 n <= 0 直接返回假。之所以要放在最前面，是因为负数在补码下最高位为 1，(n & (n - 1)) 的结果无法反映「是不是只有一个 1」的直觉语义（例如 Integer.MIN_VALUE 只有一个 1，会骗过第二条检查），必须提前拦下。

再判 (n & (n - 1)) != 0 就返回假。之所以用这个恒等式而不是逐位数 1 的个数，是因为它一次运算就能回答「是否只有一个 1」，而逐位统计要么写循环、要么调库函数，两者都偏离了本题想考的点。

最后返回 (n & 0x55555555) != 0。之所以这一步能直接作为最终答案，是因为前两条已经把候选缩小到「恰好一个 1 的正数」，剩下的唯一分歧就是这个 1 在奇数下标还是偶数下标，掩码一次与运算即可裁决。

之所以不需要写成 (n & 0x55555555) == n，是因为在「只有一个 1」的前提下，!= 0 与 == n 完全等价；但如果去掉了第二条检查，就必须改用 == n 这种更强的写法，两者不能随意互换。

以 n = 16 走一遍：16 > 0 通过第一关。16 的二进制是 0001 0000，15 是 0000 1111，按位与得 0，通过第二关。掩码 0x55555555 的低八位是 0101 0101，与 0001 0000 相与得 0001 0000，非零，返回真。核对：$16 = 4^2$，正确。

再以 n = 8 走一遍（这是最关键的反例）：8 > 0 通过。8 是 0000 1000，7 是 0000 0111，与得 0，通过第二关——说明 8 确实是 2 的幂。最后掩码相与：0000 1000 & 0101 0101 = 0000 0000，为零，返回假。核对：8 是 $2^3$ 但不是 4 的幂，正确。若省掉第三关，这里就会误判为真。

再以 n = 5 走一遍：5 > 0 通过。5 是 0101，4 是 0100，与得 0100 非零，第二关就返回假。正确——5 连 2 的幂都不是。

最后以 n = 1 走一遍：1 > 0 通过；1 & 0 = 0 通过；1 & 0x55555555 = 1 非零，返回真。核对：$1 = 4^0$，正确。

代码实现

class Solution {
    public boolean isPowerOfFour(int n) {
        if (n <= 0) {
            return false;
        }

        if ((n & (n - 1)) != 0) {
            return false;
        }

        return (n & 0x55555555) != 0;
    }
}

func isPowerOfFour(n int) bool {
    if n <= 0 {
        return false
    }

    if n&(n-1) != 0 {
        return false
    }

    return n&0x55555555 != 0
}

复杂度分析

时间复杂度：$O(1)$，凭据是整个判定只有三次比较、一次减法和两次按位与，没有任何循环或递归，运算次数与输入数值大小完全无关。

空间复杂度：$O(1)$，凭据是全程没有申请任何辅助结构，只在寄存器级别使用输入参数和一个字面量掩码。

关键点总结

「判断是否为某数的幂」这类问题要先把条件翻译成二进制模式：$2^k$ 对应「只有一个 1」，$4^k$ 在此基础上再加「这个 1 在偶数下标」，$8^k$ 则是「下标能被 3 整除」，掩码相应换成 0x49249249。整个家族用同一套框架。

n & (n - 1) 清除最低位的 1，是位运算里最高频的恒等式；等于 0 即判定「至多一个 1」，配合 n > 0 就精确等价于「是 2 的幂」。这个组合值得直接背下来。

掩码判定的前提是前一步已经保证「只有一个 1」。前提不同则写法不同：有前提时 != 0 足够，无前提时必须写 == n。做位运算题要随时明确当前已经建立了哪些前提。

符号位是位运算题的头号陷阱，负数在补码下会让「数 1 的个数」这类直觉失效，所以正数检查必须放在所有位技巧之前。

面试视角：这题面试官几乎一定会追问「不用循环怎么做」，然后再追问「为什么掩码是 0x55555555」和「能否推广到 8 的幂」。答题时要能当场把掩码的二进制写出来并解释它标记的是哪些位；另一个常被认可的等价答案是「先判是 2 的幂，再判 n % 3 == 1」，理由是 $4^k \equiv 1 \pmod 3$，能主动提出这个数论视角会明显加分。

易错点总结

只写 (n & (n - 1)) == 0 就返回：用例 n = 8，它是 2 的幂但不是 4 的幂，会误返回真。

忘记 n <= 0 的前置检查：用例 n = -2147483648，其补码只有最高位为 1，n & (n - 1) 结果为 0 通过第二关，随后 n & 0x55555555 为 0 侥幸返回假；但用例 n = 0 时 0 & -1 = 0 通过第二关、掩码相与也为 0 返回假也侥幸对，真正危险的是把第三关写成 == n 的变体时 n = 0 会返回真。

掩码写成 0xAAAAAAAA：用例 n = 4，4 & 0xAAAAAAAA = 0 返回假，而 4 正是 $4^1$；这个掩码标记的是奇数下标，方向恰好反了。

掩码写成 0x55555555 但漏掉第二关，且判断用 != 0：用例 n = 5（二进制 101），5 & 0x55555555 = 5 非零返回真，而 5 根本不是任何数的幂。

用 Math.log(n) / Math.log(4) 判断结果是否为整数：用例 n = 1073741824（即 $4^{15}$），浮点误差可能让结果算出 14.999999999999998，取整比较失败返回假。

用 n % 4 == 0 作为判据：用例 n = 12，能被 4 整除但不是 4 的幂，误返回真；用例 n = 1，不能被 4 整除但它是 $4^0$，误返回假。

循环写成 while (n % 4 == 0) n /= 4; return n == 1; 但没有前置正数检查：用例 n = 0，0 % 4 == 0 恒成立且 0 / 4 仍为 0，程序陷入死循环。

Java 里把掩码写成十进制 1431655765 但记错成 1431655766：用例 n = 1，1 & 1431655766 = 0 返回假，而正确答案是真；掩码用十六进制书写才能一眼看出 0101 的重复模式。

Go 里 n 是 64 位 int 而传入了超出 int32 的值（自行测试时）：用例 n = 4294967296（即 $4^{16}$），它只有一个 1 且在第 32 位（偶数下标），但 0x55555555 只覆盖到第 30 位，会返回假；题目限定 32 位输入才使这个掩码成立，掩码宽度必须与值域匹配。

认为「所有偶数下标的 1」都合法而省略第二关，写成 (n & 0x55555555) == n：用例 n = 5，5 & 0x55555555 = 5 等于 n，误返回真；这个写法要求的是「所有的 1 都在偶数位」而非「只有一个 1」，两者不等价。

相似题目

题目	难度	考察点
231. 2 的幂	简单	只需「正数且只有一个 1」，是本题去掉掩码那一步的子问题
326. 3 的幂	简单	底数非 2 的幂，无法用位模式判定，改用最大 3 次幂取模的技巧
191. 位1的个数	简单	反复使用 `n & (n-1)` 消最低位 1 来计数，考察同一恒等式的另一用法
190. 颠倒二进制位	简单	需要逐位取出并重新拼装，也可用分组掩码做位交换加速
405. 数字转换为十六进制数	简单	用掩码与移位按四位一组切分，考察对负数补码的正确处理