★ FEATURED ARTICLE 1. 第一眼看到“2 的幂”循环除以2的思路和它藏着的细节老读者都知道我对算法题的套路一向是“先暴力、再优化、最后聊聊题外话”。这次要聊的是一道几乎每个刷题人都见过的题目判断一个给定的整数 n 是否为 2 的幂。题目描述很短短到很多人觉得“这有什么好写的”。但当我实际刷题、面试、甚至写业务代码时围绕“2 的幂”翻车的次数远比想象中多。比如有人用浮点数对数判断结果在某个边界用例上挂了有人写循环除 2结果因为 0 的处理不当直接死循环还有人搞不清楚负数在二进制里是怎么回事上来就位运算结果自己的判断逻辑漏洞百出。先说清楚题目到底要求什么给定一个整数 n判断它是否满足存在一个非负整数 x使得 n 等于 2 的 x 次方。这里要注意“2 的幂”通常约定为 2^0 1 开始算也就是 1、2、4、8、16……都在范围内。0 不是负数不是小数也不是。我见过不少人的第一反应是用一个循环把 n 不断除以 2最后判断是否等于 1。这个思路完全正确也是题目的“送分”解法。但真正落实到代码里有几个细节值得掰开说。1.1 循环实现的第一个坑0 的无限循环先看最常见的错误写法public boolean isPowerOfTwo(int n) { while (n % 2 0) { n / 2; } return n 1; }这段代码看着很清爽但当 n 0 时0 % 2 0 恒成立n / 2 永远等于 0程序就陷入了死循环。这个坑其实暴露了一个本质问题0 在“能否被 2 整除”这件事上和 2 的幂有着完全相同的表现0 可以被 2 整除任意多次最后“除以 2”之后仍然是 0根本得不到 1。所以任何用“累除校验”思路写出来的解法都必须先单独处理 n 0 的情况。我最推荐的循环写法是public boolean isPowerOfTwo(int n) { if (n 0) { return false; } while (n 1) { if (n % 2 ! 0) { return false; } n / 2; } return true; }这段代码的思路是只要 n 还大于 1就必须保证它是偶数否则立刻返回 false除到最后如果只剩 1说明 n 从一开始就一直是 2 的倍数也就是 2 的幂。时间复杂度的量级是 O(log n)因为 n 每次除以 2循环次数大约等于 n 的二进制位数。这个复杂度本身完全合格毕竟 int 范围内的 n 最多也就循环 31 次。但如果你追求更极致的实现或者说想在面试官面前展示出对二进制本质的理解就得往位运算的方向走了。1.2 为什么“除以 2”的思路能解释通但不够优雅从数学层面看“n 不断除以 2最后得到 1”是 2 的幂的定义式完全没有问题。但从计算机层面看这个思路绕了一段路2 的幂在二进制表示里的特征极其显眼根本没有必要做除法。举个例子。10 进制里我们判断一个数是不是 10 的幂比如 10、100、1000特征是什么是“1 后面跟了一串 0”。二进制里判断 2 的幂也一样2 的幂的二进制形式就是“一个 1 后面跟了一串 0”。1 2^0二进制是 00012 2^1二进制是 00104 2^2二进制是 01008 2^3二进制是 1000看到这里题目就从一个“数学除法问题”变成了一个“二进制特征识别问题”。而识别二进制特征最趁手的工具自然是位运算。这就是我接下来说的重点。2. 位运算一行判定的原理n (n-1) 与 n (-n) 的拆解位运算解法是这道题的标准答案在很多题解里你都会看到这样一行return n 0 (n (n - 1)) 0;或者是return n 0 (n -n) n;第一次看到这两种写法的人大概率是“会抄但不懂”。我问过不止一个刚入门的朋友为什么 n (n-1) 等于 0 就说明 n 是 2 的幂他们的回答往往是“背下来的”。我不想让你背结论所以这一节我会把这两个式子的原理拆到骨头里顺便告诉你它们背后隐藏的编程思想。2.1 从“1000”和“0111”看 n (n-1) 在做什么先直接给结论n (n-1) 的作用是把 n 的二进制表示中最低位的那个 1 变成 0。这个结论很多人听说过但未必知道为什么。我们拿一个具体的例子来走一遍。n 8二进制是 1000。n - 1 7二进制是 0111。两者做按位与1000 0111 ------ 0000结果是 0。再看一个不是 2 的幂的数n 6二进制是 0110。n - 1 5二进制是 0101。两者做按位与0110 0101 ------ 0100结果是 4不是 0。为什么会有这样的差别关键在于 n-1 的二进制变化规律。任意正整数 n它的二进制表示中最低位的 1 的位置我们记为 k。那么 n-1 的二进制恰好是在第 k 位变成 0而第 k 位右边的所有位从 0 变成 1第 k 位左边的位保持不变。举个例子。n 12二进制 1100。最低位的 1 在第三位从右往左数下标从 0 开始的话是第 2 位也就是那个“1100”里的第三个数字。n-1 11二进制 1011。对比一下1100 和 1011第 k 位从 1 变 0右边的两个 0 全变 1左边的 1 保持不变。当 n 的二进制表示里只有一个 1 时n-1 会让这个唯一的 1 变成 0其他位全是 1按位与的结果自然是 0。反过来如果 n 的二进制表示里至少有两个 1n (n-1) 只会消掉最低位的那个 1剩下高位的 1 依然存在结果就不可能是 0。所以n 0 (n (n-1)) 0这个判断本质上是说这个正整数的二进制表示里恰好只有一个 1。这种“消掉最低位 1”的操作在很多算法里都有应用场景。比如统计一个数的二进制里有多少个 1Brian Kernighan 算法只要不断执行 n (n-1)每次消掉一个 1统计操作次数就能得到 1 的个数。这道题的位运算解法本质上就是 Kernighan 算法思想的一个特殊应用场景。2.2 再看 n (-n)提取最低位的 1第二种写法n 0 (n -n) n是一个更“对称”的思路。先明确一件事在计算机里负数是以补码形式存储的。一个数 n 的相反数 -n 的补码等于 n 按位取反再加 1。这个规则带来的一个漂亮结果是n (-n) 恰好能提取出 n 的最低位的 1其余位全部变 0。还是拿 8 来举例。n 8二进制 1000。-8 的补码是多少8 的二进制是 0000...1000取反是 1111...0111加 1 得到 1111...1000。换句话说-8 的有效二进制部分还是 1000只是前面补了无数个 1。二者做按位与0000...1000 1111...1000 -------------- 0000...1000结果是 8正好等于 n。再看 n 6。6 的二进制是 0110。-6 的补码是 1010按位取反 1001加 1 得到 1010。按位与0110 1010 ------ 0010结果是 2不等于 6。所以n -n n的意思是这个数最低位的 1 提取出来之后恰好等于它本身。什么情况下最低位的 1 等于自己只有一种情况就是 n 的二进制里只有这一位是 1其他位全是 0。这不就是 2 的幂吗两种位运算写法一个从“消除低位 1”切入一个从“提取低位 1”切入殊途同归。2.3 位运算解法的时间复杂度为什么是 O(1)循环除法是 O(log n)位运算为什么能到 O(1)原因很简单位运算是在 CPU 层面直接对二进制位进行的与、或、非、移位操作。不管 n 是 8 还是 2147483648n (n-1)都只需要一条机器指令运算时间与 n 的大小无关。这一点在单次调用场景下看起来差别不大但如果是在一个大规模循环里判断“哪些数是 2 的幂”O(1) 与 O(log n) 的差距就会被放大出来。这也是我在实际开发中坚持用位运算的原因之一不是因为它显得高深而是它在高频重复场景下真的能省下时间。3. 边界条件最容翻车负数、零、1、溢出和语言差异算法题难的不是主路径而是边边角角的边界条件。判断 2 的幂这道题边界条件翻车率极高几乎每个版本的语言实现都有自己的坑。我按自己实际踩过的顺序逐个说。3.1 负数为什么直接 false补码会带来什么假象很多人写完位运算解法后会随手测一下 -8发现-8 (-8-1)结果居然是 0。于是开始怀疑人生难道 -8 也是 2 的幂这不是你算错了而是你对位运算作用于负数时的语义理解需要修正。-8 的二进制在补码表示下是 1111...1000。-8 - 1 -9补码是 1111...0111。两者做按位与1111...1000 1111...0111 -------------- 1111...1000结果是 -8等等这不等于 0。我上面说的“结果是 0”来自一个常见的误算——有人拿来算的是 -8 和 -7。不管怎样重点在于负数在补码体系下高位全是 1n (n-1) 根本不满足“只有一个 1”的语义因为负数的二进制高位有无数个 1。所以在所有解法里第一道防线永远是n 0。条件不满足直接返回 false。这个判断不只是“把负数排除”它还把 0 也排除了。你可能会问0 的二进制全是 00 (0-1) 等于 0位运算结果确实等于 0那不就会误判吗对这就是为什么我说“n 0”不是可选项而是必须项。0 和 2 的幂在位运算层面都会得到同样的结果唯一的区分就是它不大于 0。把所有位运算解法都套上 n 0 这个前置条件本质上就是为了解决这个数学上的例外。3.2 1 是 2 的幂吗指数为 0 的情况要单独记1 是这道题最容易出错的第二个点。有人会条件反射地认为“幂”至少是 2 的一次方于是把 1 判为 false。但根据题目定义2 的 0 次方等于 1所以 1 确实属于 2 的幂。好消息是无论你用哪种解法1 都会被自然处理循环除法n 1 时根本进不了 while 循环最后直接返回 true。n (n-1)1 0 0返回 true。n -n1 -1 1返回 true。所以你不需要为 1 写特殊逻辑但你要清楚“1 是正确答案”别在面试时被问一句“1 算不算”就卡住。这个问题的标准答案是如果题目没有特别说明 2 的幂从 2 的 1 次方开始那么默认 2^0 1 算。3.3 溢出的坑为什么有人用循环乘法会翻车还有一个常见的思路是用一个变量不断乘 2看能不能刚好等于 n。类似这样public boolean isPowerOfTwo(int n) { int power 1; while (power n) { power * 2; } return power n; }这段代码在大多数情况下是正确的但有一个隐患当 n 是一个很大的非 2 的幂数比如 2147483647power 会一直乘到 1073741824再乘一次就变成了 -2147483648。这是因为 int 类型的乘法溢出最高位进位后数值直接变成负数这时候 power n 依然成立于是进入死循环。解决方式有两种一是把 power 声明为 long二是干脆别用乘法别人的解法都是除法或位运算就是因为整数乘法溢出太容易踩。我亲眼见过不止一个同学在现场写这段代码然后卡在边界用例上找不出原因。如果你真要写“不断乘 2”的版本务必加上 long 类型保护并且在乘之前判断一下 power n / 2。3.4 不同语言的隐藏差异JS 位运算只处理 32 位、Python 的整数无上限、Java 的 int 不对称这题在不同语言里的坑还不一样这一点很多人没意识到。JavaScript 里n (n-1)这种位运算会把 n 先转成 32 位有符号整数再计算然后再转回 Number。也就是说当 n 超过 2^31-1 时位运算结果可能和你预期的不一样。所以你用 JS 写这题时如果测试用例里出现了特别大的整数需要小心处理。Python 则没有这个烦恼。Python 的整数是任意精度的位运算天然支持任意大的数。所以在 LeetCode 上用 Python 写n 0 and (n (n-1)) 0对所有合法整数都成立非常省心。Java 的坑在于 int 的不对称。int 取值范围是 -2147483648 到 2147483647最大正数是 2^31-1但最小负数是 -2^31。也就是说-n在 n -2147483648 时正数部分 2147483648 超出了 int 范围会发生溢出结果还是 -2147483648。这会导致n -n n在 n 为负的时候可能出现奇怪的相等现象。解决办法还是一样先把 n 0 的判断放在前面利用短路逻辑让后面的位运算根本没机会执行。4. 四种主流解法横向对比从代码到性能的完整实现说完了原理和边界条件我把这道题的主流解法整理成了一张表然后给出我实际写过的几个版本代码。解法核心逻辑时间复杂度空间复杂度是否推荐循环除 2不断除以 2判断最终结果是否为 1O(log n)O(1)推荐思路清晰n (n-1)判断二进制中是否只有一个 1O(1)O(1)最推荐标准答案n -n提取最低位 1 后与原数比较O(1)O(1)推荐原理直观内置函数/对数法bitCount 或 Math.log 计算结果O(1)O(1)不推荐有坑见下文4.1 完整代码实现Java / Python / CJava 版本// 解法一循环除法 public boolean isPowerOfTwo(int n) { if (n 0) return false; while (n % 2 0) { n / 2; } return n 1; } // 解法二位运算 n (n-1) public boolean isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; } // 解法三位运算 n -n public boolean isPowerOfTwo(int n) { return n 0 (n -n) n; }Python 版本# 解法一循环除法 def is_power_of_two(n: int) - bool: if n 0: return False while n % 2 0: n // 2 return n 1 # 解法二位运算 n (n-1) def is_power_of_two(n: int) - bool: return n 0 and (n (n - 1)) 0 # 解法三位运算 n -n def is_power_of_two(n: int) - bool: return n 0 and (n -n) nC 版本 与 Java 几乎一致需要注意 int 溢出问题class Solution { public: bool isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; } };4.2 为什么我不推荐对数法浮点误差的真实案例还有一种解法是把 n 取以 2 为底的对数判断结果是否为整数public boolean isPowerOfTwo(int n) { return n 0 (Math.log(n) / Math.log(2)) % 1 0; }理论上讲得通但实际测试时就容易出问题。我印象里有一次测试 n 536870912即 2 的 29 次方用 Java 的 Math.log 计算结果居然不是整数浮点数误差导致判断失败。这是因为对数运算本身是近似的指数越大误差越明显。所以我的态度很明确能用位运算解决的问题不要用浮点数。这条经验后来帮我在很多类似的题目里避开了坑。4.3 工程视角可读性和性能之间的权衡刷题时位运算无疑是最优解但在实际业务代码里我会稍微犹豫一下。return n 0 (n (n-1)) 0;这行代码简短高效但可读性确实不算高。它要求读者至少知道“n (n-1) 会清除最低位的 1”这个知识点。如果你的团队里有人不熟悉位运算review 时会比较费劲。所以我一般是这样权衡的如果这段代码在热点路径上比如每秒被调用成千上万次那必须用位运算如果是普通业务逻辑我更倾向于写一个带注释的循环版本或者封装成工具方法并写上注释。算法题的“最优解”和工程里的“最合适解”是两码事这个区分很重要。5. 从“2 的幂”延伸出去的经典变体3 的幂、4 的幂与位运算思维一道经典题之所以经典不只是它本身有价值更因为它能延伸出好多变体。判断 2 的幂这道题往往不是单独出现的它会自然引出“3 的幂”“4 的幂”这样的兄弟姐妹问题。我在这里顺带聊聊也是想说明“2 的幂”背后的二进制思维可以复用到哪里。5.1 3 的幂为什么不能简单照搬位运算套路3 的幂没有类似的位运算特性。原因很简单3 在二进制下是 11不是一个“单个 1”它的幂的二进制形式没有统一规律比如 3 是 119 是 100127 是 11011位模式不固定。所以判断 3 的幂通常只能靠循环除法或者用一个数学技巧——因为 int 范围内最大的 3 的幂是 11622614673 的 19 次方所以可以直接写public boolean isPowerOfThree(int n) { return n 0 1162261467 % n 0; }这个解法的原理是如果 n 是 3 的幂而 1162261467 本身是 3 的幂那么 1162261467 一定能被 n 整除。反过来也成立因为 n 如果能整除一个只包含质因子 3 的数且 n 是正整数那么 n 的质因子也只能是 3所以 n 也是 3 的幂。这个思路很干净但它只能用在限定整数范围内不适合任意大整数。这也是“2 的幂”题目的独特之处它因为二进制的天然特性拥有独一无二的位运算解法而 3 的幂就只能“靠数学取巧”或者循环。5.2 4 的幂两个位运算条件的组合4 的幂是一个很有意思的中间形态。4 的幂首先一定是 2 的幂所以第一个条件可以直接复用n 0 (n (n-1)) 0。但 4 的幂还多了一个约束它的二进制表示里那个唯一的 1 必须出现在“偶数位”上。你看4 01001 在第 2 位偶数位16 100001 在第 4 位偶数位而 2 00101 在第 1 位奇数位所以 2 不是 4 的幂。怎么判断 1 是否在偶数位用一个掩码 0x55555555它的二进制是 0101 0101 0101 0101...所有偶数位为 1。如果 n 与这个掩码按位与的结果不为 0说明 n 唯一的那个 1 落在偶数位也就是 4 的幂public boolean isPowerOfFour(int n) { return n 0 (n (n - 1)) 0 (n 0x55555555) ! 0; }你看这一段代码就是“2 的幂”解法的一次自然延伸。掌握了二进制思维这类题目从来不是靠死记硬背而是靠模式识别。5.3 位运算思维在工程里的落地场景可能有人会觉得判断 2 的幂除了刷题还能干嘛我自己的经历告诉我这个判断在工程里出现的频率超乎想象。最经典的一个场景是 Java 的 HashMap 扩容。HashMap 在初始化时会根据传入的容量计算出不小于该容量的最小的 2 的幂使用的正是 tableSizeFor 方法。我翻过那段源码里面全是无符号右移和按位或运算本质上就是在玩二进制。还有一个场景是内存分配器。分配器通常会按 2 的幂来对齐内存块比如 8 字节、16 字节、32 字节。判断一个请求的大小是否恰好是某个 2 的幂可以用位运算快速判断从而决定走哪条分配路径。再有就是线程池配置、缓冲区大小计算经常会遇到“向上取整到最近的 2 的幂”这种需求而它的第一步就是先能判断“当前是不是 2 的幂”。我个人在实际开发里最常用到的一次是写一个日志缓存模块时需要把缓冲区容量锁定为 2 的幂以便用位运算代替取模运算来定位数组下标。index hash (capacity - 1)这种写法要求 capacity 必须是 2 的幂。当时我就在工具类里写了一个判断方法用的正是这道题的解体思路。那一刻我才真正理解为什么那么多人说“刷题不是没用而是你暂时没用上”。如果你准备把这题作为面试复习的一部分我建议你不仅背下位运算的写法更要理解n (n-1)为什么能消掉最低位的 1、负数补码在位运算下的表现、以及 int 溢出的边界。这几个知识点比这道题本身值钱得多。等你把 2 的幂吃透了再去看 4 的幂、再看 HashMap 的 tableSizeFor、再看各种基于位运算的工程代码你会发现它们其实是同一件事。
阅读完成 · 觉得有帮助？
