两数相除 图解题解

这道题到底在问什么

dividend

43

divisor

5

输出

8

先想最直接的笨办法

一刀切下 40,剩余从 43 直接掉到 3,商累加 8。一次抵笨办法的 8 次减法!（动画第 15 步）

最优解：一步一步想明白

1. 3思路一句话：商就是被除数里装得下几个除数。先用最笨的一个个减打底，下面再用位运算倍增提速。下面一步步演给你看。
2. 4减第 1 次把 5 一个个排开。减掉第 1 个,剩余从 43 变 38,计数 +1。
3. 5继续一个个减再减一个 5,剩余 33,计数 2。一次只能减掉一个,效率低得很。
4. 6还在慢慢减第 3 次,剩 28。照这速度还得再减 5 次,你已经能感觉到它有多笨了。
5. 7剩 3 不够减就这么减 8 次才到剩 3(不够再减),商 = 8。可如果是 20 亿 ÷ 1 呢?要减 20 亿次——必然超时。
6. 8核心提速:别一个个减。把除数不断翻倍(左移一位 = ×2),找出「不超过剩余的最大那一坨」一次性减掉,商也对应加 1、2、4、8…
7. 95 << k 各代表的「倍数」把 5 一路左移:5、10、20、40。每个底下对应的「商」是 1、2、4、8。这就是我们的弹药库:能一次减 40,就等于一次顶了 8 个 5。
8. 10temp=5,商片段=1正式开演。剩余 43,从最小的 temp=5 起步(对应商 1)。看 temp 能不能再翻倍而不超过剩余。
9. 11temp 5→10,商片段 1→210 ≤ 43,可以!temp 翻到 10,商片段翻到 2。指针右移,继续试下一倍。
10. 12temp 10→20,商片段 2→420 ≤ 43,继续翻!temp 到 20,商片段到 4。还能不能翻?再看下一格 40。
11. 13temp 20→40,商片段 4→840 ≤ 43,还能翻!temp 到 40,商片段到 8。下一步要试 80——这次该到头了。
12. 14停在 temp=40再翻就是 80,80 > 43 超了。停!当前 temp=40 就是「不超过 43 的最大一坨」,它一次顶 8 个 5。
13. 15剩余 43→3,商 +8一刀切下 40,剩余从 43 直接掉到 3,商累加 8。一次抵笨办法的 8 次减法!
14. 163 < 5,减不动回到最小的 5 重新起步,可剩余只有 3,连一个 5 都减不动。循环结束,这点零头(余数 3)直接丢掉(向零取整)。
15. 1743 ÷ 5 = 8 ✓商累计 = 8,余 3 舍去。43 ÷ 5 = 8 ✓。整个过程只做了减法和左移,没碰一次乘除。
16. 18temp=3,商片段=1换 10÷3 再走一遍,看外层可能要凑好几轮。剩余 10,从 temp=3 起步。
17. 196≤10,翻!12>10 停3 翻倍到 6(≤10),再翻 12 超了停。一次减 6,剩 4,商 = 2。第 1 轮结束。
18. 20剩 4,翻不动,减一个 3剩 4 还够减一个 3,但翻倍到 6 就超了,所以只减 3,剩 1,商累加到 3。剩 1 不够减,结束 → 10÷3 = 3。这就是外层 while 跑两轮的样子。
19. 21商 = 3,余 1 丢弃两轮加起来商 = 3(2 + 1),余 1 丢掉。10 ÷ 3 = 3 ✓。可见外层 while 会反复「找最大坨→减掉」,直到剩余不够减。
20. 22倍增过程只认正数。所以先记下「最终是正还是负」(两数异号→负),把两数都取绝对值算,算完再决定要不要加负号。
21. 2332 位整数负数比正数多一个:能装 −2147483648,却装不下 +2147483648。所以 INT_MIN ÷ (−1) 必须特判,直接返回 INT_MAX。下面演这个雷。
22. 24dividend = −2147483648看这个雷:被除数是 32 位能装的最小值 −2147483648,除数 −1。数学答案是把它变成正的。
23. 25+2147483648 装不下理论商 +2147483648 比 32 位能装的最大值 还大 1。硬算会溢出回绕成负数,得到错的结果。
24. 26直接返回 INT_MAX唯一会溢出的就这一种组合。代码开头一行特判:碰到它直接返回 INT_MAX = 2147483647,绕开溢出。其余情况都安全。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def divide(self, dividend, divisor):
        INT_MIN, INT_MAX = -2147483648, 2147483647
        if dividend == INT_MIN and divisor == -1:
            return INT_MAX            # 唯一溢出特判
        neg = (dividend < 0) != (divisor < 0)
        a, b = abs(dividend), abs(divisor)
        q = 0
        while a >= b:
            temp, m = b, 1
            while a >= (temp << 1):   # 不断翻倍找最大坨
                temp <<= 1
                m <<= 1
            a -= temp                 # 一次减掉一大坨
            q += m
        return -q if neg else q

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;
        bool neg = (dividend < 0) != (divisor < 0);
        long a = labs((long)dividend), b = labs((long)divisor);
        long q = 0;
        while (a >= b) {
            long temp = b, m = 1;
            while (a >= (temp << 1)) { temp <<= 1; m <<= 1; }
            a -= temp; q += m;
        }
        return neg ? -(int)q : (int)q;
    }
};

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1)
            return Integer.MAX_VALUE;
        boolean neg = (dividend < 0) != (divisor < 0);
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        long q = 0;
        while (a >= b) {
            long temp = b, m = 1;
            while (a >= (temp << 1)) { temp <<= 1; m <<= 1; }
            a -= temp;
            q += m;
        }
        return neg ? (int) -q : (int) q;
    }
}

复杂度

面试官可能追问