LeetCode 342 题解：判断 4 的幂（Power of Four）——从循环除法到 O(1) 位运算

LeetCode 342 题解：判断 4 的幂（Power of Four）——从循环除法到 O(1) 位运算

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本题是 LeetCode 上一道经典的数论与位运算综合题：给定一个 32 位有符号整数，判断它是否为 4 的幂次方。本文将以 problems/342.power-of-four.md 为核心骨架，完整覆盖"循环除法→二进制规律→掩码 0x55555555→数论取模"四条解题路线，并结合仓库中的位运算专题文档与同类型题目，深入剖析n & (n - 1)、奇偶位掩码等位运算技巧的底层原理。读完本文，你将掌握一类"幂次判断"问题的通用思维框架，并能熟练运用位运算将 O(log N) 的循环解法优化到 O(1)。

题目描述

给定一个整数（32 位有符号整数），请编写一个函数来判断它是否是 4 的幂次方。

示例：

输入: 16 输出: true 输入: 5 输出: false

进阶要求：你能不使用循环或者递归来完成本题吗？

这是本题真正的考察点所在。循环/递归版本的实现非常简单，但面试官往往会追加这一问，把题目从"基础模拟"升级为"数论与位运算"的综合考察。本题在面试中出现过多次，相关公司包括百度、Two Sigma（见原文档"公司"一节）。

前置知识

• 数论：幂次方的数学性质、整除与取模
• 位运算：与（&）、异或（^）、移位等基础操作及其二进制视角的语义
• 二进制表示：正整数在二进制下"1 的位置"所表达的信息

其中位运算是本题的核心武器。仓库中的 位运算专题文档 系统总结了异或的性质（任何数和本身异或为 0、任何数和 0 异或为本身、交换律），并收录了 136. 只出现一次的数字、137. 只出现一次的数字 2（同目录存在对应解法）等位运算套路题，建议先阅读该专题再攻克本题。

解法一：循环除法（直觉解法）

最符合直觉的做法是：不停地除以 4，直到不能再被 4 整除为止，然后判断结果是否为 1。

while (num && num % 4 == 0) { num /= 4; } return num == 1;

这段逻辑的正确性建立在整除性质之上：如果num是 4 的幂次方，即num = 4^k，那么连续除以 k 次 4 后恰好得到 1；否则除以 4 的过程中会得到一个既不是 0、又不是 1 的数（或者直接除不尽）。

该解法的时间复杂度为 O(log₄ n)，正确但无法满足"不使用循环/递归"的进阶要求。因此我们需要换一种思路——从二进制表示出发。

解法二：位运算 + 掩码 0x55555555（核心解法）

4 的幂次方的二进制规律

先观察 4 的幂次方用二进制表示时的形态：

发现规律：4 的幂次方的二进制表示中，唯一的 1 出现在奇数位（从最低位 0 开始计数，即第 2、4、6… 位），且不在最低位，其余位置全部为 0。本质上，4^k = 2^(2k)，即它是 2 的幂次方，且指数必须是偶数，反映到二进制上就是"1 后面跟着偶数个 0"。

再回顾 2 的幂次方的特点：最低位之外，其他位置有且仅有一个 1（这个 1 可以出现在任意位置）。

将问题拆解为两个条件

如果一个数字是 4 的幂次方，那么它只需满足两个条件：

1. 它是 2 的幂次方——这能保证最低位之外，其他位置有且仅有一个 1；
2. 这个 1 不在偶数位置，一定在奇数位置——这能把"2 的幂"进一步收窄为"4 的幂"。

条件一：如何 O(1) 判断 2 的幂？

显然不能不停地除以 2 看结果是否为 1，那样又回到了循环。这里有一个经典 trick：

如果一个数字 n 是 2 的幂次方，那么n & (n - 1)一定等于 0。

原因简述：n - 1会把 n 的最低位的 1 变成 0，并把其右边的所有 0 变成 1。当 n 只有一个 1（即 2 的幂）时，n与n - 1没有任何一位同时为 1，按位与的结果自然为 0；反之，若 n 不止一个 1，则n & (n - 1)至少保留高位的 1，结果非 0。这也是 191. 位 1 的个数 中n = n & (n - 1)循环消除最低位 1 的同一原理。

条件二：如何判断 1 在奇数位？

我们可以构造一个特殊数字：奇数位都是 1，偶数位都是 0，然后将它与 n 做按位与运算。如果结果等于 n 本身，那么 n 唯一的 1 必然落在奇数位——因为如果它落在偶数位，与这个特殊数字求与的结果就是 0 了。

题目限定 n 是 32 位有符号整数，因此特殊数字应为：

01010101010101010101010101010101

（一共 32 位，最低位为 1，从低位向高位看是"奇位 1、偶位 0"交替。）

如上图所示：64（二进制1000000，唯一的 1 在第 6 位，属奇数位）与特殊数字求与，结果仍是自身，因此 64 是 4 的幂；8（二进制1000，唯一的 1 在第 3 位，属偶数位）虽然是 2 的幂，但不是 4 的幂，与特殊数字求与结果为 0。

这一长串 0101 的二进制在十六进制下可以写成更优雅的形式。原文档作者使用计算器找到了这个高辨识度的写法：0x55555555。因为0x5 = 0101，重复 8 次恰好得到 32 位交替的0101...0101。

提示：0x55555555这类奇偶位掩码是位运算中的"常规武器"。在 190. 颠倒二进制位 的拓展解法中，就通过0xaaaaaaaa与0x55555555两两相邻位对调；191. 位 1 的个数 的 C++ 分治解法同样定义了ODD_BIT_MASK = 0xAAAAAAAA与EVEN_BIT_MASK = 0x55555555。可见掌握这组掩码可以一通百通。

最终代码

JavaScript 实现：

/* * @lc app=leetcode id=342 lang=javascript * * [342] Power of Four */ /** * @param {number} num * @return {boolean} */ var isPowerOfFour = function (num) { // tag: 数论 if (num === 1) return true; if (num < 4) return false; if ((num & (num - 1)) !== 0) return false; return (num & 0x55555555) === num; };

Python 实现：

class Solution: def isPowerOfFour(self, num: int) -> bool: if num == 1: return True elif num < 4: return False else: if not num & (num - 1) == 0: return False else: return num & 0x55555555 == num

代码逻辑拆解：

• num === 1与num < 4是两个快速剪枝分支：1 是 4 的 0 次幂，直接返回 true；小于 4 的正整数（2、3）不可能是 4 的幂（0 需结合语言对 0 的处理一并考虑，(0 & -1) === 0会误判，故先被num < 4排除）；
• (num & (num - 1)) !== 0排除所有"不是 2 的幂"的数；
• (num & 0x55555555) === num进一步排除"是 2 的幂但唯一的 1 在偶数位"的数（如 2、8、32）。

三个条件层层递进、缺一不可，全部通过则num必为 4 的幂次方。

解法三：数论取模（(num - 1) % 3 === 0）

说实话，掩码解法不容易想到。其实还有一条更巧妙的数论路线：

如果一个数字是 4 的幂次方，那么它只需满足：

1. 是 2 的倍数（更准确地说是 2 的幂次方）；
2. 减去 1 之后是 3 的倍数。

为什么成立？由幂等余的性质可知：4 ≡ 1 (mod 3)，因此对任意非负整数 k，4^k ≡ 1^k ≡ 1 (mod 3)，即4^k - 1恒能被 3 整除；反过来，若n = 2^m且n ≡ 1 (mod 3)，则2^m ≡ 1 (mod 3)，而2 ≡ -1 (mod 3)，所以(-1)^m ≡ 1 (mod 3)，m 必为偶数，即n = 2^(2k) = 4^k。两者互为充要条件。

对应的一行式代码：

return num > 0 && (num & (num - 1)) === 0 && (num - 1) % 3 === 0;

这里num > 0排除 0 与负数（0 能被 3 整除、0 & -1 === 0，但 0 不是 4 的幂）；(num & (num - 1)) === 0保证是 2 的幂；(num - 1) % 3 === 0保证指数为偶数。三者结合，时间复杂度同样是 O(1)，且不需要记住掩码，思维负担更小，在面试中容易讲清楚数学依据。

解法四：二进制字符串判断（Python）

原文档还提供了一种"降维打击"的实现：把数字转成二进制字符串，再利用字符串操作判断。核心思路是：4 的幂的二进制串形如1后跟偶数个0（即100...0，0 的个数为偶数）。

# 另一种解法：将数字转化为二进制表示的字符串，利用字符串的相关操作进行判断 class Solution: def isPowerOfFour(self, num: int) -> bool: binary_num = bin(num)[2:] # 去掉 '0b' 前缀 return binary_num.strip('0') == '1' and len(binary_num) % 2 == 1

拆解一下：

• bin(num)[2:]得到不含0b前缀的二进制串；
• binary_num.strip('0') == '1'等价于"去掉所有末尾 0 后只剩一个 1"，即二进制串中恰好一个 1（是 2 的幂）；
• len(binary_num) % 2 == 1表示二进制串长度为奇数，即1后面跟了偶数个 0，这正是4^k = 2^(2k)的二进制形态。

该解法的时间复杂度退化为 O(log n)（bin()本身需要线性扫描），但胜在直观、不易出错，可作为面试中的兜底方案或快速验证手段。

复杂度分析

以上四种解法（掩码法、取模法）的复杂度一致：

• 时间复杂度：O(1)——仅涉及常数次位运算或取模运算；
• 空间复杂度：O(1)——只使用常数额外空间。

对比循环除法解法的 O(log₄ n) 时间复杂度，位运算与数论解法在理论上实现了质的飞跃，这也是题目"进阶"一问所期望的答案方向。

关键点总结

• 数论视角：4^k = 2^(2k)，4 的幂必是 2 的幂，且指数为偶数；
• 2 的幂判定：n & (n - 1) === 0（最低位之外仅一个 1），这是贯穿多个位运算题目的核心 trick，详见 191. 位 1 的个数；
• 奇偶位判定：掩码0x55555555（32 位交替的 0101）按位与结果等于自身，即唯一的 1 在奇数位；同族掩码0xAAAAAAAA可见于 190. 颠倒二进制位；
• 模运算性质：4 ≡ 1 (mod 3)，故4^k - 1恒为 3 的倍数，由此得到免掩码的 O(1) 判定式；
• 二进制字符串：1后跟偶数个 0 是 4 的幂的字符串级判据，适合快速验证。

仓库中对应本题的图解源文件为 assets/drawio/342.power-of-four.drawio，三张配图分别展示了二进制规律、掩码运算过程与0x55555555的来源；位运算的系统性方法论可继续阅读 位运算专题。将本题与 191. 位 1 的个数、190. 颠倒二进制位 放在一起练习，即可完整掌握"幂次判断 + 奇偶位掩码"这一类位运算套路。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode