LeetCode 342 Power of Four4 的幂全解法剖析递归、迭代、对数与位运算的九种语言实现【免费下载链接】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 的幂。算法步骤若n 1返回true4^0 1。若n 0或n不能被 4 整除n % 4 ! 0返回false。递归判断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 的幂。该写法避免了函数调用栈代码更贴近底层循环语义。算法步骤若n为负数直接返回false。当n 1时循环若n不能被 4 整除返回false否则令n n / 4。循环结束后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 1public 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」来验证。算法步骤若n 0返回false。计算log(n) / log(4)换底公式得到以 4 为底的对数。若该值对 1 取模等于 0无小数部分返回true否则返回false。多语言实现class Solution: def isPowerOfFour(self, n: int) - bool: return n 0 and log(n, 4) % 1 0public 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)$。方法四位运算枚举偶数位思路Intuition4 的幂在二进制下的形态为1、100、10000、1000000……即恰好只有一个置位set bit且该位总是处于偶数位第0、2、4、…… 位。因此可以遍历所有偶数位第0到第30位步长为 2检查n是否恰好等于其中某个位置的1 i即4^(i/2)对应的值1、4、16、64……算法步骤若n为负数返回false。从第0位到第30位、步长2遍历若n (1 i)返回true。遍历结束未命中返回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 Falsepublic 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)$。方法五位掩码 I0x55555555思路Intuition4 的幂首先必须是 2 的幂二进制只有一个置位可用n (n - 1) 0验证。但并非所有 2 的幂都是 4 的幂如2、8就不是。关键区别在于4 的幂唯一的置位落在偶数位上。掩码0x55555555二进制01010101...0101在所有偶数位上都是 1、奇数位上都是 0。将n与该掩码做按位与若结果仍等于n说明n唯一的置位确实在偶数位即n是 4 的幂。算法步骤检查n 0。检查n是 2 的幂(n (n - 1)) 0。检查置位在偶数位(n 0x55555555) n。三个条件同时满足才返回true。多语言实现class Solution: def isPowerOfFour(self, n: int) - bool: return n 0 and (n (n - 1)) 0 and (n 0x55555555) npublic 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 (n0x55555555) 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)$。方法六位掩码 IIn % 3 1思路Intuition4 的幂对 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 的幂中精确区分出来全程无浮点、无循环。算法步骤检查n 0。检查n是 2 的幂(n (n - 1)) 0。检查n % 3 1确认它具体是 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 的对数实现就属于此类精度敏感写法使用时需留意。六种解法对比总结方法核心思想是否有浮点风险代码量适用场景递归反复除 4 到 1无短思路演示、教学迭代循环除 4 到 1无短通用、推荐基础版数学对数log4(n)为整数有极短仅限思路展示位运算枚举偶数位匹配1 偶数位无短位运算练习位掩码 I2 的幂 置位在偶数位无极短面试最优解之一位掩码 II2 的幂 n % 3 1无极短面试最优解之一六种方法的时间复杂度与空间复杂度均为 $O(1)$区别主要体现在实现的优雅程度、是否依赖浮点精度以及是否需要循环/递归栈。工程上最推荐的是方法五或方法六——它们只需三五个常数级运算即可完成判定。边界情况自查清单编写或验证实现时建议覆盖以下输入14^0应为true4、16、64、256连续 4 的幂均为true0非正数应为false负数如-4应为false2、8、322 的幂但非 4 的幂应为false5、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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考