企业官网建设流程全解析

LeetCode 342 Power of Four（4 的幂）全解法剖析：递归、迭代、对数与位运算的九种语言实现

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文围绕 LeetCode 342「4 的幂（Power of Four）」展开，系统梳理判断正整数是否为 4 的整数次幂的 6 类解法——递归、迭代、对数数学法、枚举偶数位位运算、0x55555555位掩码法以及n % 3 == 1同余判定法，并逐一给出 Python、Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的完整实现。读者读完将掌握「幂判定」类问题的思考范式：如何从暴力除法逐步优化到常数时间的纯位运算，以及浮点对数方案的精度隐患与规避方式。文中所有实现均可在当前仓库 articles/power-of-four.md 与各语言源码目录中找到对应版本。

前置知识

在动手解题之前，需要先具备三块基础能力，它们也是后续所有解法的理论地基：

• 位运算（Bit Manipulation）：理解二进制表示、按位与（&）、左移（<<）等操作，以及 2 的幂在二进制中的形态（只有一个二进制位为 1）。
• 对数（Logarithms）：利用换底公式log_a(n) = log(n) / log(a)反解指数，并判断结果是否为整数。
• 2 的幂判定技巧：n & (n - 1) == 0能在一行内判断n是否为 2 的幂——因为减 1 会借位翻转所有低位，只有恰好一个二进制位为 1 的数才会让按位与结果归零。

仓库中 articles/power-of-two.md、articles/number-of-one-bits.md 等文章对上述位运算技巧有更深入的展开，可交叉阅读。

方法一：递归

思路（Intuition）

若n是 4 的幂，则反复除以 4 最终必然到达 1（因为4^0 = 1）。如果在除的过程中某一步n不再能被 4 整除，或n一开始就非正，则它一定不是 4 的幂。

这天然引导出一个递归解法：每一步把问题规模缩小为原来的四分之一，即递归地判断n / 4是否为 4 的幂。

算法步骤

1. 若n == 1，返回true（4^0 = 1）。
2. 若n <= 0或n不能被 4 整除（n % 4 != 0），返回false。
3. 递归判断n / 4是否为 4 的幂。

多语言实现

class Solution: def isPowerOfFour(self, n: int) -> bool: if n == 1: return True if n <= 0 or n % 4: return False return self.isPowerOfFour(n // 4)

public class Solution { public boolean isPowerOfFour(int n) { if (n == 1) { return true; } if (n <= 0 || n % 4 != 0) { return false; } return isPowerOfFour(n / 4); } }

class Solution { public: bool isPowerOfFour(int n) { if (n == 1) { return true; } if (n <= 0 || n % 4 != 0) { return false; } return isPowerOfFour(n / 4); } };

class Solution { /** * @param {number} n * @return {boolean} */ isPowerOfFour(n) { if (n === 1) { return true; } if (n <= 0 || n % 4 !== 0) { return false; } return this.isPowerOfFour(Math.floor(n / 4)); } }

public class Solution { public bool IsPowerOfFour(int n) { if (n == 1) { return true; } if (n <= 0 || n % 4 != 0) { return false; } return IsPowerOfFour(n / 4); } }

func isPowerOfFour(n int) bool { if n == 1 { return true } if n <= 0 || n%4 != 0 { return false } return isPowerOfFour(n / 4) }

class Solution { fun isPowerOfFour(n: Int): Boolean { if (n == 1) { return true } if (n <= 0 || n % 4 != 0) { return false } return isPowerOfFour(n / 4) } }

class Solution { func isPowerOfFour(_ n: Int) -> Bool { if n == 1 { return true } if n <= 0 || n % 4 != 0 { return false } return isPowerOfFour(n / 4) } }

impl Solution { pub fn is_power_of_four(n: i32) -> bool { if n == 1 { return true; } if n <= 0 || n % 4 != 0 { return false; } Self::is_power_of_four(n / 4) } }

仓库实现印证

当前仓库 kotlin/0342-power-of-four.kt 中保留的正是这条递归路线，其注释直接标注了复杂度特征：

// recursion time O(logn) class Solution { fun isPowerOfFour(n: Int): Boolean { if (n == 1) return true if (n <= 0 || n % 4 != 0) return false return isPowerOfFour(n / 4) } }

复杂度分析

• 时间复杂度：$O(1)$。从纯渐进意义上讲，递归深度为log4(n)次，但在 32 位整数范围内最多只需约 16 次除法，次数恒定，因此按常数看待。
• 空间复杂度：$O(1)$。递归调用栈深度与时间复杂度同量级（至多十几层），不随输入规模增长而增长。

方法二：迭代

思路（Intuition）

迭代解法与递归逻辑完全一致，只是把「递归调用」换成「while 循环」：只要n仍大于 1，就持续判断能否被 4 整除并整除下去。若循环结束后n恰好等于 1，则原数就是 4 的幂。该写法避免了函数调用栈，代码更贴近底层循环语义。

算法步骤

1. 若n为负数，直接返回false。
2. 当n > 1时循环：
   • 若n不能被 4 整除，返回false；
   • 否则令n = n / 4。
3. 循环结束后，n == 1则返回true，否则返回false。

多语言实现

class Solution: def isPowerOfFour(self, n: int) -> bool: if n < 0: return False while n > 1: if n % 4: return False n //= 4 return n == 1

public class Solution { public boolean isPowerOfFour(int n) { if (n < 0) return false; while (n > 1) { if (n % 4 != 0) return false; n /= 4; } return n == 1; } }

class Solution { public: bool isPowerOfFour(int n) { if (n < 0) return false; while (n > 1) { if (n % 4 != 0) return false; n /= 4; } return n == 1; } };

class Solution { /** * @param {number} n * @return {boolean} */ isPowerOfFour(n) { if (n < 0) return false; while (n > 1) { if (n % 4 !== 0) return false; n = Math.floor(n / 4); } return n === 1; } }

public class Solution { public bool IsPowerOfFour(int n) { if (n < 0) return false; while (n > 1) { if (n % 4 != 0) return false; n /= 4; } return n == 1; } }

func isPowerOfFour(n int) bool { if n < 0 { return false } for n > 1 { if n%4 != 0 { return false } n /= 4 } return n == 1 }

class Solution { fun isPowerOfFour(n: Int): Boolean { if (n < 0) return false var num = n while (num > 1) { if (num % 4 != 0) return false num /= 4 } return num == 1 } }

class Solution { func isPowerOfFour(_ n: Int) -> Bool { if n < 0 { return false } var num = n while num > 1 { if num % 4 != 0 { return false } num /= 4 } return num == 1 } }

impl Solution { pub fn is_power_of_four(n: i32) -> bool { if n < 0 { return false; } let mut num = n; while num > 1 { if num % 4 != 0 { return false; } num /= 4; } num == 1 } }

仓库实现印证

仓库 cpp/0342-power-of-four.cpp 保存的正是迭代除法的变体，它用一个布尔标志pow记录中间状态，并利用三元表达式在循环内完成「整除则继续、否则置否」的判断：

class Solution{ public: bool isPowerOfFour(int n){ if(n <= 0){ return false; } bool pow = true; while((n > 1) && (pow == true)){ n % 4 == 0 ? n = n / 4 : pow = false; } return pow; } };

注意该实现与标准迭代版的等价性：n % 4 == 0时继续除以 4，否则把pow置为false退出循环；最终返回的pow只有在n被反复除尽到 1 时才保持true。

复杂度分析

• 时间复杂度：$O(1)$（32 位整数范围内循环次数恒定，至多 16 轮）。
• 空间复杂度：$O(1)$，仅使用常数个变量。

方法三：数学（对数）

思路（Intuition）

若n是 4 的幂，则存在整数k使得n = 4^k。两边同时取以 4 为底的对数得到k = log4(n)。只要这个对数值是整数，n就是 4 的幂。

判断对数值是否为整数，可以通过「对 1 取模余数为 0」来验证。

算法步骤

1. 若n <= 0，返回false。
2. 计算log(n) / log(4)（换底公式，得到以 4 为底的对数）。
3. 若该值对 1 取模等于 0（无小数部分），返回true，否则返回false。

多语言实现

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

public class Solution { public boolean isPowerOfFour(int n) { return n > 0 && Math.log(n) / Math.log(4) % 1 == 0; } }

class Solution { public: bool isPowerOfFour(int n) { return n > 0 && fmod(log(n) / log(4), 1) == 0; } };

class Solution { /** * @param {number} n * @return {boolean} */ isPowerOfFour(n) { return n > 0 && (Math.log(n) / Math.log(4)) % 1 === 0; } }

public class Solution { public bool IsPowerOfFour(int n) { return n > 0 && Math.Log(n) / Math.Log(4) % 1 == 0; } }

func isPowerOfFour(n int) bool { if n <= 0 { return false } logVal := math.Log(float64(n)) / math.Log(4) return math.Mod(logVal, 1) == 0 }

class Solution { fun isPowerOfFour(n: Int): Boolean { return n > 0 && Math.log(n.toDouble()) / Math.log(4.0) % 1 == 0.0 } }

class Solution { func isPowerOfFour(_ n: Int) -> Bool { return n > 0 && log(Double(n)) / log(4.0).truncatingRemainder(dividingBy: 1) == 0 } }

impl Solution { pub fn is_power_of_four(n: i32) -> bool { n > 0 && (n as f64).ln() / 4.0_f64.ln() % 1.0 == 0.0 } }

仓库实现印证与精度警示

仓库 java/0342-power-of-four.java 保存的正是对数方案，其判断整数的做法是「对数值与其取整后相等」：

class Solution { public boolean isPowerOfFour(int n) { double x = Math.log(n) / Math.log(4); return x == (int) x; } }

需要特别提醒：log(n) / log(4)在浮点运算下并非总是精确的整数。例如log(64) / log(4)在某些平台上会得到2.9999999...而非精确的3，导致% 1 == 0判断失败、把合法的 4 的幂误判为false。仓库 Java 版用x == (int) x判断也面临同样的精度风险。这类浮点方案适合作为思路演示，若追求稳健，建议改用纯整数路线（迭代除法或位运算）。

复杂度分析

• 时间复杂度：$O(1)$。
• 空间复杂度：$O(1)$。

方法四：位运算（枚举偶数位）

思路（Intuition）

4 的幂在二进制下的形态为1、100、10000、1000000……即恰好只有一个置位（set bit），且该位总是处于偶数位（第0、2、4、…… 位）。

因此可以遍历所有偶数位（第0到第30位，步长为 2），检查n是否恰好等于其中某个位置的1 << i（即4^(i/2)）对应的值：1、4、16、64……

算法步骤

1. 若n为负数，返回false。
2. 从第0位到第30位、步长2遍历：
   • 若n == (1 << i)，返回true。
3. 遍历结束未命中，返回false。

遍历上界取30是因为 32 位有符号整数的最高位（符号位）不可用；若在 Python 这类任意精度整数环境中，理论上可扩展到更大范围。

多语言实现

class Solution: def isPowerOfFour(self, n: int) -> bool: if n < 0: return False for i in range(0, 32, 2): if n == (1 << i): return True return False

public class Solution { public boolean isPowerOfFour(int n) { if (n < 0) return false; for (int i = 0; i < 32; i += 2) { if (n == (1 << i)) { return true; } } return false; } }

class Solution { public: bool isPowerOfFour(int n) { if (n < 0) return false; for (int i = 0; i < 32; i += 2) { if (n == (1 << i)) { return true; } } return false; } };

class Solution { /** * @param {number} n * @return {boolean} */ isPowerOfFour(n) { if (n < 0) return false; for (let i = 0; i < 32; i += 2) { if (n === 1 << i) { return true; } } return false; } }

public class Solution { public bool IsPowerOfFour(int n) { if (n < 0) return false; for (int i = 0; i < 32; i += 2) { if (n == (1 << i)) { return true; } } return false; } }

func isPowerOfFour(n int) bool { if n < 0 { return false } for i := 0; i < 32; i += 2 { if n == (1 << i) { return true } } return false }

class Solution { fun isPowerOfFour(n: Int): Boolean { if (n < 0) return false for (i in 0 until 32 step 2) { if (n == (1 shl i)) { return true } } return false } }

class Solution { func isPowerOfFour(_ n: Int) -> Bool { if n < 0 { return false } for i in stride(from: 0, to: 32, by: 2) { if n == (1 << i) { return true } } return false } }

impl Solution { pub fn is_power_of_four(n: i32) -> bool { if n < 0 { return false; } for i in (0..32).step_by(2) { if n == (1 << i) { return true; } } false } }

复杂度分析

• 时间复杂度：$O(1)$（固定 16 次迭代）。
• 空间复杂度：$O(1)$。

方法五：位掩码 I（0x55555555）

思路（Intuition）

4 的幂首先必须是 2 的幂（二进制只有一个置位），可用n & (n - 1) == 0验证。但并非所有 2 的幂都是 4 的幂（如2、8就不是）。

关键区别在于：4 的幂唯一的置位落在偶数位上。掩码0x55555555（二进制01010101...0101）在所有偶数位上都是 1、奇数位上都是 0。将n与该掩码做按位与，若结果仍等于n，说明n唯一的置位确实在偶数位，即n是 4 的幂。

算法步骤

1. 检查n > 0。
2. 检查n是 2 的幂：(n & (n - 1)) == 0。
3. 检查置位在偶数位：(n & 0x55555555) == n。
4. 三个条件同时满足才返回true。

多语言实现

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

public class Solution { public boolean isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) == n; } }

class Solution { public: bool isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) == n; } };

class Solution { /** * @param {number} n * @return {boolean} */ isPowerOfFour(n) { return n > 0 && (n & (n - 1)) === 0 && (n & 0x55555555) === n; } }

public class Solution { public bool IsPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) == n; } }

func isPowerOfFour(n int) bool { return n > 0 && (n&(n-1)) == 0 && (n&0x55555555) == n }

class Solution { fun isPowerOfFour(n: Int): Boolean { return n > 0 && (n and (n - 1)) == 0 && (n and 0x55555555) == n } }

class Solution { func isPowerOfFour(_ n: Int) -> Bool { return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) == n } }

impl Solution { pub fn is_power_of_four(n: i32) -> bool { n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) == n } }

仓库实现印证

仓库 kotlin/0342-power-of-four.kt 中同时保留了一个细微变体，把末位判断从(n & 0x55555555) == n换成了(n & 0x55555555) != 0：

// bit manipulation time O(1) class Solution { fun isPowerOfFour(n: Int) = n > 0 && (n and (n - 1) == 0) && (n and 0x55555555) != 0 }

两种写法在「n已是 2 的幂」的前提下等价：既然n只有一个置位，n & 0x55555555非零即意味着该置位命中了掩码中的某个偶数位。== n的表达更严格直观，!= 0则更简洁，二者均正确。

复杂度分析

• 时间复杂度：$O(1)$（三次常数级位运算）。
• 空间复杂度：$O(1)$。

方法六：位掩码 II（n % 3 == 1）

思路（Intuition）

4 的幂对 3 取模存在一个优美的规律：4^k mod 3 = 1对所有非负整数k恒成立。原因是4 = 3 + 1，由二项式展开(3 + 1)^k可知展开式中除最后一项1^k = 1外，其余各项都含因子 3，故余数恒为 1。

反过来，非 4 幂的 2 的幂（如2、8、32）对 3 取模余数为 2。于是「2 的幂判定 + 对 3 取模余 1」组合起来，就能把 4 的幂从所有 2 的幂中精确区分出来，全程无浮点、无循环。

算法步骤

1. 检查n > 0。
2. 检查n是 2 的幂：(n & (n - 1)) == 0。
3. 检查n % 3 == 1，确认它具体是 4 的幂。
4. 条件全部满足才返回true。

多语言实现

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

public class Solution { public boolean isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && (n % 3 == 1); } }

class Solution { public: bool isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && (n % 3 == 1); } };

class Solution { /** * @param {number} n * @return {boolean} */ isPowerOfFour(n) { return n > 0 && (n & (n - 1)) === 0 && n % 3 == 1; } }

public class Solution { public bool IsPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && (n % 3 == 1); } }

func isPowerOfFour(n int) bool { return n > 0 && (n&(n-1)) == 0 && n%3 == 1 }

class Solution { fun isPowerOfFour(n: Int): Boolean { return n > 0 && (n and (n - 1)) == 0 && n % 3 == 1 } }

class Solution { func isPowerOfFour(_ n: Int) -> Bool { return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1 } }

impl Solution { pub fn is_power_of_four(n: i32) -> bool { n > 0 && (n & (n - 1)) == 0 && n % 3 == 1 } }

复杂度分析

• 时间复杂度：$O(1)$。
• 空间复杂度：$O(1)$。

常见陷阱

混淆「2 的幂」与「4 的幂」

所有 4 的幂都是 2 的幂，但反之不成立。如果只做(n & (n - 1)) == 0这一项检查，2、8、32等「2 的幂但非 4 的幂」的值也会被误判通过。必须追加一条约束（置位位于偶数位，或n % 3 == 1）来收窄判定范围。

对数方案中的浮点精度误差

log(n) / log(4)会引入浮点误差。典型反例是log(64) / log(4)，某些平台下计算结果为2.9999999...而非精确的3，此时「对 1 取模等于 0」的比较会把合法的 4 的幂错误拒绝。可考虑引入容差（epsilon）比较、四舍五入后复核，或干脆改用基于整数的迭代/位运算方案。仓库 java/0342-power-of-four.java 的对数实现就属于此类精度敏感写法，使用时需留意。

六种解法对比总结

六种方法的时间复杂度与空间复杂度均为 $O(1)$，区别主要体现在实现的优雅程度、是否依赖浮点精度，以及是否需要循环/递归栈。工程上最推荐的是方法五或方法六——它们只需三五个常数级运算即可完成判定。

边界情况自查清单

编写或验证实现时，建议覆盖以下输入：

• 1（4^0，应为true）；
• 4、16、64、256（连续 4 的幂，均为true）；
• 0（非正数，应为false）；
• 负数（如-4，应为false）；
• 2、8、32（2 的幂但非 4 的幂，应为false）；
• 5、12、20（普通非幂值，应为false）。

对照仓库中的 cpp/0342-power-of-four.cpp、java/0342-power-of-four.java、kotlin/0342-power-of-four.kt 三份实现逐一跑通上述用例，即可确认理解无误。若想进一步巩固位运算技巧，可继续阅读仓库中 articles/power-of-two.md、articles/sum-of-two-integers.md 与 articles/single-number.md 等相邻题目。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode