LeetCode 29. 两数相除

2026-08-27 HGNULB 约 5 分钟

文章信息 11 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决 10-20 字节跳动微软美团腾讯百度华为

题目描述

✅ 29. 两数相除

题意分析

给定两个 32 位有符号整数 dividend 和 divisor，求它们相除的商，并且不允许使用乘法、除法和取余运算符。结果向零截断，也就是说 -7 除以 3 得 -2 而不是 -3。

约束信号有两条，都是本题真正的考点。第一，禁用 *、/、%，能用的只有加减法和位移，商必须靠这些原语拼出来。第二，运算全程被限制在 32 位有符号整数范围 $[-2^{31}, 2^{31} - 1]$ 内，题目额外规定：若商超出这个范围，就返回 $2^{31} - 1$。

唯一会越界的输入是 INT_MIN / -1，它的真值是 $2^{31}$，恰好比上界大 1，必须钳制到 INT_MAX 返回；除此之外任何组合的商都落在合法范围内。

另一个更隐蔽的边界是 INT_MIN 自身：32 位补码里它的绝对值 $2^{31}$ 无法表示，abs(INT_MIN) 会原地翻回 INT_MIN，所以任何「先取绝对值再算」的写法都必须先想清楚用什么类型来承载中间量。

其余边界包括：被除数为 0；除数绝对值为 1；被除数绝对值小于除数（商为 0）；两数一正一负导致结果为负。

解法：二进制长除法

核心思路

逐次减去除数最坏需要约 $2^{31}$ 次。更高效的做法是把商看成二进制数，从第 31 位到第 0 位依次试探：若“除数绝对值左移 bit 位”不超过当前余数，就减去这块，并把商的第 bit 位置 1。

这是整数的二进制长除法。处理完某一位后始终满足：被除数绝对值等于“当前商乘除数绝对值”加当前余数。按高位到低位试商也不会错过最优解：若当前倍数放得下，该位对应的数量不可能由更低位补足；若放不下，该位当然不能取 1。

溢出是本题另一半。必须先把 32 位操作数转成 64 位，再取绝对值，才能安全表示 INT_MIN 的绝对值；INT_MIN / -1 的结果本身超出 32 位上界，需要按题意单独返回 INT_MAX。

解题步骤

特判 INT_MIN / -1，避免唯一的返回值溢出场景。

用两个操作数符号是否不同记录结果正负。

先转成 64 位，再取绝对值得到 remain 和 value。

从第 31 位降到第 0 位。若 value << bit 不超过 remain，就减去它，并给商加上 1 << bit。

根据记录的符号给商取正或取负，转回 32 位返回。

以 43 / 4 为例：4 << 3 = 32 可以减，商先得到 8，余数变为 11；4 << 1 = 8 还能减，商变为 10，余数为 3；更低位都放不下，最终返回 10。

代码实现

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

        boolean negative = (dividend < 0) ^ (divisor < 0);
        long remain = Math.abs((long) dividend);
        long value = Math.abs((long) divisor);
        long quotient = 0;
        for (int bit = 31; bit >= 0; bit--) {
            long chunk = value << bit;
            if (chunk <= remain) {
                remain -= chunk;
                quotient += 1L << bit;
            }
        }
        return (int) (negative ? -quotient : quotient);
    }
}

func divide(dividend int, divisor int) int {
    const maxInt32 = 1<<31 - 1
    const minInt32 = -1 << 31
    if dividend == minInt32 && divisor == -1 {
        return maxInt32
    }

    negative := (dividend < 0) != (divisor < 0)
    remain := absInt64(int64(dividend))
    value := absInt64(int64(divisor))
    quotient := int64(0)
    for bit := 31; bit >= 0; bit-- {
        chunk := value << bit
        if chunk <= remain {
            remain -= chunk
            quotient += int64(1) << bit
        }
    }
    if negative {
        quotient = -quotient
    }
    return int(quotient)
}

func absInt64(num int64) int64 {
    if num < 0 {
        return -num
    }
    return num
}

复杂度分析

时间复杂度：$O(\log M)$，M 为被除数绝对值；对 32 位整数固定检查 32 个商位，也可视为 $O(1)$。

空间复杂度：$O(1)$，只使用若干整数变量。

关键点总结

从高位到低位试商，本质是二进制长除法；每个商位只判断一次。

必须先转成 64 位再取绝对值，否则 abs(INT_MIN) 会在 32 位内溢出。

INT_MIN / -1 是唯一一个数学结果超出 32 位返回范围的输入，必须返回 INT_MAX。

若面试限制不能使用 64 位整数，可把两个操作数统一转为负数，在负数域完成比较和倍增，因为负数域能表示 INT_MIN。

易错点总结

漏掉 INT_MIN / -1 特判：正确数学结果是 2147483648，转回 int 会溢出。

写成 (long) Math.abs(dividend)：绝对值已经先在 int 中溢出；正确顺序是 Math.abs((long) dividend)。

只根据被除数判断符号：7 / -3 会被误判为正数；应比较两个操作数符号是否不同。

用 chunk < remain 而不是 <=：当剩余量恰好等于当前倍数时会漏掉该商位，例如 8 / 2。

把负数除法理解为向下取整：题目要求向零截断，-7 / 3 应返回 -2。

相似题目

题目	难度	考察点
50. Pow(x, n)	中等	倍增思想实现快速幂
371. 两整数之和	中等	位运算模拟加法进位
LCR 001. 两数相除	简单	同题的位运算除法
面试题 16.09. 运算	中等	仅用加法实现四则运算