跳到主要内容

LeetCode 29. 两数相除

本节目标

用二进制长除法从高位到低位确定商，并处理符号、INT_MIN 与唯一溢出。

这道题承接位运算拓展：当不能使用乘、除和取模时，把除数写成若干个二进制倍数，仍能逐位构造商。

查看原题

题意与约束​

给定 32 位有符号整数 dividend 和非零 divisor，计算 dividend / divisor，结果向 0 截断。题目不允许在主算法中使用乘法、除法和取模；若结果超出 32 位有符号整数范围，只会是 -2^31 / -1，此时返回 2^31 - 1。

因此，10 / 3 的答案是 3，7 / -3 的答案是 -2。除数非零由题目保证，平台函数不需要额外定义除零行为。

从重复减法到倍增​

反复减去除数可以得到商，但当被除数很大、除数很小时，需要执行非常多轮。例如从 2^31 - 1 中每次减去 1 显然不可行。

左移一位会把一个非负数变成它的二进制两倍。于是可以尝试减去 divisor << k：它代表除数的第 k 个二进制倍数，也同时代表商中加入 2^k。一次选择较大的 k，就把多次重复减法合并成一次。

二进制长除法​

先把两个数转换为非负的绝对值 a 与 b。从 k = 31 依次检查到 0：若 a >> k >= b，也就是剩余值至少能减去 b 的第 k 个二进制倍数，就从 a 中减去 b << k，并把商的第 k 位设为 1。

以 10 / 3 为例，所有高于第 1 位的尝试都失败。第 1 位时，10 >> 1 = 5 >= 3，减去 3 << 1 = 6 后余数为 4，商累积为 2。第 0 位时，4 >= 3，再减去 3 后余数为 1，商累积为 3。

从高位到低位决定商位是正确的：若当前余数容得下 b << k，这个 2^k 一定应属于商；减去它后余数小于原余数，后续只需决定更低位。若容不下，任何包含该位的商都会超过被除数，只能把这一位留为 0。每一轮都保持不变式：b × 已确定商 + 当前余数 = 原始被除数的绝对值。在 10 / 3 的轨迹中，确定第 1 位后是 3 × 2 + 4 = 10，确定第 0 位后是 3 × 3 + 1 = 10；直到所有 32 位检查完毕，该关系仍成立。

符号与截断方向​

长除法只处理绝对值，先得到非负商的大小，再根据两个输入的符号是否不同决定结果是否为负。这正好实现向 0 截断：7 与 -3 的绝对值商为 2，补上负号得到 -2。

不要把 Python 的 // 当作这里的语义。7 // -3 是 -3，因为它向负无穷取整；本题要求的是 -2，即向 0 截断。先算绝对值商、最后统一处理符号能让两种语言保持一致。

INT_MIN 与唯一溢出​

INT_MIN 等于 -2^31，它的绝对值 2^31 无法放入 32 位有符号 int。C++ 先把输入转换为 64 位的 long long，再取相反数，才能安全得到非负绝对值并进行移位。

唯一无法表示的结果是 INT_MIN / -1 = 2^31；必须在一般流程前直接返回 INT_MAX。其余情况的商都能表示为 int，包括 INT_MIN / 1 = INT_MIN。Python 整数没有固定宽度，仍显式定义同样的边界常量和守卫，以保持与题目 32 位契约一致。

代码实现​

两份源码都先处理唯一溢出，再从第 31 位扫描到第 0 位。C++ 用 long long 保存绝对值与商；Python 用相同的移位过程，最后再应用符号。

C++17
#include <climits>

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }

        long long a = dividend;
        long long b = divisor;
        if (a < 0) {
            a = -a;
        }
        if (b < 0) {
            b = -b;
        }

        long long quotient = 0;
        for (int shift = 31; shift >= 0; shift--) {
            if ((a >> shift) >= b) {
                a -= b << shift;
                quotient += 1LL << shift;
            }
        }

        if ((dividend < 0) != (divisor < 0)) {
            quotient = -quotient;
        }
        return static_cast<int>(quotient);
    }
};

复杂度分析​

  • 时间复杂度：O(32)，固定检查 32 个二进制位，在题目的固定宽度下也可视为 O(1)。
  • 空间复杂度：O(1)，只使用绝对值、商和循环变量等常数个变量。

易错点​

  • 直接对 C++ 的 int 取 INT_MIN 的绝对值：结果无法表示，应先转换为 long long。
  • 忽略 INT_MIN / -1：这是唯一需要截断到 INT_MAX 的溢出对。
  • 先给输入加符号、在循环中处理负余数：右移与比较更难推理，应全程处理非负绝对值。
  • 把负数结果按向下取整处理：本题是向 0 截断，7 / -3 必须返回 -2。
  • 只从低位向高位尝试：会重复处理小倍数；从高位开始才能一次确定最大的可行商位。

模式迁移​

遇到“不能使用乘、除或模，但需要组合某个量的倍数”的题目，可先把倍数写成二进制位：高位到低位试探、可行就扣除并记录该位。若输入允许负数或固定宽度整数，还要把符号、绝对值范围和最终表示范围放在主循环之外单独验证。