今天的挑战出现在第 45 天清单里的时候，我第一反应是：这题是不是混进来的？“实现一个算法确定数字 N 是否为 2 的幂，是则输出 YES，否则输出 NO”，怎么看都像入门题库第一页的东西。但真正坐下来写，把边界条件、位运算原理、不同语言的行为差异全部过一遍之后，我才发现这道题的水远比看上去深。它几乎是一道能同时检验数学直觉、位运算熟练度和测试用例设计能力的综合题，值得拿出来单独写一篇文章。
这篇文章就把我从拿到题目到最终验证的整个过程写清楚，包括为什么会从最普通的循环解法一路演化到位运算解法、各个版本的代码长什么样、测试时最容易踩的坑在哪里，以及面试官最喜欢围绕这道题做的几个变体。给正在刷题的朋友、准备面试的朋友、还有像我一样搞每日挑战自我驱动的人一个参考。
1. 把题目真正拆开之后，才发现要求里全是细节
1.1 题目到底在要求什么
“实现一个算法”这个描述其实非常宽泛。没有限定编程语言，没有限定输入范围，也没有限定时间复杂度和空间复杂度，唯一明确的是输出格式：是 2 的幂就输出 YES，否则输出 NO。
这里立刻带出一个很实际的问题：N 的取值范围决定了你能用哪些解法。如果 N 被限定在 32 位整数范围内，比如常见的 int 类型，那么位运算和循环取余都可以正常工作，区别只在于效率和代码优雅程度。如果 N 可能是任意大的整数，比如 Python 的大整数类型，那就要重新审视浮点数对数法，也要注意某些看似聪明的技巧是否能覆盖到那个数量级。
我一开始没太在意输入范围，直接默认按 32 位整数去写。后来测试到超过 int 上限的用例时，才意识到自己在起点就漏了一个关键假设。所以写这类题之前，先问自己一句：我要写的这个函数，输入到底是什么类型？这个问题通常比算法本身更决定成败。
1.2 我初看答案时踩过的几个“想当然”
第一，我以为输出格式写成 yes/no 也能过。但题目里写得很清楚，YES 和 NO 全大写。在线判题系统对大小写非常严格，一旦不一致就直接 WA，没有解释机会。这个细节看起来小，但真的会让你的代码“莫名其妙”地失败。
第二，我以为只有正整数才需要判断。实际上，测试数据很可能把 0、1、负数、INT_MAX、INT_MIN 全部塞进来。如果按“不断除以 2”的思路写，0 会陷入死循环；如果按位运算而无视符号位，负数又会被误判成 2 的幂。这些边界组合起来，能让一个表面正确的解法崩得体无完肤。
第三，我一开始完全没有考虑 N=1 这个特殊情况。数学定义里，1 等于 2 的 0 次方，所以它应该输出 YES。但第一版循环代码很容易因为循环条件写错，把 1 判断成 NO。后来我把边界用例一条条手工跑过，才算真正理解为什么这道题能出现在第 45 天——它是在用题目本身教你：读题永远先于写码。
2. 从“不断除以 2”到“一眼看穿二进制”，关键突破在哪
2.1 数学定义先行：两条看似自然的路都有隐患
判断一个数是否为 2 的幂，最直接的数学定义是：存在某个整数 k，使得 N 等于 2 的 k 次方。顺着这个定义，最容易想到两条路。
第一条路是循环除法：从 N 开始反复除以 2，看最后能不能除到 1。这个方法直观，但问题也很明显。N 为 0 时循环会无限进行；N 为负数时符号会把整个判断搅浑。第二条路是用对数：计算 log2(N)，然后判断它是否为整数。这条路看起来优雅，却隐藏着浮点数精度问题。当 N 很大时，log2(N) 的结果可能因为舍入误差变成 52.99999999999999 这样的值，直接判断是否等于整数就会得出错误结论。我见过不少人在评论区争论对数法到底可不可用，其实核心就是一句：在数学上正确，在计算机的浮点数体系里不一定正确。
2.2 二进制表示的惊人规律：2 的幂永远只有一个“1”
真正让这道题变成经典题目的，是数据在计算机里的二进制表示。2 的任何整数次幂写成二进制，永远是 1 后面跟着一串 0：2 是 10，4 是 100，8 是 1000，16 是 10000。换句话说，2 的幂在二进制中的特征只有一个：恰好有一个位上是 1，其余全是 0。
我最早学到这一条时，觉得它不过是解题技巧。后来在实际项目里做音频采样率判断时，发现常见的采样率比如 8000、16000、44100 并非全部都是 2 的幂，但设备的缓冲大小却经常被设计成 2 的幂，这时候判断缓冲区大小是否合法，一下子就从循环变成了按位与，效率提升了，代码也短了很多。位运算不是炫技，它是对底层存储规律的高效利用。
2.3 n & (n-1) 是怎么被推到眼前的
由“唯一的一个 1”这个特征，自然会想到一个问题：如果把这个 1 消掉，整个数应当变成 0。那么，怎样才能消掉最低位的那个 1？答案是减 1。当你对 n 做减 1 操作时，最低位那个 1 会变成 0，而它右边的所有 0 都会变成 1。
举个例子，n=8 时，二进制是 1000，n-1=7，二进制是 0111，两者按位与得到 0000。再试一个普通数，n=6，二进制是 0110，n-1=5，二进制是 0101，两者按位与得到 0100，不为 0。所以判断条件就浮出水面了：n 大于 0，并且 n 与 (n-1) 按位与的结果为 0。
我第一次看懂这个写法时，确实有一种“原来还能这样”的震动。它把一次完整的循环压缩成了一步减法和一步按位与，整个判断过程不再依赖 N 的位数。这个式子后来在很多场景里反复出现，包括状态机判断、内存对齐检测、哈希表容量调整，是值得刻进肌肉记忆的位运算之一。
3. 几种解法逐一落地：从最朴素到最精巧
3.1 循环取余法：被低估的稳定方案
先写最直观的版本。假设 N 是正整数，反复对 2 取余，如果某一步出现了非 0 余数，就一定不是 2 的幂；如果一路余数都是 0，最后能缩到 1，就说明是。Python 版本如下：
def is_power_of_two(n): if n <= 0: return False while n > 1: if n % 2 != 0: return False n //= 2 return True这段代码的时间复杂度是 O(log n)，空间复杂度是 O(1)。对于 32 位整数，最多循环约 31 次，实际运行完全够用。它的优点是足够直白，边界条件也好控制，几乎不可能因为位运算的隐形规则出错。
说它被低估，是因为很多人觉得这样的解法“不够高级”。但实际上，在面试里先给出这个版本，再进一步优化到位运算版本，恰恰是被面试官欣赏的答题节奏。第一个版本展示了你理解问题，优化版本才展示出你理解计算机。
这里有个细节值得单独提。循环条件我写的是 n > 1，不是 n > 0。如果写成 n > 0，那么 n=1 时循环依然进入，1 对 2 取余得 1，接着被整除为 0，最终错误地输出 NO。我在第一次提交时就踩了这个坑，印象极其深刻。
3.2 位运算核心解法：一行代码解决战斗
真正的重头戏是这个版本：
def is_power_of_two(n): return n > 0 and (n & (n - 1)) == 0整个判断逻辑浓缩成一行。n > 0 用来过滤掉 0 和负数，因为没有这个条件时，负数可能因为补码特征被误判；(n & (n - 1)) == 0 则承担真正的核心判断。
在 C/C++ 里可以写成分离的布尔表达式，Java 里则要注意入参类型。如果是 int，那么 int 的最小值 -2147483648 是一个极度微妙的用例。它在二进制补码表示里是 10000000000000000000000000000000，看起来只有一个位是 1，直接用位运算判断会把它误判为 YES，但它是负数，所以必须靠 n > 0 拦下。这个坑我在后面测试部分会专门展开来说。
3.3 等价变体：n & (-n) 与库函数思路
除了 n & (n - 1)，还有一个等价写法是 n & (-n)。对于正整数 n，n & (-n) 可以提取出二进制中最低位的那个 1。如果 n 本身就是 2 的幂，最低位的 1 就是唯一一个 1，提取结果会等于 n 本身。于是判断条件变成：
def is_power_of_two(n): return n > 0 and (n & -n) == n这个写法与第一个位运算版本效率相当，但理解成本略高，因为它依赖补码表示的知识。如果你不清楚补码下正负数之间的运算关系，很容易被这里的 -n 绕晕。
库函数方案同样值得讨论。Java 中 Integer.bitCount(n) 可以直接数出二进制 1 的个数，如果 n 大于 0 且 1 的个数恰好为 1，同样可以判定。Python 里可以用 bin(n).count('1')，写成这样：
def is_power_of_two(n): return n > 0 and bin(n).count('1') == 1这种方案可读性非常好，但底层会遍历所有二进制位，性能上和直接位运算不在一个量级。对于刷题来说，写出这段没问题；对于一个需要高频调用的底层模块来说，我更推荐 n & (n - 1)。我在实际项目里做缓冲对齐判断时，用的就是位运算版本，因为那个函数每秒钟可能被调用上万次，每多一次循环都是肉眼可见的浪费。
3.4 几种方案横向对比：选型要看场景
对我自己写过的几个版本，我做了一张对比表。这张表不是为了分出谁优谁劣，而是提示在不同场景下应该选谁。
| 方案 | 时间复杂度 | 空间复杂度 | 优点 | 风险点 |
|---|---|---|---|---|
| 循环取余 | O(log n) | O(1) | 直观，边界好推导 | 循环次数较多，代码长 |
| n & (n-1) | O(1) | O(1) | 最快，代码最短 | 容易漏掉 n > 0 条件 |
| n & (-n) | O(1) | O(1) | 同量级性能，适合讲补码原理 | 理解门槛高 |
| bitCount/bin 计数 | O(位数) | O(1) | 可读性最好 | 依赖语言库函数，性能略低 |
面试场景下，我最推荐的做法是：先给出数学定义，再说“2 的幂的二进制只有一个 1”，然后落到位运算写法，同时主动解释 n > 0 的作用。这样能给考官传递一个明确的信号：你不是背过答案，而是真正理解了这条式子怎么来的。
4. 边界值不是刁难，是这道题真正的考点
4.1 从 0 到 INT_MIN：每一个边界都要亲自跑
这部分我认为是整道题最精华的部分。先列一份必测清单：0、1、2、3、16、31、32、100、INT_MAX、INT_MIN。每个值背后的逻辑都不同。
0 不是 2 的幂，应输出 NO。所有只写 while n % 2 == 0 而没有前置判断的代码，都会在这里陷入死循环，因为 0 对 2 取余恒为 0，永远无法退出。
1 是 2 的 0 次方，按数学定义应输出 YES。这是很多人漏掉的用例，也是区分“理解定义”与“背写法”的试金石。
2 的二进制是 10，满足位运算条件，输出 YES。3 的二进制是 11，不满足，输出 NO。16 的二进制是 10000，输出 YES。31 的二进制是 11111，连续五个 1，明显不满足，输出 NO。32 的二进制是 100000，输出 YES。100 的二进制是 1100100，中间的 1 不止一个，输出 NO。
INT_MAX 的二进制是 01111111111111111111111111111111，它不是 2 的幂，输出 NO。这里的意义是测试大数场景中位运算和循环是否都能正常工作。
INT_MIN 的情况最刺激。它的补码是 10000000000000000000000000000000，恰好只有一个位是 1，因此不太严谨的位运算判断会给出 YES。但如果从数学定义出发，一个负数显然不可能是 2 的幂，正确输出是 NO。这两个结论的冲突，恰好说明 n > 0 这个前置条件不是可有可无的摆设。
4.2 把测试用例写成代码：可持续复用的检查清单
手工逐个验证只能保证当时没错，要想更系统地检查，应该把测试用例直接固化成代码。用 Python 写最方便，一段断言式的循环就能搞定：
test_cases = [ (0, False), (1, True), (2, True), (3, False), (4, True), (5, False), (6, False), (8, True), (9, False), (15, False), (16, True), (17, False), (31, False), (32, True), (100, False), (1024, True), (1025, False), ] for n, expected in test_cases: result = is_power_of_two(n) assert result == expected, f"FAIL: n={n}, expected={expected}, got={result}" print("All tests passed.")这段测试覆盖了 0、1、2、3、常见边界、误判高危数字、2 的整数次幂以及相邻数字。测试全部通过，也只能说明这些用例没问题。更稳妥的做法是再加一段“对拍”测试：用一个绝对正确但很慢的循环解法作为基准，把 1 到 10000 的所有数字都跑一遍，让两个函数对每个数字的输出保持一致。我在第 45 天的时候就用这个办法，一次性抓出了两个自己以为没事的边界错误。
4.3 我在这道题上真正踩到的溢出坑
我是实际写过一段错误代码的人，体会特别深。当时用 Java 写，本地调试时传入 int n = -2147483648，函数返回了 true，我心里直接冒出一句“这怎么可能”。
查了好一会儿才发现，INT_MIN 的补码只有一个位是 1，所以 (n & (n - 1)) 的结果确实是 0，单看位运算它完全满足条件。但负数不可能通过“2 的幂”这种在整数范围内定义的概念判定。我的代码最初只写了 return (n & (n - 1)) == 0 而没有加 n > 0，所以在负数边界上翻了车。
加上 n > 0 之后，这条用例才恢复正常。这个经历让我真切理解了为什么所有位运算写法都要求先判断正数：不是风格问题，是正确性问题。
5. 把这道题讲透之后，面试官还喜欢怎么变式追问
5.1 变体一：判断 N 是否为 4 的幂
最常见的变体是判断 N 是否为 4 的幂。4 的幂在二进制里同样只有一个 1，但这个 1 只能出现在二进制位的偶数位置，也就是第 0、2、4、6 位等等。所以除了判断 n & (n - 1) == 0 之外，还要额外确认唯一的那个 1 落在偶数位置上。
一种经典做法是引入一个掩码，比如 32 位环境下的 0x55555555，也就是二进制的 0101010101010101 序列。如果一个数是 2 的幂但唯一的 1 不在掩码为 1 的位上，它就不可能是 4 的幂。这个变体的核心依然是对二进制结构的理解，而不是死记某个公式。只要能画出二进制位图，当场推导出解法并不难。
5.2 变体二：统计二进制中 1 的个数
把判断条件反过来，题目就变成“二进制里是否恰好只有一个 1”，再延伸一步就是统计二进制中到底有多少个 1。这里会引出经典的 Brian Kernighan 算法，它本质上就是不断用 n & (n - 1) 消掉最低位的 1，每消一次计数加一，直到 n 变为 0，循环次数等于 1 的个数，而不是二进制位数。
我在一次模拟项目里真的遇到过类似场景：需要快速判断某个配置字段启用了多少个独立功能位，当时第一个想到的方案是遍历每一位再累加，后来重构成每次消除最低位 1 的写法，代码变短了，耗时也明显降了下来。这类问题在底层代码优化里非常常见，多花一点时间理解位运算，回报周期可能比想象中短得多。
5.3 更深一层：位运算不是炫技，而是对数据底层的尊重
把原题和几个变体串起来看，真正有用的不是那几行代码，而是一种思维习惯：看到一个数字时，能不能主动从二进制表示的角度去想问题。
不少刷题的人把这类题目当作“位运算技巧”直接背下来，刷完就忘。但实际做项目时会发现，位运算之所以频繁出现在高性能代码中，是因为它能把“需要循环很多次”的情况压缩成 O(1) 的常数时间操作，能把一段复杂的条件判断浓缩成一行可静态推导的表达式。这种能力没法靠背题获得，只能靠一次次亲手推导、亲手踩坑、亲手验证来积累。
我自己在写完这道题之后，没有急着进入第 46 天，而是把判断 4 的幂、统计 1 的个数、找出最低位 1 这几个变体全部重新实现了一遍，然后又故意在几个函数里埋下不同的错误版本，再用测试把它们挨个抓出来。这个“主动写 bug、再抓 bug”的训练方式看起来有些自虐，但对巩固边界条件和位运算原理特别有效。如果你也想真正吃透这道题，推荐亲自把 0、1、负数、INT_MIN、大整数以及浮点对数的精度问题全部跑一遍，这比看任何人的代码一百遍都更让人放心。
