力扣热题100实战 | 第29期：两数相除——位运算与倍增法的巅峰对决

力扣热题100实战 | 第29期：两数相除——位运算与倍增法的巅峰对决

• • 前言
  • 一、题目：不靠乘除，如何做除法？
  • • 关键点解读
  • 二、第一反应：减法模拟（直观但低效）
  • • 核心思想
    • 代码实现
    • 复杂度分析
    • 这段代码的问题在哪？
  • 三、核心解法一：倍增法（指数搜索）
  • • 思想来源
    • 算法步骤
    • 为什么用负数不用正数？
    • 图解流程
    • 代码实现
    • 代码解析
    • 复杂度分析
  • 四、核心解法二：位运算优化（面试终极答案）
  • • 思想来源
    • 算法步骤
    • 图解流程
    • 代码实现
    • 代码解析
    • 复杂度分析
  • 五、三种解法巅峰对决
  • • 面试建议
  • 六、细节剖析：面试官真正关心的问题
  • • Q1：为什么用负数不用正数？Integer.MIN_VALUE 取绝对值会怎样？
    • Q2：左移运算会不会溢出？怎么防止？
    • Q3：为什么 while 循环中用 `dvd <= dvs` 而不是 `dvd >= dvs`？
    • Q4：如何处理唯一的溢出情况 `-2³¹ / -1`？
    • Q5：为什么不能用 `Math.abs()` 直接取绝对值？
  • 七、面试官追问进阶版
  • • 追问1：如何用二分查找实现这道题？
    • 追问2：如何用对数函数实现？（奇技淫巧）
    • 追问3：如果要求实现 `%` 运算（取余），怎么改？
    • 追问4：如何测试代码的正确性？
  • 八、实际开发：这道题到底有什么用？
  • • 场景1：嵌入式系统
    • 场景2：大数运算库
    • 场景3：性能优化
    • 场景4：理解计算机底层
    • 场景5：面试考察代码严谨性
  • 九、总结：从一道题到一类题
  • 附录：思考题

不用乘、除、取模，如何实现除法？这道题看似简单，实则是位运算和边界处理的试金石。它教会我们：当基础运算被禁止时，如何用更底层的操作实现高级运算。

前言

你好，我是@礼拜天没时间。

上一期我们学习了“找出字符串中第一个匹配项的下标”（第28题），掌握了KMP算法的精髓。这一期，我们来解一道非常特殊的题目——两数相除（LeetCode 第29题）。

这道题的特殊之处在于：它禁止使用我们习以为常的乘法、除法和取模运算，逼着我们去思考更底层的实现方式。这就像让你用加减法实现计算器——看似原始，却能让你真正理解计算机是如何做除法的。

很多同学第一次接触这道题时，要么被边界条件折磨得焦头烂额，要么写出来的代码虽然能跑但讲不清楚原理。今天，我希望能带你从最朴素的减法模拟出发，一步步推导出最优的位运算解法。

一、题目：不靠乘除，如何做除法？

先看题目描述（LeetCode 第29题）：

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

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

整数除法的结果应当**截去（truncate）**其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2。

注意： 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2³¹, 2³¹ − 1]。本题中，如果除法结果溢出，则返回 2³¹ − 1。

示例 1：

输入：dividend = 10, divisor = 3
输出：3
解释：10/3 = truncate(3.33333..) = 3

示例 2：

输入：dividend = 7, divisor = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2

示例 3：

输入：dividend = -2147483648, divisor = -1
输出：2147483647
解释：-2³¹ / -1 = 2³¹，但 2³¹ 超出了 int 范围，所以返回 2³¹-1

关键点解读

二、第一反应：减法模拟（直观但低效）

当我第一次看到这道题，我的第一反应是：除法不就是减法的重复吗？ 比如 10/3，就是不断用 10 减去 3，看能减多少次。

核心思想

代码实现

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);

// 转换为正数——这里有坑！Integer.MIN_VALUE转正数会溢出
long dvd = Math.abs((long) dividend);
long dvs = Math.abs((long) divisor);

int result = 0;

// 减法模拟
while (dvd >= dvs) {
dvd -= dvs;
result++;
}

return negative ? –result : result;
}
}

复杂度分析

• 时间复杂度：O(n) —— n 是商的大小，最坏情况下如 Integer.MAX_VALUE / 1，需要循环 21亿次，绝对超时
• 空间复杂度：O(1) —— 只用了常数变量

这段代码的问题在哪？

三、核心解法一：倍增法（指数搜索）

思想来源

既然逐个减太慢，我们能不能每次减去除数的倍数？就像我们手算除法时，不是一位一位地减，而是先看能减去除数的多少倍。

例如 100 / 3：

• 3 × 32 = 96，小于100，可以减96
• 100 – 96 = 4，剩下4
• 4 / 3 = 1，总共 32 + 1 = 33

这个过程就是倍增法——用指数级增长的方式快速逼近商 。

算法步骤

为什么用负数不用正数？

因为 Integer.MIN_VALUE 取绝对值会溢出 。但如果我们全部转为负数，Integer.MIN_VALUE 仍然是 -2147483648，不会溢出。这是处理32位整数边界的常用技巧 。

图解流程

以 dividend = 100, divisor = 3 为例（先忽略符号）：

第1轮：

• 当前被除数 = 100
• 除数3不断翻倍：3, 6, 12, 24, 48, 96, 192（超过100停止）
• 最大不超过100的是96，对应翻了 2⁵ = 32 倍
• 结果 += 32，被除数 -= 96 → 剩余 4

第2轮：

• 当前被除数 = 4
• 除数3不断翻倍：3, 6（超过4停止）
• 最大不超过4的是3，对应翻了 2⁰ = 1 倍
• 结果 += 1，被除数 -= 3 → 剩余 1

第3轮：

• 当前被除数 = 1 < 除数3，结束

最终结果 = 32 + 1 = 33 ✅

代码实现

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);

// 全部转为负数，避免 Integer.MIN_VALUE 取绝对值溢出
int dvd = dividend > 0 ? –dividend : dividend;
int dvs = divisor > 0 ? –divisor : divisor;

int result = 0;

// 倍增法
while (dvd <= dvs) { // 注意是负数比较，所以是 <=
int temp = dvs;
int multiple = 1;

// 不断翻倍，直到超过当前被除数
// 注意溢出判断：temp << 1 不能小于 Integer.MIN_VALUE/2
while (temp >= Integer.MIN_VALUE >> 1 && dvd <= temp << 1) {
temp <<= 1;
multiple <<= 1;
}

dvd -= temp;
result += multiple;
}

return negative ? –result : result;
}
}

代码解析

复杂度分析

• 时间复杂度：O(log n × log n) —— 外层循环每次至少减少一半的被除数，内层循环每次翻倍，最多30次
• 空间复杂度：O(1) —— 只用了常数变量

四、核心解法二：位运算优化（面试终极答案）

思想来源

上面的倍增法已经很快了，但我们可以用预处理的方式进一步优化——提前计算除数的所有倍数（2的幂次倍），然后从大到小尝试减去 。

这就像我们手算二进制除法：把除数左移0位、1位、2位…直到超过被除数，然后从高位到低位判断。

算法步骤

图解流程

以 dividend = 100, divisor = 3 为例：

预处理 powers（以正数示意，实际用负数）：

• powers[0] = 3 × 1 = 3，对应倍数 1
• powers[1] = 3 × 2 = 6，对应倍数 2
• powers[2] = 3 × 4 = 12，对应倍数 4
• powers[3] = 3 × 8 = 24，对应倍数 8
• powers[4] = 3 × 16 = 48，对应倍数 16
• powers[5] = 3 × 32 = 96，对应倍数 32
• powers[6] = 3 × 64 = 192，超过100，停止

从大到小遍历：

• i=5, powers[5]=96 ≤ 100 → 减去96，结果+=32，剩余4
• i=4, powers[4]=48 > 4 → 跳过
• i=3, powers[3]=24 > 4 → 跳过
• i=2, powers[2]=12 > 4 → 跳过
• i=1, powers[1]=6 > 4 → 跳过
• i=0, powers[0]=3 ≤ 4 → 减去3，结果+=1，剩余1

最终结果 = 32 + 1 = 33 ✅

代码实现

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 dvd = dividend > 0 ? –dividend : dividend;
int dvs = divisor > 0 ? –divisor : divisor;

// 预处理倍数数组
int[] powers = new int[32]; // 32位整数最多31次左移
int[] multiples = new int[32];

powers[0] = dvs;
multiples[0] = 1;

int i = 0;
// 预处理：不断翻倍，直到接近 Integer.MIN_VALUE/2
while (i < 31 && powers[i] >= Integer.MIN_VALUE >> 1) {
powers[i + 1] = powers[i] << 1;
multiples[i + 1] = multiples[i] << 1;
i++;
}

int result = 0;

// 从大到小遍历
for (int j = i; j >= 0; j—) {
if (dvd <= powers[j]) {
dvd -= powers[j];
result += multiples[j];
}
}

return negative ? –result : result;
}
}

代码解析

复杂度分析

• 时间复杂度：O(log n) —— 预处理需要 O(log n)，遍历也需要 O(log n)
• 空间复杂度：O(log n) —— 存储倍数数组，但常数大小（最多32）

五、三种解法巅峰对决

面试建议

优先掌握位运算预处理法，因为它最接近计算机底层实现，且效率最高 。

倍增法作为备选：如果面试官要求不能用额外数组，可以给出倍增法。

减法模拟作为思路铺垫：可以先讲减法模拟，然后自然引出“如何优化”到倍增法。

六、细节剖析：面试官真正关心的问题

Q1：为什么用负数不用正数？Integer.MIN_VALUE 取绝对值会怎样？

答案：Integer.MIN_VALUE = -2147483648，它的绝对值是 2147483648，超出了 int 的最大值 2147483647，所以直接取绝对值会溢出 。如果全部转为负数，Integer.MIN_VALUE 仍然是 -2147483648，不会溢出 。

Q2：左移运算会不会溢出？怎么防止？

答案：会。在左移之前需要判断当前值是否小于 Integer.MIN_VALUE >> 1，如果小于，左移后就会溢出 。

// 安全左移的判断条件
if (temp >= Integer.MIN_VALUE >> 1) {
temp <<= 1; // 安全
}

Q3：为什么 while 循环中用 dvd <= dvs 而不是 dvd >= dvs？

答案：因为我们将所有数转成了负数。负数比较时，“更小”意味着绝对值更大。例如 -10 <= -3 表示 -10 的绝对值更大，也就是被除数还足够大，可以继续减 。

Q4：如何处理唯一的溢出情况 -2³¹ / -1？

答案：在函数开头单独判断 ：

if (dividend == Integer.MIN_VALUE && divisor == –1) {
return Integer.MAX_VALUE;
}

Q5：为什么不能用 Math.abs() 直接取绝对值？

答案：Math.abs(Integer.MIN_VALUE) 返回的仍然是 Integer.MIN_VALUE，因为溢出了 。所以必须用 long 转换或者用负数域处理。

七、面试官追问进阶版

追问1：如何用二分查找实现这道题？

思路：商一定在 [0, dividend] 范围内，可以用二分查找逼近商。需要一个 mul 函数（倍增乘法）来判断 mid * divisor 与 dividend 的关系 。

// 倍增乘法实现
long mul(long a, long k) {
long ans = 0;
while (k > 0) {
if ((k & 1) == 1) ans += a;
k >>= 1;
a += a;
}
return ans;
}

时间复杂度 O(log n × log n)，空间 O(1) 。

追问2：如何用对数函数实现？（奇技淫巧）

思路：利用数学公式 a / b = exp(log(a) – log(b))，然后用 floor 取整 。

public int divide(int dividend, int divisor) {
if (dividend == Integer.MIN_VALUE && divisor == –1) return Integer.MAX_VALUE;
double logResult = Math.log(Math.abs((double) dividend)) – Math.log(Math.abs((double) divisor));
double result = Math.exp(logResult);
int ans = (int) Math.floor(result);
return (dividend > 0) == (divisor > 0) ? ans : –ans;
}

但这种方法有浮点精度问题，不推荐在面试中使用。

追问3：如果要求实现 % 运算（取余），怎么改？

思路：先计算出商，然后用 dividend – divisor * quotient 得到余数。注意符号处理：余数的符号与被除数相同。

追问4：如何测试代码的正确性？

思路：

八、实际开发：这道题到底有什么用？

很多读者会问：“手写除法，实际工作中哪用得到？”

其实它的思想无处不在：

场景1：嵌入式系统

在缺乏硬件除法器的嵌入式芯片上，必须用软件实现除法，用的就是这种移位减法算法。

场景2：大数运算库

在实现 BigInteger 时，除法不能用 CPU 指令直接完成，需要手写除法算法。

场景3：性能优化

在某些特殊场景下，手写位运算可能比硬件除法更快（虽然现代CPU已优化得很好）。

场景4：理解计算机底层

这道题能帮你理解计算机是如何做除法的——计算机根本不会做除法，它只会做加法和移位 。

场景5：面试考察代码严谨性

这道题是考察边界处理和溢出意识的绝佳题目，能写对的人往往代码功底扎实。

九、总结：从一道题到一类题

回顾一下，我们从两数相除学到了什么：

力扣热题100的第二十九题，不是为了难住你，而是为了告诉你：当高级运算被禁止时，我们要回到最基本的加法和移位，用智慧和技巧重新搭建出高级运算。这正是计算机底层工作的魅力所在。

下一期预告：《串联所有单词的子串》——滑动窗口与哈希表的终极结合

附录：思考题

看完这篇文章，你可以试着回答：

欢迎在评论区留下你的思考！