两数相除 | 每日算法 · 变量语义法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8，-2.7335 将被截断至 -2。

返回被除数 dividend 除以除数 divisor 得到的商。

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−2³¹, 2³¹ − 1]。本题中，如果商 严格大于 2³¹ − 1，则返回 2³¹ − 1；如果商 严格小于 -2³¹，则返回 -2³¹。

示例 1

输入：dividend = 10, divisor = 3

输出：3

10/3 = 3.33333..，向零截断后得到 3。

示例 2

输入：dividend = 7, divisor = -3

输出：-2

7/-3 = -2.33333..，向零截断后得到 -2。

💭 模拟答题者思考

1. 我先想暴力：用 while a >= b 每次 a -= b; quotient++——逻辑对，但 dividend = 2³¹-1, divisor = 1 要循环 20 亿次，必超时。

2. 重复在哪里？每次只减一个 b 太碎。其实商的本质是「a 里能装下多少个 b」，可以一次减去 2b、4b、8b… 这样的大块，再把对应倍数加进商。

3. 位运算加倍：内层令 temp = b、multiple = 1，只要 a >= temp << 1 就同时左移 temp 和 multiple（等价于 ×2，不用乘法）。这样一轮能吃掉尽可能大的一块。

4. 符号单独处理：先把 dividend、divisor 转绝对值到 a、b，用异或判断 sign；唯一特判 INT_MIN / -1 会溢出，直接返回 INT_MAX。

5. 累加完乘 sign 后，用 max(INT_MIN, min(INT_MAX, quotient)) 裁剪到 32 位。每轮外层减一块、内层加倍，总复杂度 O(log²n)。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`sign`	int	定义：最终商的符号，`+1` 或 `-1` 维护：由 `dividend` 与 `divisor` 异号则为 `-1`，同号为 `+1` 更新：在转绝对值之前一次性确定，循环中不变
`a`	long	定义：被除数的绝对值，表示「还剩多少没减完」维护：每轮外层循环从 `a` 中减去一块 `temp`，直到 `a < b` 更新：初始化 `a = abs(dividend)`；每轮 `a -= temp`
`b`	long	定义：除数的绝对值，作为每次「加倍试探」的基准维护：全程不变，用于判断 `a` 是否还能再减以及内层左移的上界更新：初始化 `b = abs(divisor)`，循环中不变
`temp`	long	定义：当前这一轮准备一次性减去的「块」，等于 `b × 2^k` 维护：内层循环通过左移不断加倍，直到再加倍会超过 `a` 更新：每轮外层开始时重置为 `b`，内层满足条件时 `temp <<= 1`
`multiple`	long	定义：与 `temp` 同步的权重，表示本轮减去的块相当于多少个 `b` 维护：`temp` 每左移一位，`multiple` 也左移一位（即 ×2）更新：每轮外层重置为 `1`；减完后 `quotient += multiple`
`quotient`	long	定义：累加得到的商（绝对值部分）维护：每从 `a` 减去一块 `temp`，就把对应权重 `multiple` 加入商更新：初始化 `0`；每轮 `quotient += multiple`，最后乘 `sign` 并裁剪到 32 位范围

⌨️ 落码步骤

1. 特判 dividend == INT_MIN and divisor == -1，直接返回 INT_MAX

2. 计算 sign，令 a = abs(dividend)、b = abs(divisor)，quotient = 0

3. 外层 while a >= b：重置 temp = b、multiple = 1

4. 内层 while a >= temp << 1：temp <<= 1，multiple <<= 1（找到本轮最大可减块）

5. 执行 a -= temp，quotient += multiple，继续外层直到 a < b

6. 返回 sign * quotient 裁剪到 [INT_MIN, INT_MAX]

💻 代码实现

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31
        if dividend == INT_MIN and divisor == -1:
            return INT_MAX
        sign = -1 if (dividend < 0) ^ (divisor < 0) else 1
        a, b = abs(dividend), abs(divisor)
        quotient = 0
        while a >= b:
            temp, multiple = b, 1
            while a >= temp << 1:       # 加倍试探，找本轮最大块
                temp <<= 1
                multiple <<= 1
            a -= temp
            quotient += multiple
        quotient *= sign
        return max(INT_MIN, min(INT_MAX, quotient))

class Solution {
public:
    int divide(int dividend, int divisor) {
        const int INT_MAX = 0x7FFFFFFF;
        const int INT_MIN = 0x80000000;
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;
        int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
        long a = labs((long)dividend), b = labs((long)divisor);
        long quotient = 0;
        while (a >= b) {
            long temp = b, multiple = 1;
            while (a >= (temp << 1)) {   // 加倍试探，找本轮最大块
                temp <<= 1;
                multiple <<= 1;
            }
            a -= temp;
            quotient += multiple;
        }
        quotient *= sign;
        if (quotient > INT_MAX) return INT_MAX;
        if (quotient < INT_MIN) return INT_MIN;
        return (int)quotient;
    }
};
// 时间 O(log²n)，空间 O(1)

📈 复杂度分析

时间复杂度 O(log²n)

空间复杂度 O(1)

⚠️ 常见坑

❗ 溢出：必须用 long 存 a、b、temp、quotient；INT_MIN / -1 在 32 位下会溢出，需单独返回 INT_MAX。

❗ 内层条件是 a >= temp << 1（还能再翻倍才移），不是 a >= temp；否则 temp 会多加一位导致减法过量。

❗ 符号用异或 (dividend < 0) ^ (divisor < 0) 判断，转绝对值后再算；最后结果要裁剪到 32 位有符号范围。

🔍 必测边界 Case

Case 1：被除数为 0

dividend = 0, divisor = 5 → 0（a < b，循环不执行）

Case 2：溢出边界

dividend = -2147483648, divisor = -1 → 2147483647（唯一需特判的溢出情形）

Case 3：商为 1

dividend = 3, divisor = 3 → 1（a == b，一轮减完）