昨天刷题打卡恰好做到 LeetCode 1404，一道标着 Medium 的二进制题：输入一个二进制表示的字符串，按照“奇数加一、偶数除以二”的规则把它减到 1，返回需要的步骤数。让我意外的是，网上不少题解都选择了直接模拟，跑出来的耗时却天差地别——有的甚至接近 100ms，而真正优雅的解法只有几毫秒。这篇文章就把我的完整推导、实测对比和踩坑过程写下来，希望能帮你一次性看穿这道题。

1. 先别急着模拟：读懂题意背后的“除法”逻辑

先把题目规则完整复述一遍。给定一个二进制字符串 s，比如"1101"，每一步你可以执行两种操作之一：

• 如果当前数字是偶数，把它除以 2；
• 如果当前数字是奇数（并且不等于 1），把它加 1。

目标是让数字最终变成"1"，返回这个过程需要的总步数。题目里还补了一句：输入保证没有前导零，也就是说不会出现"0001"这种脏数据。

看到这种题，绝大多数人的第一反应就是照着规则硬模拟：先把字符串转成整数，然后 while 循环里面判断奇偶、做除法、做加法，直到等于 1 为止。这种做法当然是对的，但它恰恰踩中了这道题最想考察的盲区——二进制字符串最长可以有 500 位，Python 的 int 虽然能装下这么大的数，但你每做一次加 1 都可能触发一整条进位链，每做一次右移都要重新处理字符串，整体复杂度会退化得很厉害。

我手算一个例子你感受一下。"1101"从右往左逐位观察：

• 当前是"1101"，最低位是 1，奇数，加 1 变成"1110"；
• 最低位是 0，偶数，右移变成"111"；
• "111"最低位是 1，奇数，加 1 变成"1000"；
• "1000"右移变成"100"；
• "100"右移变成"10"；
• "10"右移变成"1"。

一共 6 步。注意中间的"111"加 1 直接变成"1000"，低位三个 1 同时被进位吞掉。这种“连锁进位”正是朴素模拟最痛苦的地方：每次加 1 都要从最低位一路扫描到最高位，最坏情况下一步就可能消耗 O(n) 的时间，总共 O(n) 步就是 O(n²)。字符串长度 500 的时候虽然不至于超时，但你的代码会变得又慢又难维护，放在面试场景里非常减分。

所以这道题真正的考点根本不是“会不会写 while 循环”，而是你能不能换一个视角：二进制里的除法本质上就是右移，奇偶本质上就是最低位是 1 还是 0，加 1 本质上是一条从低到高的进位链。想通这三件事，解法就完全不一样了。

2. 从 100ms 到 1ms：三种写法的实测对比

2.1 字符串模拟版：最直观，也最容易跑出 100ms

先看我写的第一版，逻辑和题目描述完全一一对应：

def numSteps(s: str) -> int: ans = 0 while s != "1": if s[-1] == "0": s = s[:-1] else: s = bin(int(s, 2) + 1)[2:] ans += 1 return ans

这个写法在长度较小的用例上很清爽，但一旦碰上接近 500 位的二进制串，性能立刻暴露问题。int(s, 2)需要把整个字符串解析成整数，bin(...)又要把整数转回字符串，两次转换都是 O(n) 的操作，再叠加最坏 O(n) 次循环，整体就是 O(n²)。我在本地用随机生成的 500 位二进制串压测，单次调用跑了足足 90 多毫秒，运气差一点就到 100ms 了。你如果是在 LeetCode 上提交也可能会出现 100ms 左右的耗时，这也是标题里那个“耗时 100”的直接来源。

2.2 Python 大整数版：快了很多，但回避了考点

第二版我改成了直接用 Python 的无限精度整数来模拟，不再来回转字符串：

def numSteps(s: str) -> int: x = int(s, 2) ans = 0 while x != 1: if x & 1 == 0: x >>= 1 else: x += 1 ans += 1 return ans

这一版比字符串模拟快不少，因为底层的大整数运算由 C 语言实现，右移一位基本就是常数级操作，加 1 的进位也能高效处理。实测同样 500 位用例，耗时大概在 5~15ms 之间，确实比 100ms 好看多了。但这个写法本质上还是“照着规则一步步走”，没有真正利用二进制结构做批量计算。面试时写出这版，通常只能拿个“能跑通”的评价，面试官追问一句“能不能 O(n) 一遍扫描”你就得现场重新想了。

2.3 线性扫描版：一次遍历，答案直接算

最终我觉得最漂亮的解法，是从右往左扫描字符串，维护一个进位状态carry，直接统计总步数：

class Solution: def numSteps(self, s: str) -> int: ans = 0 carry = 0 n = len(s) for i in range(n - 1, 0, -1): bit = int(s[i]) + carry if bit & 1: ans += 2 carry = 1 else: ans += 1 carry = bit // 2 return ans + carry

这个版本时间复杂度 O(n)，空间复杂度 O(1)，提交后耗时稳定在 0~3ms。和前面 100ms 的版本相比，等于把耗压缩了两个数量级，而核心逻辑反而更短。

三种写法放在一起对比一下：

3. carry 进位扫描的推导全过程

3.1 二进制中的“奇偶”和“除以 2”

这一步是整道题的基石。二进制数的最低位是 1 就是奇数，最低位是 0 就是偶数，这比“转成十进制再% 2”要自然得多。除以 2 在二进制里就是右移一位，"1010"右移变成"101"，数值从 10 变成 5，完全等价。

所以对任意一位来说，它的命运只有两种：

• 它最终会被右移出这个数，也就是被“消耗”掉；
• 它可能作为最高位的 1，被保留到最后。

这个“消耗”过程就是步数的主要来源。而加 1 操作只会在当前数是奇数的瞬间发生，也就是最低位为 1 时。

3.2 从低位向上扫描的三种状态

假设我们从右往左扫描，变量carry表示从更低位传来的进位。因为一次加 1 只可能发生在最低位为 1 的时候，而这个加法的影响会沿着二进制串一路向高位传播，所以扫描时当前位置的“实际值”应该是int(s[i]) + carry，也就是原来的这一位加上低位传上来的进位。这个值只有三种可能：0、1、2。

先看bit为 0 的情况：说明这一位原来就是 0，低位也没有进位传上来。此时整个数在当前位及更低位的组合是偶数，所以我们只需要做一次右移，让这一位被消耗掉，步数加 1，进位保持为 0。

再看bit为 1 的情况：说明这一位实际是 1，整个数现在处于奇数状态。根据题目规则，奇数且不为 1 时，我们要先加 1 再右移。加 1 会把这一位的 1 变成 0，并向更高位产生一个进位，所以消耗 2 步，同时新的进位为 1。

最后是bit为 2 的情况：说明这一位原来是 1，来自低位的进位也是 1。1 + 1 = 2，二进制本位写 0，同时继续向更高位进位 1。但注意，当前这一位实际变成了 0，所以整个数在低位组合起来是偶数，不需要额外的加 1 操作，只需要右移一次，消耗 1 步，进位保持为 1。

把这三条分支整理成表格：

看到这里你应该能理解代码里的if bit & 1:为什么能区分情况了：bit为 1 走奇数分支，bit为 0 或 2 走偶数分支。偶数分支里再用bit // 2取出进位，正好只有 2 的时候进位为 1。

3.3 为什么最高位不需要进循环

很多第一次写这个解法的人会问：为什么循环只到range(n - 1, 0, -1)，而不是从n - 1到0包含最高位？

原因很简单：最高位的那个 1，最终就是我们要保留的“1”。题目要求减到 1 就结束，所以最高位这个 1 不需要再被右移掉，也不应该因为它再计入步数。如果强行把最高位也放进循环，你就会给这个 1 额外判一次“死刑”，答案会整体偏大。

那循环结束后为什么要return ans + carry？这里的carry表示的是：扫描完最高位之后，最高位的原始 1 如果遇上传上来的进位，就会发生 1 + 1 = 2，原最高位变成 0，进位产生的 1 成为新的最高位。这个新最高位就是最终剩下的那个 1，它不需要任何额外操作。所以末尾的carry不是一个“步数”，而是一个“标记”，表示当前还有这个新最高位存在。

我用"111"举例你就明白了。手算全过程："111"加 1 变"1000"，右移变"100"，再右移变"10"，再右移变"1"，总共 4 步。套公式：

• i = 2，s[2] = 1，carry = 0，bit = 1，奇数分支，ans 加 2，carry 变为 1；
• i = 1，s[1] = 1，carry = 1，bit = 2，偶数分支，ans 加 1，carry 仍为 1；
• 循环结束，ans = 3，返回 3 + 1 = 4。

正好是 4 步。那个末尾的carry = 1对应的是"111"加 1 之后多出来的新最高位"1000"中的那个 1。

3.4 拿 "1101" 完整跑一遍

前面手算过"1101"的答案是 6，现在用扫描法逐步验证：

注意 i = 2 这一步：s[2] 是 0，但 carry 是 1，所以实际这一位是 1，当前数字是奇数。这正好对应手算过程中的"111"：它加 1 变成"1000"，然后右移变成"100"，两步消耗被完整记录在 ans 里。

3.5 换个视角：答案等于右移次数加加 1 次数

官方题解里还给出过一个更本质的解释：整个过程的每一步操作，要么是右移，要么是加 1。右移次数等于最终二进制位数减去 1（因为最终只保留最高位的 1），加 1 次数等于从低到高扫描过程中遇到“实际值为 1”的次数。

看回"1101"：加 1 操作发生了 2 次，分别在最低位的 1 和倒数第二位的 1 上；右移操作发生了 4 次。2 + 4 = 6。用线性扫描代码解释就是：奇数分支每次 +2，其中 +1 记右移、+1 记加 1；偶数分支每次 +1 只记右移。这个视角用来面试讲题非常加分，因为你能把代码里的每个数字都解释出实际含义，而不是死记“bit 为 1 就加 2”。

4. 边界条件与容易踩的三个细节

4.1 最短输入是 "1"

如果输入直接是"1"，目标已经达到，答案是 0。代码里循环一次都不执行，carry初始为 0，直接返回 0。这个用例虽然简单，但很多人会在写字符串模拟时忘记处理，导致 while 循环条件判断出错或死循环。

4.2 全 1 字符串的极端进位

"111...1"这种输入最考验对加 1 进位链的理解。字符串模拟版在处理它时，每一步都可能要遍历一整串 1，性能直接拉满到 100ms 级别。而线性扫描版因为 carry 会持续存在，每个位置的bit都变成 2，全部走偶数分支，步数增量全部是 1，只有最后一次进位在末尾被ans + carry接住。从代码角度说，你要保证carry在连续 2 的情况下不会丢，这就是为什么偶数分支里必须写bit // 2而不是简单写成carry = 0。

4.3 Python 循环边界的坑

for i in range(n - 1, 0, -1)不包含 0，这正好跳过了最高位。我见过不少网友代码把这里写成range(n - 1, -1, -1)，结果最高位也被当成普通位处理，所有答案都会偏大。拿"10"验证：正确结果应该是 1，因为 2 除以 2 直接变 1；如果循环把最高位也算进去，你会得到 2 甚至更多。所以这个区间写法非常关键，写完务必用最短用例自测一遍。

还有一个隐藏细节：int(s[i]) + carry的结果不会超过 2，因为int(s[i])只能是 0 或 1，而carry在这个算法中只会是 0 或 1。因此合法输入下bit的范围就是 0 到 2，不需要考虑更大的进位分支。

5. 从 1404 延伸出去：位运算刷题的两条心法

5.1 把四则运算翻译成二进制操作

刷 LeetCode 热门 100 题和位运算题单时，你会发现一个高频套路：题目里只要出现“除以 2”“乘以 2”“判断奇偶”，几乎都可以翻译成右移、左移、看最低位。1404 是这套思路最直白的应用，再往后你会遇到统计二进制中 1 的个数（LeetCode 191）、判断一个数是否是 2 的幂（LeetCode 231）、比特位计数（LeetCode 338）等题，核心都是同一个能力：把十进制世界的运算直觉，转换成二进制位的结构观察。

比如说 LeetCode 191 里著名的x & (x - 1)技巧，作用是清除最低位的 1。这个技巧其实就是理解了“减 1 操作会让最低位的 1 变成 0，并把后面的 0 全部变成 1”这个二进制规律。1404 里的carry扫描，本质上也是在使用同样的进位传播思想，只不过方向赶巧是从低到高。

5.2 把加 1 看成一条进位链

很多人在做字符串模拟时，觉得加 1 就是调用一次加法函数就完事了，但 1404 告诉你：加 1 可能改变一整段连续的 1。这个观察对后续做二进制加法（LeetCode 67）、字符串加法（LeetCode 415）都很有帮助。处理这类问题时，我建议你先在草稿纸上画出“从低位到高位逐个处理进位”的过程，再动手写循环。只要你能熟练掌握“当前位 + 进位”这个状态机的流转，很多看起来复杂的题目都会突然变成同一个套路。

对于正在刷题的朋友，我还有一个很实用的学习节奏建议：不要把 1404 当作一道孤立的题做完就丢，试着把它和二进制的其他基础题放在同一天刷。今天做完 1404，第二天刷 191 和 338，周末再做一道 67 二进制加法，你会发现思路迁移得特别快。刷题指南里常说的“同类型题目集中突破”，就是这个意思。

5.3 适合联动的题目清单

如果你想把今天这个解法吃透，可以按下面的顺序做一组练习：

完成这一组之后，你再看 1404 就会觉得它其实是一道“包装成中等题的入门位运算题”。它的代码量不大，但考察的思维密度不低，值得多花半小时把原理彻底搞透。

我个人刷完这道题之后最大的体会是：永远不要急着用最直白的模拟去解决一道看似简单的题目。先在草稿纸上把二进制位的变化过程画出来，找到其中的规律，再动手写代码，往往能省下好几倍的调试时间。LeetCode 上很多题不是难在写代码，而是难在你能不能从“用计算机模拟过程”跳到“用数学语言描述过程”。1404 就是练习这种跳跃的好素材。