判断一个整数是不是 2 的幂这种题我最早是在基础班带模拟训练时遇到的。很多人的第一反应就是写个循环不断除以 2能除到 1 就算通过也有背过位运算口诀的同学直接甩出n (n - 1) 0。这两种方向看起来一个朴素一个华丽但真正写对的人并不多。原因就在于这道题的关键从来不是“会不会判断”而是能不能把除法与位运算背后的二进制逻辑讲清楚同时把所有边界条件都处理干净。这篇就围绕“2 的幂”展开把循环除法、递归、位运算、查表法这几种常见思路全部拆开结合负数、0、整数溢出这些高频坑位给出可以直接复现的代码和测试用例。适合刚开始刷题的初学者也适合准备面试想快速复习位运算的人。就算你已经会做这道题后半部分的延伸技巧和工程场景也值得看一眼。1. 题目拆解为什么一道简单题值得琢磨判断一个整数是不是 2 的幂题干短得不能再短。可我做带题训练时发现越是这种一眼能看懂的题越能暴露细节处理能力。有人记得循环除法有人背得住n (n - 1)但能把负数、0、int 边界全部讲明白的人并不多。所以这一篇不打算只贴答案而是把从除法到位运算的推导过程、边界测试和工程场景一次性说透。1.1 题目本身与判断标准题目输入是一个整数 n要求返回布尔值。首先要明确定义2 的幂指的是2^k其中 k 是非负整数。所以1 2^0也必须返回 true这是很多人容易漏掉的第一个点。负数呢-2、-8 都不是 2 的幂因为 2 的整数次幂永远是正整数。0 更不是0 的二进制全是 0不存在任何 2 的因子。换句话说题目表面上是“判断”实际考察三个边界0、1、负数再加一个 int 范围内的最大 2 的幂。如果你拿n 1或者n 2^某常量去做特判覆盖范围会非常有限一旦输入稍微变化就出错。正确做法是找一个通用的判定标准而不是枚举。1.2 除法和位运算是两种不同的思维模式“除法”想的是数学过程不断除以 2看最后是否变成 1。这种思路最大的优点是不依赖任何计机底层知识用小学生的算术就能理解。缺点是它需要一步步循环时间复杂度是对数级别。虽然O(log n)已经非常快但站在工程角度还有更符合二进制结构的判断方式。“位运算”想的是存储结构2 的幂在二进制里只有最高位是 1其余位全是 0。比如 8 是100016 是1000032 是100000。这个特征比“能被 2 连续整除”更本质也更适合计算机处理。同一个题目除法是顺着数学定义走位运算是顺着计算机底层的表达方式走两条路都值得掌握。1.3 解法总览与复杂度对比解法核心依据时间复杂度备注循环除法不断除以 2看最终是否等于 1O(log n)朴素、可靠、易理解递归除法与循环同思路用递归表达O(log n)递归深度最多几十层位运算用n (n - 1)消去最低位的 1O(1)代码最短但必须处理n 0查表二分预生成 2 的幂序列再二分查找O(log 31)适合极高频调用场景这张表想说明一件事解法没有绝对好坏。位运算在常数上最快但如果漏掉n 0这个条件它反而比循环除法更容易翻车。先保证正确再追求简洁这才是做题的正确顺序。2. 核心细节从除法到位运算的实现解析这一节是全文的重头戏我会从最朴素的办法一路写到一行位运算。别急着抄答案先理解每个版本为什么这样写再动手实现。2.1 先写一个不依赖技巧的循环除法如果让我用最稳妥的方式写第一版我会选循环除法因为它的正确性一目了然public boolean isPowerOfTwo(int n) { if (n 0) { return false; } while (n % 2 0) { n / 2; } return n 1; }思路很直白负数或 0 直接返回 false只要 n 是偶数就不断除以 2最后如果剩下 1说明所有因子 2 都被除干净了。如果剩一个其他数字比如 12 一直除以 2 得到 3说明它还有别的质因子不是 2 的幂。16 一直除以 2 得到 1符合条件。这里有个小细节循环条件写while (n % 2 0)会比while (n 1)配合额外奇偶判断更紧凑。我习惯用前者因为“是不是偶数”直接成了循环前提不需要在循环体里再写if分支。对于初学者来说这个版本也是调试起来最友好的一版。2.2 一行位运算的底层逻辑接着看位运算解法代码只有一行核心逻辑public boolean isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }第一次见到这行代码时我也觉得像魔法。拆开看其实非常单纯n (n - 1)的效果是“把 n 的最低位的 1 变成 0”。如果 n 是 2 的幂二进制里只有一个 1消掉之后结果自然是 0反过来如果 n 的二进制里有多个 1即使消掉最低位那个剩下的结果仍然不是 0。拿 8 和 10 验证8 的二进制是10007 是0111按位与得到0000。10 的二进制是10109 是1001按位与得到1000非 0。所以 8 判定为真10 判定为假结果完全符合预期。那么为什么必须写n 0因为n 0时n - 1 -1在补码表示下所有位都是 10 (-1)还是 00 会被误判成 true。而 0 绝对不是 2 的幂。这个坑我会在第四章展开。2.3 查表与二分备选但值得了解的另类解法还有一种思路是把 2 的幂全部提前算出来。Java 的 int 最多表示到2^31 - 1所以正 2 的幂一共只有 31 个从 2^0 到 2^30。把它们放进定长数组用二分查找判断目标值是否存在public boolean isPowerOfTwo(int n) { if (n 0) return false; int[] pows new int[31]; long v 1; for (int i 0; i 31; i) { pows[i] (int) v; v 1; } int left 0, right pows.length - 1; while (left right) { int mid left (right - left) / 2; if (pows[mid] n) return true; if (pows[mid] n) left mid 1; else right mid - 1; } return false; }31 个元素参与二分时间复杂度可以认为约等于 O(1)。但我仍然建议把位运算作为首选因为查表法需要造数组、走二分实际指令数更多而且把简单问题复杂化了。只有在面试里聊到“思路多样性”或者你正在处理“需要一次性判断海量数值”的超大规模场景时查表法才有亮相的价值。2.4 一个更冷门的判定用最大 2 的幂做整除再分享一个除法与位运算结合的思路。32 位有符号整数范围内最大的 2 的幂是2^30也就是1073741824。任何一个正 2 的幂都能整除它反过来也成立。于是可以写public boolean isPowerOfTwo(int n) { return n 0 (1 30) % n 0; }这个写法非常简洁但适用范围有限如果换成 long 类型就得改成1L 62。它的本质仍然使用了“2 的幂只有 2 这个质因子”的数学特性而不是枚举。这种解法我平时不会用但在面试中能补充出来至少说明你对整数范围有敏感度。3. 实操记录先列测试用例再写实现做题最忌讳“想清楚大概就提交”。这道题我建议先把测试用例设计完整再动代码。下面是我实际操作中会用的一组输入覆盖了正常情况、边界情况和常见陷阱。3.1 测试用例比实现更需要认真设计输入期望结果原因1true2^02true2^116true2^41024true2^101073741824true2^30int 内最大的 2 的幂0false不是正数-1false负数-1024false负数3false质数除 2 之外还有其他因子12false12 2^2 * 32147483647falseint 最大值明显不是 2 的幂特别强调 1 和 0。1 这个用例能检查你是不是漏了“2 的 0 次方也算”的前提0 专门用来考验位运算版本是否写了n 0。我早期直接把return (n (n - 1)) 0交上去0 被误判为 true在线评测平台直接给我标红。3.2 从第一版到最终版的实际提交过程我的习惯是先用循环除法拿到一个稳定答案再改写成位运算。第一版提交通过之后我又试了递归写法public boolean isPowerOfTwo(int n) { if (n 0) return false; if (n 1) return true; if (n % 2 1) return false; return isPowerOfTwo(n / 2); }递归整体上是循环除法的翻版优点是代码语义更接近数学定义。对于 int 来说最多递归 31 层完全不会爆栈换成 long 也只有 64 层。递归唯一的额外开销是函数调用但在这个量级上可以忽略。面试时偶尔拿出来说一嘴能体现你对递归和循环本质关系的理解。最后再改成位运算版本。三次提交在评测平台上成绩相差无几因为测试数据量不足以拉开差距。但在真实工程里比如一次要判断一亿个随机数循环除以 2 的除法和移位指令耗时就会明显暴露出来。所以位运算版本仍然是我最终会采用的版本。3.3 多语言实现与类型差异同一套位运算逻辑在主流语言里差别不大。Java 的 int 是 32 位有符号整数负数按补码处理C 的 int 也几乎总是 32 位行为与 Java 一致。Python 的 int 没有固定位数位运算依然适用但是n 0的条件依然不能省。Python 版本def is_power_of_two(n: int) - bool: return n 0 and (n (n - 1)) 0这段代码的底层逻辑完全等价于 Java 版本。因为位运算判断 2 的幂不是语言特性而是二进制世界的基本规则。唯一区别是 Python 没有整数溢出所以你可以传入任意较大的整数只要它是 2 的幂结果依然是 true。4. 实战排雷负数、0 与溢出相关的常见坑这一节是我最想写的内容。因为位运算版本代码很短很多人看似懂了却在提交时连续翻车。问题通常不在主逻辑而在边界条件。4.1 负数为什么会被位运算误判负数不是 2 的幂这是数学结论。但在 Java / C 这类有符号整型里负数按补码存储补码的按位与会造成假阳性。最典型的例子是Integer.MIN_VALUE它的二进制是1000...000也就是只有最高位是 1。而Integer.MIN_VALUE - 1会溢出变成0111...111两者按位与的结果是 0。也就是说如果代码写return (n (n - 1)) 0Integer.MIN_VALUE会被误判为 true。这是彻底的错误。加上n 0之后所有负数在第一关就被拦截。所以位运算版本绝不能省掉这个条件。顺带一提负数的二进制表示非常反直觉-1的所有位都是 1。很多初学者以为负数在内存里只是把最高位变成 1实际远不止如此。搞懂补码再回头理解这道题会轻松很多。4.2 做溢出操作时的典型事故另一个坑发生在生成 2 的幂列表时。int 能表示的最大 2 的幂是 2^30如果继续乘 2得到 2^31它会溢出成负数。我见过有人写循环生成 32 个 2 的幂结果最后一个变成负数long v 1; for (int i 0; i 32; i) { int x (int) v; // 第 32 次时溢出 v 1; }解决办法很简单要么用 long 存要么循环只跑到 30。遇到“位数有限”的题目心里要始终装着一个边界32 位有符号整数里2 的幂最大是 2^30。这个边界意识会伴随你处理很多位运算题。4.3 常见错误速查表错误写法错误现象根因与修正return (n (n - 1)) 00 被误判为 true没有排除 n 0把n 0写成n 1n 1 返回 false1 是 2^0必须允许循环除法不加奇数判断非 2 幂数字也会走到最后需要先判n % 2 ! 0用Math.log(n) / Math.log(2)个别大数误判浮点精度不可控不要用浮点判断整数幂循环生成 32 个 2 的幂2^31 溢出成负数只到 2^30 或改用 long直接判断 n 2n 4这张表建议直接收藏。很多看起来诡异的问题到最后查下来都不是思路问题而是边界和溢出问题。写任何与整数相关的题目时把 0、负数、最大值、最小值放进测试列表基本能避开九成事故。5. 延伸从 2 的幂到通用位运算技巧做题不能只停留在通过一个测试点。这道题真正有价值的地方在于n (n - 1)这个操作可以迁移到很多其他场景。我在这里展开几个常用变体。5.1 n (n - 1) 到底在做什么n (n - 1)的本质是“把最低位的 1 清零”。这个操作在二进制算法里出场率极高。最常见的应用是统计二进制中 1 的个数int countOnes(int n) { int count 0; while (n ! 0) { count; n (n - 1); } return count; }每次循环消掉一个 1循环次数等于二进制中 1 的个数而不是逐位遍历 32 位。这个技巧能直接把统计时间复杂度从 O(位数) 降到 O(1 的个数)在很多高频场景里有效。另一个变体是判断 4 的幂。先确认它是 2 的幂再检查唯一的那个 1 是否落在偶数位。比如 n 与0x55555555按位与结果不为 0 就说明它在奇数位上对应 4 的幂。这些都是同一道题发散出来的技巧所以“2 的幂”确实是位运算入门的最佳例题。5.2 位运算能力在真实项目中的体现别觉得这些只会出现在笔试里。实际工程里 2 的幂无处不在哈希表扩容后容量往往设计成 2 的幂这样计算桶下标可以用(hash (capacity - 1))代替取模性能更高内存分配器按 2 的幂对齐纹理尺寸、音视频缓冲区块大小也经常要求是 2 的幂。我举个具体例子“把任意数向上取整到最近的 2 的幂”有这样一种经典写法int roundUp(int n) { n--; n | n 1; n | n 2; n | n 4; n | n 8; n | n 16; return n 1; }它把从最高位 1 向下的所有低位全部置为 1再整体加 1 进位成一个新的 2 的幂。理解了 2 的幂的二进制特征再看这种代码会非常舒服。这也是为什么我一直建议初学者认真对待简单题简单题背后的二进制直觉会在复杂工程里反复出现。5.3 我在刷完这道题之后养成的习惯实际带题时我发现大多数人第一次提交位运算都栽在n 0这个条件上。这件事让我反思了很久一道题目再简单边界条件的处理仍然能拉开差距。后来我固定了一个习惯任何与整数、位运算相关的题先把 0、负数、最大值、最小值写进测试用例再开始写主逻辑。这个习惯帮我省下了很多无谓的提交失败。如果你刚开始接触这类题我的建议是每个解法都自己写一遍而不是只抄答案。写完以后再试着把循环除法改成递归把递归改成位运算看能否独立推导出return n 0 (n (n - 1)) 0这一行。能推导出来才算真正完成了从“除法”到“位运算”的思维跃迁。