两数相除

先想最笨的:43 里能减掉几个 5?减一次记一次,减到不够减为止。简单,但慢。

笨办法 · 一次减一个 5：把 5 一个个排开。减掉第 1 个,剩余从 43 变 38,计数 +1。

笨办法 · 减第 2 次：再减一个 5,剩余 33,计数 2。一次只能减掉一个,效率低得很。

笨办法 · 减第 3 次：第 3 次,剩 28。照这速度还得再减 5 次,你已经能感觉到它有多笨了。

笨办法 · 减到第 8 次才停：就这么减 8 次才到剩 3(不够再减),商 = 8。可如果是 20 亿 ÷ 1 呢?要减 20 亿次——必然超时。

核心提速:别一个个减。把除数不断翻倍(左移一位 = ×2),找出「不超过剩余的最大那一坨」一次性减掉,商也对应加 1、2、4、8…

翻倍表 · 5 不断 ×2：把 5 一路左移:5、10、20、40。每个底下对应的「商」是 1、2、4、8。这就是我们的弹药库:能一次减 40,就等于一次顶了 8 个 5。

倍增找最大坨 · 起步：正式开演。剩余 43,从最小的 temp=5 起步(对应商 1)。看 temp 能不能再翻倍而不超过剩余。

10 ≤ 43 · 翻倍!：10 ≤ 43,可以!temp 翻到 10,商片段翻到 2。指针右移,继续试下一倍。

20 ≤ 43 · 再翻!：20 ≤ 43,继续翻!temp 到 20,商片段到 4。还能不能翻?再看下一格 40。

40 ≤ 43 · 还能翻!：40 ≤ 43,还能翻!temp 到 40,商片段到 8。下一步要试 80——这次该到头了。

80 > 43 · 翻不动了：再翻就是 80,80 > 43 超了。停!当前 temp=40 就是「不超过 43 的最大一坨」,它一次顶 8 个 5。

一次减掉 40：一刀切下 40,剩余从 43 直接掉到 3,商累加 8。一次抵笨办法的 8 次减法!

剩余 3 · 还能再减吗?：回到最小的 5 重新起步,可剩余只有 3,连一个 5 都减不动。循环结束,这点零头(余数 3)直接丢掉(向零取整)。

完成 · 商 = 8：商累计 = 8,余 3 舍去。43 ÷ 5 = 8 ✓。整个过程只做了减法和左移,没碰一次乘除。

再演一例 · 10 ÷ 3 起步：换 10÷3 再走一遍,看外层可能要凑好几轮。剩余 10,从 temp=3 起步。

10 ÷ 3 · 翻倍到 6：3 翻倍到 6(≤10),再翻 12 超了停。一次减 6,剩 4,商 = 2。第 1 轮结束。

10 ÷ 3 第 2 轮：剩 4 还够减一个 3,但翻倍到 6 就超了,所以只减 3,剩 1,商累加到 3。剩 1 不够减,结束 → 10÷3 = 3。这就是外层 while 跑两轮的样子。

10 ÷ 3 · 完成：两轮加起来商 = 3(2 + 1),余 1 丢掉。10 ÷ 3 = 3 ✓。可见外层 while 会反复「找最大坨→减掉」,直到剩余不够减。

倍增过程只认正数。所以先记下「最终是正还是负」(两数异号→负),把两数都取绝对值算,算完再决定要不要加负号。

32 位整数负数比正数多一个:能装 −2147483648,却装不下 +2147483648。所以 INT_MIN ÷ (−1) 必须特判,直接返回 INT_MAX。下面演这个雷。

溢出实演 · INT_MIN ÷ (−1)：看这个雷:被除数是 32 位能装的最小值 −2147483648,除数 −1。数学答案是把它变成正的。

数学答案越界：理论商 +2147483648 比 32 位能装的最大值 还大 1。硬算会溢出回绕成负数,得到错的结果。

特判钳制：唯一会溢出的就这一种组合。代码开头一行特判:碰到它直接返回 INT_MAX = 2147483647,绕开溢出。其余情况都安全。

边界三连：先把正常、溢出、异号三种想清,代码就稳了。注意向零取整:−2 而不是 −3。

面试追问：把「左移=乘2」「O(log²n) 怎么来」「溢出特判」讲清,是这题面试的得分点。