LeetCode LCR 001. 两数相除

约 8 分钟
文章信息 5 个分类 2 个标签
分类
LeetCode 简单 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数学 LCR
目录

题目描述

✅ LCR 001. 两数相除

题意分析

给两个 32 位有符号整数 a、b，求 a / b 的商，向零取整（也就是 10 / 3 = 3、-10 / 3 = -3），并且不允许使用乘法、除法和取余运算符。

「不许用除法」这条约束基本上把可用工具限死了：只剩加减、比较和移位。既然只能做加减，最朴素的做法就是不停地从被除数里减去除数、数减了多少次；而移位可用意味着「一次减掉除数的 $2^k$ 倍」是允许的，这是把线性次数压成对数次数的唯一入口。

另一条关键约束是结果必须仍是 32 位整数。$-2^{31}$ 没有对应的正数，所以「先取绝对值再算」这个直觉写法在 a = -2^{31} 时立刻溢出。反过来，负数区间比正数区间多容纳一个值，因此把两个操作数统一成负数再运算才是安全的方向。

边界要单独想清楚的有四处：除数为 $1$ 时商就是被除数本身，此时若被除数是 $-2^{31}$，任何「先转正」的写法都会炸；$-2^{31} / -1$ 的真实答案 $2^{31}$ 超出 int 上限，题目要求截断成 $2^{31}-1$；被除数为 $0$ 时应该直接得 $0$；以及符号只取决于两个操作数是否同号，与绝对值的计算过程无关。

解法：数学推导

核心思路

暴力做法是把 a 反复减去 b，减一次商加一。正确但会超时：当 a 是 $2^{31}-1$ 而 b 是 $1$ 时，循环要跑二十多亿次。瓶颈非常明确——每轮只削掉一个 b，进展太慢。

观察点在于：如果 b 能减一次，那么 2b 未必不能减；如果 2b 也能减，那 4b 还可以试。也就是说，我们可以在每一轮里先把除数不断翻倍，找到不超过当前被除数的最大的 $b \times 2^k$，一次性减掉它，同时给商加上 $2^k$。这等价于把商写成二进制、从高位往低位一位一位确定，于是外层轮数从 $O(a/b)$ 降到了 $O(\log a)$。

符号问题用「统一到负数域」解决。把 a、b 都变成非正数（a > 0 时取 -a，b 同理），这个变换对任何 32 位整数都不会溢出，因为负半轴容得下正半轴的全部取值。此后所有比较都在负数域进行：a <= b 表示「|a| >= |b|，还能继续减」，a <= (x << 1) 表示「|a| >= 2|x|，翻倍后仍不超过被除数」。

这套写法要维持的不变量是：answer 已经累计的商，恰好对应「原始 |a| 中已经被减掉的那部分」，而当前的 a 是尚未处理的余量，且余量的绝对值严格小于已减掉的量所对应的那一步。循环在余量绝对值小于 |b| 时终止，此时 answer 就是完整的商的绝对值，最后按同号与否决定正负。

翻倍时还需要一道护栏：x <<= 1 在 x 小于 $-2^{30}$ 时会溢出，所以循环条件里必须先卡住 x >= Integer.MIN_VALUE >> 1。

解题步骤

  • 先摘出除数为 $1$ 的情况，直接返回 a。这一步不是优化而是正确性保证：只有 |b| == 1 时商才可能达到 $2^{31}$，把 b == 1 提前返回后，剩下唯一会溢出的组合就只有 $-2^{31} / -1$。
  • 再摘出 a == Integer.MIN_VALUE && b == -1，返回 Integer.MAX_VALUE。这是题目明确规定的截断行为，也是上一条留下的唯一漏网之鱼。
  • 记录符号 sign，条件是两数同正或同负。必须在改动 a、b 之前记，因为下一步就要把它们的符号抹平。
  • 把 a、b 统一成非正数。方向选负而不是正，是因为 $-2^{31}$ 取正会溢出，而任何正数取负都安全。
  • 外层循环条件 a <= b：在负数域里这表示余量的绝对值还不小于除数，商还能继续增长。
  • 内层把 x 从 b 开始翻倍，条件是 x >= Integer.MIN_VALUE >> 1（防止移位溢出）且 a <= (x << 1)（翻倍后绝对值仍不超过余量）。同步把 cnt 也翻倍，cnt 始终等于 x 是 b 的多少倍。
  • 一次性结算：answer += cnt，a -= x。因为 x 是负数，a -= x 实际上在把余量往零的方向拉。
  • 按 sign 返回 answer 或 -answer。答案变量全程记录的是商的绝对值，符号只在最后一次性贴上去。

以 a = 10, b = 3 走一遍：b != 1 且不是 $-2^{31}/-1$，sign = true（同为正），取负后 a = -10、b = -3、answer = 0。第一轮外层：-10 <= -3 成立，x = -3、cnt = 1；内层判断 -10 <= -6 成立，于是 x = -6、cnt = 2；再判断 -10 <= -12 不成立，内层退出。结算 answer = 2，a = -10 - (-6) = -4。第二轮外层：-4 <= -3 成立，x = -3、cnt = 1；内层判断 -4 <= -6 不成立，直接退出。结算 answer = 3，a = -4 - (-3) = -1。第三轮外层：-1 <= -3 不成立，循环结束。sign 为真，返回 3。整个过程只做了两轮外层，而不是朴素解法的三次减法——差距在 a 很大时会指数级放大。

代码实现

class Solution {
    public int divide(int a, int b) {
        // 除数为 1 时商就是 a 本身，提前返回可以避开 a = MIN_VALUE 的溢出。
        if (b == 1) {
            return a;
        }
        // 唯一超出 int 上界的组合，按题意截断。
        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }

        boolean sign = (a > 0 && b > 0) || (a < 0 && b < 0);
        // 统一到负数域：负半轴容得下正半轴的全部取值，取负不会溢出。
        a = a > 0 ? -a : a;
        b = b > 0 ? -b : b;

        int answer = 0;
        while (a <= b) {
            int x = b;
            int cnt = 1;
            // 先卡住移位溢出，再判断翻倍后是否仍不超过剩余的被除数。
            while (x >= (Integer.MIN_VALUE >> 1) && a <= (x << 1)) {
                x <<= 1;
                cnt <<= 1;
            }
            answer += cnt;
            a -= x;
        }

        return sign ? answer : -answer;
    }
}

func divide(a int, b int) int {
    if b == 1 {
        return a
    }
    if a == math.MinInt32 && b == -1 {
        return math.MaxInt32
    }

    sign := (a > 0 && b > 0) || (a < 0 && b < 0)
    if a > 0 {
        a = -a
    }
    if b > 0 {
        b = -b
    }
    answer := 0

    for a <= b {
        x := b
        cnt := 1
        for x >= (math.MinInt32>>1) && a <= (x<<1) {
            x <<= 1
            cnt <<= 1
        }
        answer += cnt
        a -= x
    }

    if sign {
        return answer
    }
    return -answer
}

复杂度分析

  • 时间复杂度：$O(\log^2 a )$。外层每轮至少把余量减半，所以最多 $32$ 轮；每轮内层的翻倍次数也不超过 $32$ 次。凭的是「一次减掉 $b \times 2^k$」把线性的减法次数压成了二进制位数。
  • 空间复杂度：$O(1)$。全程只用 sign、answer、x、cnt 几个标量，没有任何随输入规模增长的结构。

关键点总结

  • 「不许用乘除」的题面几乎总是在暗示倍增：把「减一个」升级成「减 $2^k$ 个」，是这类题从 $O(n)$ 到 $O(\log n)$ 的固定套路。
  • 处理有符号整数的绝对值时，统一到负数域比统一到正数域更安全，因为补码的负半轴比正半轴多一个数。这条原则在快速幂、取绝对值、反转整数等题里都能复用。
  • 任何会翻倍的变量，翻倍前必须先检查是否越过阈值的一半。护栏写在循环条件里，而不是翻倍之后补救。
  • 符号和绝对值分离处理：中间过程只算绝对值，符号在入口记录、出口贴上，能显著减少分支。
  • 面试视角：面试官问这道题时，真正想看的是你能否主动说出「哪些输入会溢出」。开口就把 b == 1、MIN_VALUE / -1 两个特判点出来，比写完代码再被追问要加分得多；如果面试官进一步问「为什么不用 long 兜底」，标准回答是——某些语言/平台没有更宽的整型可用，负数域技巧才是通用解。

易错点总结

  • 错误写法：a = Math.abs(a); b = Math.abs(b);。输入 a = -2147483648 时 Math.abs 原样返回负数，后续所有比较语义翻转，结果直接算错。
  • 错误写法：漏掉 a == Integer.MIN_VALUE && b == -1 的特判。输入 a = -2147483648, b = -1 时 cnt 会翻倍到 $2^{31}$ 溢出成负数，answer 跟着变成 $-2147483648$，sign 为真直接返回它，而正确答案是 2147483647。
  • 错误写法：删掉 b == 1 的提前返回。这条特判的作用是让「商一定落在 int 范围内」这个前提成立——|b| == 1 是商可能达到 $2^{31}$ 的唯一场景。删掉后某些用例靠两次溢出互相抵消碰巧还对，但这属于未定义的侥幸，不能当作可以省略的理由。
  • 错误写法：内层条件只写 a <= (x << 1)，不加溢出护栏。输入 a = -2147483648, b = -1（若未提前特判）时 x 会从 $-2^{30}$ 翻到溢出，比较结果随机，循环可能永不终止。
  • 错误写法：把 sign 的计算放在取负之后。此时 a、b 都已是非正数，sign 恒为 true，-10 / 3 会返回 3。
  • 错误写法：外层条件写成 a < b。输入 a = 3, b = 3 时，取负后 -3 < -3 不成立，循环一次都不进，返回 0 而不是 1。
  • 错误写法：内层退出后忘记把 cnt 累加而只加 $1$。10 / 3 第一轮减掉的是 $6$，商却只加了 $1$，最终返回 2。
  • 错误写法：用 a += x 代替 a -= x。x 已经是负数，加法会让余量越走越远，10 / 3 会陷入死循环。
  • 错误写法：先返回 -answer 再判断符号，或把 sign 判成「异号为真」。-10 / -3 会返回 -3。

相似题目

题目 难度 考察点
29. 两数相除 中等 与本题同题，官方难度标为中等，溢出边界的问法更严格
面试题 16.09. 运算 中等 只给加法，要求自造减、乘、除，倍增思路要同时用在三个方向
50. Pow(x, n) 中等 倍增用在乘法侧，指数为负与 $n = -2^{31}$ 是对应的溢出坑
372. 超级次方 中等 指数以数组形式给出，倍增要配合逐位递推和取模
231. 2 的幂 简单 只判断是否恰为 $2^k$，用 n & (n - 1) 一步出结果