1. 从一道禁用除模的题说起它到底在考什么给定两个整数 A 和 B要求在不使用除法/和取模%运算的前提下求出 A 除以 B 的商和余数。这道题第一次看到的时候很多人的第一反应是这不是故意为难人吗——明明一行A / B和A % B就能搞定的事为什么要绕这么大一圈但如果你真的在底层开发、嵌入式、算法竞赛或者面试场景里摸爬滚打过一段时间就会明白这类题目从来不是为了让你重新发明除法而是在考察几件非常实在的能力对整数运算边界的敏感度、对二进制位运算的熟练程度、以及对效率这件事的量化判断。我自己第一次遇到这个题是在准备一场技术面试的时候当时脑子里只有最朴素的减法循环思路写出来之后面试官追问了一句如果 A 是 20 亿、B 是 1你这个循环要跑多少次我当场就意识到问题的严重性了。后来我把这道题反复拆解、用不同的思路实现、做了性能对比才真正把它吃透。这篇文章就把我踩过的坑、试过的方案、以及每种方案背后的取舍逻辑完整地分享出来不管你是刚学编程的新手还是想复习位运算的老手应该都能从中拿到点东西。需要先明确几个前提因为这道题的坑很大一部分藏在边界条件里。第一A 和 B 都是整数但具体是正整数、还是包含负数会直接决定实现的复杂度第二B 不能为 0这是除法的基本前提实际写代码时必须处理第三所谓不使用除法和取模通常也包括不能调用库函数里封装好的除法比如某些语言里的divmod之类。把这三点想清楚后面的方案设计才有意义。这道题的核心价值在于它逼着你去理解除法到底是什么。除法的本质其实是减法的一种加速形式——A 除以 B 的商就是从 A 里最多能减去多少个 B。理解了这一点所有的优化思路其实都是在回答同一个问题如何更快地数出这个多少个。朴素减法是一个一个数太慢二进制移位是一次数一大批快得多。这就是整篇文章的主线。2. 最朴素的减法循环能跑通但别高兴太早2.1 减法思路的直觉来源先从最符合直觉的方案讲起因为它是理解后续所有优化的地基。既然除法的本质是从被除数里反复减去除数那最直接的做法就是用一个计数器记录减了多少次每次从 A 里减去 B直到剩下的数小于 B 为止。这时候计数器的值就是商剩下的那个数就是余数。用生活化的类比来说这就像你有一堆糖果A 颗要平均分给若干个小朋友每个小朋友分 B 颗。你不知道能分给几个小朋友于是一个一个地分给第一个小朋友 B 颗剩下的还够不够再分一份够就继续不够就停。最后分出去的小朋友数量就是商手里剩下的糖果就是余数。这个类比虽然简单但它精确地对应了减法循环的每一步。写成代码大概是这样def div_subtract(a, b): if b 0: raise ValueError(除数不能为 0) quotient 0 # 处理同号/异号的情况这里先假设都是正数 while a b: a - b quotient 1 remainder a return quotient, remainder这段代码逻辑上完全正确对于 A17、B5 这种情况循环会执行 3 次得到商 3、余数 2答案没问题。很多初学者写到这里就觉得搞定了但如果只停在这一步那这道题就白做了。2.2 时间复杂度是致命伤问题出在效率上。上面这个循环的执行次数等于商的大小也就是大约 A/B 次。当 A 很大而 B 很小时这个次数会爆炸。举个极端的例子A 2,000,000,00020 亿B 1。这时候循环要执行 20 亿次哪怕每次循环只花 1 纳秒总共也要 2 秒。而如果用普通的除法运算这个过程是常数时间完成的几乎瞬间出结果。我在自己的机器上实测过用 Python 跑这个减法循环当 A 是 10 的 8 次方、B 是 1 的时候耗时已经肉眼可见地到了秒级而同样的输入用内置除法耗时在微秒级别。这个差距不是优化一下能弥补的而是算法复杂度层面的鸿沟——一个是 O(A/B)一个是 O(1)。提示面试里如果只写出减法循环通常会被追问能不能优化。这时候你要能立刻说出循环次数等于商最坏情况是 O(A/B)当 B 很小时会退化这句话本身就是加分项说明你有复杂度意识。2.3 减法方案里藏着的边界坑即便不考虑效率减法方案在边界处理上也有一堆细节。首先是负数如果 A 或 B 是负数while a b这个条件就不成立了。比如 A -17、B 5按数学定义商应该是 -4、余数应该是 3因为 -17 5 × (-4) 3但你的循环条件-17 5直接为假一次都不执行结果全错。其次是余数的符号这个容易被忽略的问题。不同的语言、不同的数学约定对余数符号的处理是不一样的。有的约定余数符号跟被除数一致截断除法C、Java、Python 的//和%在正数下一致但负数下不同有的约定余数永远非负地板除法。这道题如果没有明确约定你必须自己先定一个规则并在代码里贯彻到底。我个人的建议是先把 A 和 B 都转成正数处理记录下符号最后再根据约定调整商和余数的符号这样能把最复杂的符号逻辑隔离出来主循环只处理正数清爽很多。3. 二进制长除法把一个一个减升级成一批一批减3.1 核心洞察移位就是乘 2要真正优化这道题必须借助二进制。这里有一个关键事实在二进制下左移一位等于乘以 2右移一位等于除以 2。这个性质是后面所有优化的基石。既然除法是减法的加速那我们能不能一次减去一大块而不是一次只减一个 B答案是能。思路是这样的与其每次减 B不如先找到B 乘以 2 的多少次方仍然不超过 A。比如 A 100、B 3我们先看 3×26、3×412、3×824、3×1648、3×329696 不超过 100但 3×64192 超过了。于是我们知道商里至少有 32 这一份。先减去 96商加上 32剩下 4然后对剩下的 4 重复这个过程找到 3×13 不超过 4减去 3商加上 1剩下 1。最终商 32 1 33余数 1。验证一下33 × 3 1 100完全正确。这个过程的本质就是二进制长除法和我们小学学的十进制竖式除法是同一个道理只不过换成了二进制。十进制竖式里我们一位一位地试商二进制里每一位只有 0 和 1 两种可能试起来更简单。3.2 用移位实现找最大倍数上面那个找 B 乘以 2 的多少次方不超过 A的过程用移位实现非常自然。核心代码长这样def div_binary(a, b): if b 0: raise ValueError(除数不能为 0) # 先统一转成正数处理符号最后再补 sign 1 if a 0: a -a sign -sign if b 0: b -b sign -sign quotient 0 # 从高位往低位试 for shift in range(31, -1, -1): # 检查 b shift 是否不超过 a if (b shift) a: a - (b shift) quotient (1 shift) # 根据符号约定调整 if sign 0: quotient -quotient remainder a # 这里余数取非负约定 return quotient, remainder这段代码的关键在于那个从 31 到 0 的循环。为什么是 31因为对于 32 位整数来说商最大不会超过 2 的 31 次方考虑符号位所以从最高位开始试就够了。每一轮我们检查b shift也就是 b 乘以 2 的 shift 次方是否还小于等于当前的 a如果是就把它减掉并在商的对应二进制位上置 1。3.3 为什么这个方案快得多复杂度上这个方案是 O(32)也就是常数级别对于固定位宽的整数。不管 A 是 100 还是 20 亿循环次数都是固定的 32 次或者 64 次取决于整数位宽。这就把前面减法方案的 O(A/B) 直接降到了 O(位数)是质的飞跃。我用同样的测试数据对比过A 10 的 8 次方、B 1 的情况下减法方案要跑上亿次循环而二进制长除法只需要 32 次循环耗时从秒级降到微秒级。这个差距在真实系统里是决定性的——比如你在写一个嵌入式程序CPU 主频只有几十兆一次除法如果耗时几毫秒整个系统的实时性就崩了。注意b shift这个操作在 shift 很大时可能会溢出。比如 b 本身已经接近整数上限再左移 31 位就直接溢出了结果变成负数比较就失效了。稳妥的做法是先用一个循环把 b 左移到刚好不超过 a的最大位置或者用更宽的整数类型比如 Python 天然支持大整数但 C/Java 里要小心。这个坑我在 C 语言里踩过调试了半天才发现是溢出导致的比较错误。3.4 一个更省事的变体先对齐最高位上面那个从 31 开始逐位试的写法虽然正确但每一轮都要做一次移位和比较稍微有点浪费。一个常见的优化是先找到 b 需要左移多少位才能够得着 a 的最高位然后从这个位置开始往下试。这样能跳过前面一堆必然失败的比较。def div_binary_v2(a, b): if b 0: raise ValueError(除数不能为 0) sign 1 if a 0: a -a sign -sign if b 0: b -b sign -sign # 找到最大的 shift使得 b shift a shift 0 while (b (shift 1)) a: shift 1 quotient 0 while shift 0: if (b shift) a: a - (b shift) quotient (1 shift) shift - 1 if sign 0: quotient -quotient return quotient, a这个版本和前面那个本质一样只是起点更聪明。实测下来对于 A 远大于 B 的情况它能少做十几次无用的比较虽然提升幅度不大但在追求极致性能的场景里这种细节是值得抠的。4. 符号、溢出与边界那些真正让代码翻车的地方4.1 负数处理先转正再算最后补符号前面反复提到先转正再算这里展开讲讲为什么。整数除法最麻烦的地方就是符号。如果主循环里同时处理正负号条件判断会变得极其复杂容易出错。而如果把 A 和 B 都取绝对值主循环就只需要处理正数逻辑干净得多。符号的处理可以推迟到最后商的符号由 A 和 B 的符号共同决定同号为正、异号为负余数的符号则取决于你采用的约定。这里有个细节要注意取绝对值的时候如果 A 是最小的负数比如 32 位有符号整数的 -2147483648取绝对值会溢出因为正数最大只能表示到 2147483647。这个坑非常隐蔽很多标准库的abs函数在这个输入上都会出问题。稳妥的做法是先把 A 和 B 转成无符号类型或者更宽的类型再处理或者用 Python 这种天然支持大整数的语言来规避。4.2 余数符号的两种约定关于余数的符号业界主要有两种约定理解它们的区别很重要约定类型余数符号例子A-17, B5常见语言截断除法与被除数相同商 -3余 -2C、Java、Go地板除法永远非负商 -4余 3Python//和%两种约定都自洽区别在于商向零取整还是商向下取整。截断除法是向零取整地板除法是向下取整。这道题如果没有明确要求你需要自己选一种并说明。我个人的习惯是默认采用截断除法因为它和大多数系统级语言的默认行为一致迁移成本低。但如果题目来自 Python 背景那可能期望的是地板除法这时候就要在最后调整如果余数为负就把余数加上 |B|同时商减 1。4.3 除零和特殊输入的防御B 为 0 是必须拦截的这个不用多说。但还有一些边界值得注意A 为 0 时商和余数都是 0主循环一次都不执行结果自然正确不用特殊处理。B 为 1 时商就是 A余数是 0二进制长除法也能正确处理。B 为 -1 时如果 A 是最小负数商又会溢出这个和前面取绝对值溢出是同一类问题。我在实际项目里总结出一条经验凡是涉及整数除法的代码都要在函数入口处做一次完整的边界检查把 B0、A 或 B 为极值这些情况提前拦掉主逻辑只处理正常范围的输入。这样代码的可读性和可维护性都会好很多出 bug 的时候也容易定位。5. 不同实现方案的横向对比与选型建议5.1 三种方案的性能与适用场景把前面讲的方案整理成一张表方便你根据场景选型方案时间复杂度代码复杂度适用场景减法循环O(A/B)极低教学演示、A/B 很小的场景二进制长除法逐位试O(位数)中等通用场景、面试答题二进制长除法先对齐O(位数)中等偏高追求性能的底层实现从工程角度看二进制长除法是性价比最高的选择复杂度是常数级代码量也不大逻辑清晰可验证。减法循环虽然简单但只适合用来讲清楚除法是减法这个直觉真拿去做生产代码是要出事的。5.2 语言层面的差异不同语言实现这道题时有几个点需要特别注意。Python 天然支持任意精度整数不用担心溢出写起来最省心但要注意 Python 的//是地板除法和 C 系的截断除法不一样。C 和 Java 里整数位宽固定移位溢出是真实存在的风险必须用更宽的类型或者提前判断。JavaScript 的位运算会把操作数转成 32 位有符号整数超过范围会出问题处理大数时得用BigInt。我在用 JavaScript 实现的时候就被这个坑绊过A 和 B 稍微大一点位运算的结果就莫名其妙变成负数查了半天才发现是 32 位截断导致的。后来改用BigInt才正常。所以选语言的时候一定要先搞清楚它的整数模型。5.3 面试场景下的答题策略如果这道题出现在面试里我的建议是分三步走。第一步先说出最朴素的减法思路表明你理解了除法的本质第二步主动指出减法方案的性能问题引出二进制长除法的优化第三步写出二进制长除法的代码并主动讨论符号、溢出、除零这些边界。这样一套下来面试官能看到你的思维层次比一上来就写最优解但讲不清为什么要有说服力得多。提示面试时如果时间紧张可以先把正数版本的二进制长除法写对然后口头说明负数我会先取绝对值、最后补符号除零会在入口拦截这样既保证了代码正确性又展示了边界意识。6. 我在实际动手过程中踩过的几个坑6.1 移位溢出最隐蔽的 bug前面提过移位溢出这里再强调一次因为它真的太容易踩了。在 C 语言里b shift当 shift 接近 31 时如果 b 不是 1结果几乎必然溢出。溢出后的值是未定义行为undefined behavior可能变成负数、可能变成 0取决于编译器和平台。我第一次写的时候没注意测试用例里 A 和 B 都比较小跑得好好的一换成大数就出错而且错误结果毫无规律排查了很久。解决办法有两个一是用long long或者unsigned类型来承载移位结果扩大表示范围二是在移位前先判断b是否已经大于a shift用右移代替左移来避免溢出。第二种更优雅但可读性稍差。我现在的习惯是能用更宽类型就用更宽类型简单直接不容易出错。6.2 循环边界差一错误的重灾区二进制长除法里循环的起止位置很容易写错。比如从 31 开始还是从 30 开始到 0 结束还是到 1 结束这些差一错误off-by-one会导致结果差一个 2 的幂次非常隐蔽。我的经验是先用小数据手工验证循环边界比如 A5、B2手工推一遍每一位的情况确认循环覆盖了所有可能的位。确认无误后再跑大数据测试。6.3 符号调整的时机还有一个坑是符号调整的时机。我一开始把符号调整写在循环里面每减一次就判断一次符号代码又乱又慢。后来改成循环里只处理正数循环结束后统一调整代码立刻清爽了。这个经验其实很通用把变化的部分和不变的部分分开处理主循环只做最核心的减法符号、边界这些外围逻辑放到循环外是写出干净代码的关键。7. 从这道题延伸出去位运算还能做什么这道题表面上是在考除法实际上是在考位运算的运用能力。把这道题吃透之后你会发现位运算在很多地方都能派上用场。比如判断一个数是不是 2 的幂可以用n (n - 1) 0求一个数的二进制里有多少个 1可以用n (n - 1)反复消掉最低位的 1交换两个数不用临时变量可以用异或三次。这些技巧和二进制长除法是同一套思维方式的产物——把整数看成二进制位的组合而不是一个抽象的数量。我个人觉得这道题最大的收获不是学会了怎么写除法而是养成了遇到运算先想想二进制层面发生了什么的习惯。这个习惯一旦建立起来很多看似复杂的问题都会变得清晰。比如你以后再看到不用乘法实现乘法不用加法实现加法这类题思路其实是相通的都是把基本运算拆解成位操作再用循环或递归组合起来。最后分享一个我自己的练习方法把这道题的每种实现都手写一遍然后用随机数据和大数据分别测试对比结果和性能。手写能帮你记住细节测试能帮你发现边界问题对比能帮你建立性能直觉。这三件事做下来这道题才算真正变成你自己的东西。