LeetCode 29. 两数相除
题目描述
✅ 29. 两数相除
题意分析
给定两个 32 位有符号整数，返回被除数除以除数后的整数商，舍弃小数部分，方向是向零截断。除数保证不为零，计算过程中不能使用乘法、除法或取余，也不能依赖更宽的整数类型。
结果仍需落在 32 位有符号范围内；唯一会超出上界的输入组合是
INT_MIN / -1，需要返回INT_MAX。正负号与商的大小可以分开处理，但最小负数不能先直接取绝对值。
解法：负数域二进制长除法
核心思路
[!blue]
逐次减去除数会使运行次数与商成正比。改为从高到低尝试除数的二进制倍数，每次决定商的一位，就只需检查固定的 32 位；倍数用左移得到，商也按对应的二进制位累加。
32 位负数比正数多容纳一个绝对值：
INT_MIN无法取正，但任何正数都能安全取负。因此先把正操作数转为负数，用remain保存尚未减去的负余量，value保存负除数，quotient也按非正数累计。原来是否异号单独保存。尝试第
bit位时，负倍数是chunk = value << bit。为了先避免溢出，要求value >= (INT_MIN >> bit)；右侧是该位允许的最小负除数，过小就不能左移。检查必须发生在移位之前，不能先得到已经溢出的倍数再判断。若
remain <= chunk，剩余量的绝对值足以减去这个倍数，就执行remain -= chunk，并向负商加入(-1 << bit)。负数越小绝对值越大，所以这里的大小方向与正数除法相反；减去负倍数后，remain会向零靠近。从高位向低位选择，已跳过或已选过的更高位都不需再考虑：选过某个倍数后，余量不足以再容纳它，否则前一个更大的倍数就应已被选中。最后余量绝对值小于除数，负商的绝对值正好是整数商，剩余部分直接舍弃。
异号时保留负商，同号时取反。最小负数除以负一已经提前处理，所以需要取反的结果都在可表示范围内；零和其他符号组合也能沿同一流程得到向零截断的商。
解题步骤
- 特判
INT_MIN / -1，再记录两个操作数是否异号。- 将正操作数取负，初始化负余量、负除数和零商。
- 从第 31 位到第 0 位，先检查
value >= (INT_MIN >> bit)；不安全的倍数直接跳过。- 对安全倍数，若
remain <= chunk，减去该倍数并把对应的负二进制权值加入商。- 异号返回负商，同号返回其相反数。
代码实现
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);
int remain = dividend > 0 ? -dividend : dividend;
int value = divisor > 0 ? -divisor : divisor;
int quotient = 0;
for (int bit = 31; bit >= 0; bit--) {
// 先确认负数左移仍可表示，不能溢出后再判断。
if (value < (Integer.MIN_VALUE >> bit)) {
continue;
}
int chunk = value << bit;
// 负数越小绝对值越大，余量足够才减去这个倍数。
if (remain <= chunk) {
remain -= chunk;
quotient += (-1 << bit);
}
}
return negative ? quotient : -quotient;
}
}
func divide(dividend int, divisor int) int {
const minInt32 = -1 << 31
const maxInt32 = 1<<31 - 1
if dividend == minInt32 && divisor == -1 {
return maxInt32
}
negative := (dividend < 0) != (divisor < 0)
remain, value := int32(dividend), int32(divisor)
if remain > 0 {
remain = -remain
}
if value > 0 {
value = -value
}
quotient := int32(0)
for bit := 31; bit >= 0; bit-- {
// 先确认负数左移仍可表示，不能溢出后再判断。
if value < (int32(minInt32) >> bit) {
continue
}
chunk := value << bit
// 负数越小绝对值越大，余量足够才减去这个倍数。
if remain <= chunk {
remain -= chunk
quotient += int32(-1) << bit
}
}
if negative {
return int(quotient)
}
return int(-quotient)
}
复杂度分析
- 时间复杂度：$O(1)$，固定检查 32 个商位，每轮仅常数次运算。
- 空间复杂度：$O(1)$，只维护固定数量的 32 位整数。
关键点总结
[!green]
- 负数域能直接容纳最小整数，整个过程无需绝对值或更宽类型。
- 先检查可表示范围，再左移；移位后才判断无法补救溢出。
- 负数比较方向与绝对值相反，
remain <= chunk才表示能减去这个倍数。- 负商直接累加负权值，只有确定正结果可表示时才取反。
易错点总结
[!yellow]
- 不能对
INT_MIN取正的绝对值，应该把正数转为负数，在负数域计算。- 负除数左移前必须检查范围，溢出后得到的值已经无法代表正确倍数。
- 可减判断应包含相等，余量恰好等于倍数时也必须选取该商位。
- 正负号取决于两个操作数是否异号，不能只看被除数。
- 负数商舍弃小数部分是向零截断，不能按向负无穷取整去调整结果。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 50. Pow(x, n) | 中等 | 同样按二进制拆分次数并成倍处理，原题通过平方加速幂，本题通过倍增除数确定商。 |