0029. Divide Two Integers

题目信息

题号:
  1. 两数相除

难度:

Medium

主题:

整数、倍增、二进制、贪心、溢出

原题:

LeetCode 0029

重点:

从逐次减法推导到按二进制位试商,并安全处理向零截断、符号和 32 位边界

题目重述

给定两个 32 位有符号整数 dividend 和 divisor,计算整数商并返回。不得使用乘法、除法和取模运算符。

结果的小数部分必须向零截断。例如 7 / -3 返回 -2,而不是向下取整得到 -3。题目保证 divisor != 0。

输入范围为 [-2^31, 2^31 - 1]。若数学结果超过 32 位有符号整数范围,只会发生在 INT_MIN / -1,此时必须返回 INT_MAX。

自建示例

  • 正数且有余数:dividend = 58、divisor = 7,返回 8,因为 58 = 7 * 8 + 2;

  • 异号并向零截断:dividend = -58、divisor = 7,返回 -8;

  • 被除数绝对值较小:dividend = 3、divisor = 5,返回 0;

  • 最小负数:dividend = INT_MIN、divisor = 1,返回 INT_MIN;

  • 唯一溢出:dividend = INT_MIN、divisor = -1,返回 INT_MAX。

C++ 实现

#include <climits>

class Solution {
private:
    long long magnitude(int value) {
        return value < 0 ? -static_cast<long long>(value) : static_cast<long long>(value);
    }

    int applySignAndClamp(long long quotient, bool negative) {
        if (!negative && quotient > INT_MAX) {
            return INT_MAX;
        }
        const long long signedQuotient = negative ? -quotient : quotient;
        return static_cast<int>(signedQuotient);
    }

    int repeatedSubtraction(int dividend, int divisor) {
        long long remaining = magnitude(dividend);
        const long long base = magnitude(divisor);
        long long quotient = 0;
        while (remaining >= base) {
            remaining -= base;
            ++quotient;
        }
        const bool negative = (dividend < 0) != (divisor < 0);
        return applySignAndClamp(quotient, negative);
    }

    int repeatedDoubling(int dividend, int divisor) {
        long long remaining = magnitude(dividend);
        const long long base = magnitude(divisor);
        long long quotient = 0;
        while (remaining >= base) {
            long long chunk = base;
            long long contribution = 1;
            while ((chunk << 1) <= remaining) {
                chunk <<= 1;
                contribution <<= 1;
            }
            remaining -= chunk;
            quotient += contribution;
        }
        const bool negative = (dividend < 0) != (divisor < 0);
        return applySignAndClamp(quotient, negative);
    }

    int binaryLongDivision(int dividend, int divisor) {
        long long remaining = magnitude(dividend);
        const long long base = magnitude(divisor);
        long long quotient = 0;
        for (int bit = 31; bit >= 0; --bit) {
            const long long chunk = base << bit;
            if (chunk <= remaining) {
                remaining -= chunk;
                quotient += 1LL << bit;
            }
        }
        const bool negative = (dividend < 0) != (divisor < 0);
        return applySignAndClamp(quotient, negative);
    }

public:
    int divide(int dividend, int divisor) {
        return binaryLongDivision(dividend, divisor);
    }
};

题解

除法的直接含义

先忽略符号。若不断从 |dividend| 中减去 |divisor|,能够成功减去的次数就是商的绝对值;当剩余量小于 除数绝对值时停止,未被消去的部分就是余数。

repeatedSubtraction 直接实现这一含义。每次循环保持:

|dividend| = |divisor| * quotient + remaining

循环结束时 0 <= remaining < |divisor|,因此 quotient 正是绝对值除法向下取整后的结果。最后再恢复符号, 就得到题目要求的向零截断商。

这个方法的问题不在正确性,而在每轮只增加 1。例如 INT_MAX / 1 需要超过二十亿轮,时间与商的数值 大小成正比。

倍增删除重复减法

一次减去一个除数过慢,可以通过加法倍增构造:

divisor, 2 * divisor, 4 * divisor, 8 * divisor, ...

代码不使用乘法,而是让 chunk 和对应的 contribution 同时左移一位。若当前剩余量至少容纳两倍 chunk,就继续倍增;否则当前 chunk 是本轮能够减去的最大二次幂倍数。

以 58 / 7 为例,第一轮依次得到 7、14、28、56,一次减去 56,商增加 8,剩余 2。 这相当于把八次重复减法压缩为一次减法和若干次倍增。

repeatedDoubling 每轮都从 base 重新构造最大倍数。外层最多执行 O(log |quotient|) 轮,每轮又可能 倍增 O(log |quotient|) 次,因此最坏时间为 O(log² |quotient|)。

商的二进制分解

逐轮倍增仍在重复构造同一组二次幂倍数。商本身可以写成若干二次幂之和,例如:

13 = 8 + 4 + 1 = 1101₂

因此可以从最高位到最低位直接判断商的每一位是否为 1。对于位 bit,候选除数倍数为 base << bit:

  • 候选不大于当前剩余量时,该位可以取 1,减去候选并把 1 << bit 加入商;

  • 候选大于当前剩余量时,该位只能取 0,继续检查更低位。

处理完某一位后,更高位已经固定,剩余量只需要由更低位对应的倍数继续表示。这就是整数长除法在二进制中的形式。

降序试商

必须从高位向低位判断。若最高可行位没有选入,只靠所有更低位之和也无法得到更大的合法商;选入后,算法再用 低位填充剩余量,最终得到不超过被除数绝对值的最大除数倍数。

以 58 / 7 为例:

商位

候选倍数

剩余量

动作

2^3

7 << 3 = 56

58

选入,商变为 8,剩余 2

2^2

28

2

跳过

2^1

14

2

跳过

2^0

7

2

跳过

最终商为 8。剩余量 2 小于除数 7,不能再增加任何商位。

固定扫描范围

两个输入都是 32 位整数,商的绝对值最大为 2^31,所以只需要检查 bit = 31 到 0 共 32 个位置。

base 最大为 2^31。计算 base << 31 时最大得到 2^62,仍在 64 位有符号整数范围内。使用 long long 保存绝对值、候选倍数和商,可以安全表示 |INT_MIN| = 2^31,也避免对 INT_MIN 直接取 32 位绝对值产生溢出。

符号与截断方向

主体算法只计算:

floor(|dividend| / |divisor|)

若两个输入符号不同,就对这个非负商取负。余数始终被直接舍弃,没有在负数结果上再减一,因此结果向零截断。 例如 -58 / 7 的绝对值商为 8,恢复符号后得到 -8。

两个输入是否异号可由 (dividend < 0) != (divisor < 0) 判断。零既不小于零,也不会造成符号歧义。

唯一溢出

32 位正数最大值为 2^31 - 1,负数最小值为 -2^31。只有 INT_MIN / -1 会产生正数 2^31, 超过 INT_MAX;其他商都能放入 32 位有符号整数。

applySignAndClamp 在恢复正号前检查这一情况并返回 INT_MAX。当结果为负数 -2^31 时,它仍是合法的 INT_MIN,可以安全转换回 int。

代码演进

repeatedSubtraction 每轮只删除一个除数,代码直接对应除法定义,但运行次数等于商的绝对值。

repeatedDoubling 用左移构造二次幂倍数,一轮可以替代大量重复减法;它删除了线性于商的循环,却会在每个外层 阶段重新从 base 开始倍增。

binaryLongDivision 直接枚举商的 32 个二进制位。逐轮重新构造倍数的内层循环消失,每个候选位只计算一次, 同时不再需要保存倍增表。公开入口采用这一方法。

复杂度分析

方法

时间复杂度

工作空间

主要代价

重复减法

O(|quotient|)

O(1)

每次只消去一个除数

逐轮倍增

O(log² |quotient|)

O(1)

每轮重新寻找最大二次幂倍数

二进制长除法

O(log C)

O(1)

从高到低检查固定整数范围内的商位

C 表示整数取值范围;对固定 32 位输入,主解法始终检查 32 个商位,因此运行次数具有常数上界。