昨天刷题打卡恰好做到 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偶数右移变成111111最低位是 1奇数加 1 变成10001000右移变成100100右移变成1010右移变成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 的版本相比等于把耗压缩了两个数量级而核心逻辑反而更短。三种写法放在一起对比一下写法时间复杂度空间复杂度500 位用例实测参考字符串模拟O(n²)O(n)约 90~100msPython 大整数模拟约 O(n²)C 加速O(n)约 5~15ms线性扫描O(n)O(1)约 0~3ms3. 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。把这三条分支整理成表格原始位 s[i]低位进位 carry实际值 bit含义步数增量新 carry000偶数右移10101奇数加 1 后右移21011奇数加 1 后右移21112偶数右移11看到这里你应该能理解代码里的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 2s[2] 1carry 0bit 1奇数分支ans 加 2carry 变为 1i 1s[1] 1carry 1bit 2偶数分支ans 加 1carry 仍为 1循环结束ans 3返回 3 1 4。正好是 4 步。那个末尾的carry 1对应的是111加 1 之后多出来的新最高位1000中的那个 1。3.4 拿 1101 完整跑一遍前面手算过1101的答案是 6现在用扫描法逐步验证循环轮次s[i]carry进入前bit分支步数增量carry进入后ans 累计i 3101奇数212i 2011奇数214i 1112偶数115循环结束------ans carry 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 的关联点191位 1 的个数理解最低位和右移2312 的幂理解二进制中只有最高位为 1338比特位计数用递推关系统计每个数的 1 个数67二进制求和加 1 进位链的扩展版本415字符串相加把二进制进位推广到十进制进位完成这一组之后你再看 1404 就会觉得它其实是一道“包装成中等题的入门位运算题”。它的代码量不大但考察的思维密度不低值得多花半小时把原理彻底搞透。我个人刷完这道题之后最大的体会是永远不要急着用最直白的模拟去解决一道看似简单的题目。先在草稿纸上把二进制位的变化过程画出来找到其中的规律再动手写代码往往能省下好几倍的调试时间。LeetCode 上很多题不是难在写代码而是难在你能不能从“用计算机模拟过程”跳到“用数学语言描述过程”。1404 就是练习这种跳跃的好素材。