不使用乘除和取模如何实现整数除法？（LeetCode 29）

简化版

整数除法不能用乘法、除法、取模时，可以用“倍增减法”。朴素做法是不断用被除数减除数，太慢；优化做法是每轮把除数不断翻倍，找到不超过当前被除数的最大倍数，一次减掉。符号单独处理，最后根据正负号返回结果。

最大坑是溢出：Integer.MIN_VALUE / -1 的数学结果是 2147483648，超过 int 最大值，要返回 Integer.MAX_VALUE。为了避免 abs(Integer.MIN_VALUE) 溢出，常用 long 承接绝对值。

详细版

int divide(int dividend, int divisor) {
    if (dividend == Integer.MIN_VALUE && divisor == -1) {
        return Integer.MAX_VALUE;
    }

    boolean negative = (dividend < 0) ^ (divisor < 0);
    long a = Math.abs((long) dividend);
    long b = Math.abs((long) divisor);
    int ans = 0;

    while (a >= b) {
        long cur = b;
        int count = 1;
        while ((cur << 1) <= a) {
            cur <<= 1;
            count <<= 1;
        }
        a -= cur;
        ans += count;
    }

    return negative ? -ans : ans;
}

思路是用 b, 2b, 4b, 8b... 快速逼近当前剩余的 a。每轮至少减掉一个最大二进制块，所以时间复杂度约 O(log n * log n)，也可以预处理倍增表优化为 O(log n)。

完整版教学

一、朴素减法为什么不够

如果要计算 100 / 3，不断执行 100-3-3-...，减 33 次得到商 33。这个方法在小数字上能工作，但当被除数接近 2^31 时，可能要循环上十亿次，明显不可接受。

这道题真正考的是：不用乘除取模，如何快速找到“除数能放进被除数多少次”。答案是倍增，也就是用加法和位移构造 divisor * 2^k。

二、倍增减法的核心

每一轮不只减一个 divisor，而是找当前剩余值中能容纳的最大翻倍块。

43 / 3
3, 6, 12, 24, 48(超过)
先减 24，商加 8，剩余 19

3, 6, 12, 24(超过)
再减 12，商加 4，剩余 7

3, 6, 12(超过)
再减 6，商加 2，剩余 1

1 < 3，停止
商 = 8 + 4 + 2 = 14

本质上，商 14 被拆成二进制块 8 + 4 + 2。

三、符号处理要和绝对值处理分开

商的符号只由两个数是否异号决定：异号为负，同号为正。可以用异或表达：

boolean negative = (dividend < 0) ^ (divisor < 0);

之后把两个数都转成非负长整型再做倍增。这样主循环只关心正数减法，逻辑更清晰。

四、为什么要先转 long 再取绝对值

int 的范围是不对称的：[-2147483648, 2147483647]。Integer.MIN_VALUE 的绝对值是 2147483648，无法放进 int。

long a = Math.abs((long) dividend);
long b = Math.abs((long) divisor);

如果写成 Math.abs(dividend)，当 dividend == Integer.MIN_VALUE 时结果仍然是负数，后续比较和位移都会出错。这是本题最常见的坑。

处理整数边界时，凡是出现取负、取绝对值、左移翻倍，都要先想清楚是否会触碰 Integer.MIN_VALUE 或上界溢出。

五、内层循环如何找到最大块

内层循环从 cur=b 开始，不断左移：

long cur = b;
int count = 1;
while ((cur << 1) <= a) {
    cur <<= 1;
    count <<= 1;
}

cur 表示当前能减掉的除数倍数，count 表示这个倍数对应的商。比如 cur=24 时，如果原始除数是 3，那么 count=8。当下一次翻倍超过 a，当前 cur 就是最大可减块。

六、复杂度和优化方式

方法	思路	时间复杂度	备注
朴素减法	每次减一个 divisor	O(商)	大数会超时
每轮重新倍增	每轮找最大 `divisor*2^k`	O(log^2 n)	代码最直观
预处理倍增表	先列出所有块，再从大到小减	O(log n)	更像二进制拆分

面试中写每轮倍增通常已经足够，能清晰解释边界比追求最短代码更重要。

七、特殊溢出分支

只有一个结果会超过 int 上界：Integer.MIN_VALUE / -1。根据题目要求，遇到它返回 Integer.MAX_VALUE。

-2147483648 / -1 = 2147483648
int 最大值 = 2147483647
所以返回 2147483647

其他情况即使被除数是 Integer.MIN_VALUE，只要除数不是 -1，结果都能落在 int 范围内。

八、常见误区与追问

误区：直接使用 Math.abs(int)。 Integer.MIN_VALUE 取绝对值仍会溢出，必须先转 long。
误区：漏掉 MIN_VALUE / -1。 这是唯一会让最终商超过 int 上界的组合。
误区：用连续减法就算完成。 大输入会退化到 O(n)，面试通常不能接受。
误区：符号在循环中混着处理。 符号单独判断，主逻辑使用非负数更稳定。
追问：为什么倍增可以加速？ 因为每次用 2^k 倍除数覆盖一大段商，相当于按二进制拆商。
追问：能不能做到 O(log n)？ 可以预处理所有不超过被除数的倍增块，再从大到小选择。

九、加强记忆

除法可以理解成“除数能被减掉多少次”。
朴素减法慢，倍增一次减掉 divisor * 2^k。
符号用异或判断，主循环只处理正数。
Integer.MIN_VALUE 的绝对值必须用 long 承接。
特判 MIN_VALUE / -1 返回 Integer.MAX_VALUE。

简化版

详细版