29. 两数相除

鲁迅说过，人生最大的快乐就在不断的求知，不断地进步，在刷 LeetCode 的过

程中强化自己的基础知识，二哥的 LeetCode 刷题笔记正给了我这样进步的快

乐。

题意

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和

取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为

8 ，-2.7335 将被截断至 -2 。

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

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 $ [−2^{31}, 2^{31} − 1]

$ 。本题中，如果商严格大于 $ 2^{31} − 1 $ ，则返回 $ 2^{31} − 1 $ ；如果商 严格小于 $

-2^{31} $ ，则返回 $ -2^{31} $ 。

难度

中等

示例

输入: dividend = 10, divisor = 3

输出: 3

解释: 10/3 = 3.33333.. ，向零截断后得到 3 。

输入: dividend = 7, divisor = -3

输出: -2

解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。

分析 1

题目要求不能用除法（/），也不能用乘法（*），还有 “取余（%）”，如果我们偏要用除

法会怎么样呢？

class Solution {

public int divide(int dividend, int divisor) {

// 直接使用除法计算结果

long result = (long) dividend / divisor;

// 处理溢出情况

if (result > Integer.MAX_VALUE) {

return Integer.MAX_VALUE;

}

if (result < Integer.MIN_VALUE) {

return Integer.MIN_VALUE;

 }

return (int) result;

}

}

来看一下运行结果：

029.%E4%B8%A4%E6%95%B0%E7%9B%B8%E9%99%A4-20240221182536.png

竟然也击败了 100% 的用，哈哈哈 ? ?

其实有时候我们真解不出来的话，多多少少先把答案写上去，至于能不能得分，再说呗。

分析 2

题目要求不能用除法，不过我们处理溢出情况的写法，后面还是要用到的，尤其是 (long)

dividend 这个强转的处理，其实就考察了基本数据类型的转换问题，包括最后返回的

(int) result，都是很细节的问题，但却很重要。

那既然不能用除法，我们应该怎么去计算两数相除呢？

用减法。

除法基本上是减法的逆运算，它表示将一个数（被除数）分成几个相等的部分（除数）

时，可以得到多少个这样的部分（商）。如果用减法来实现除法，本质上是在问：“我可

以从被除数中减去多少次除数？”每减去一次，就相当于得到了一个单位的商。

假设我们要计算 dividend / divisor = quotient（被除数 / 除数 = 商），其中 dividend 和

divisor 是已知的，我们要找到 quotient。

①、初始化计数器：设置一个计数器 count，初始值为 0。这个计数器将用来记录我们能

从被除数中减去多少次除数。

②、循环减除数：只要被除数 dividend 大于或等于除数 divisor，就从被除数中减去除

数，并且计数器 count 加一。

while (dividend >= divisor) {

dividend -= divisor;

count++;

}

③、处理剩余部分：当被除数小于除数时，循环结束。此时，count 的值就是整数除法的

结果（商），而此时的 dividend 是除法的余数。

假设我们要计算 10 / 3：

1. 初始时，dividend = 10，divisor = 3，count = 0。

2. 10 >= 3，执行减法 10 - 3 = 7，count = 1。

3. 7 >= 3，再次执行减法 7 - 3 = 4，count = 2。

4. 4 >= 3，再次执行减法 4 - 3 = 1，count = 3。

5. 此时，1 < 3，循环结束，count = 3 是商，1 是余数。

我们来试一下，直接用 ACM 的模式在 Intellij IDEA 中打印结果：

class Main02901 {

public static void main(String[] args) {

Solution02901 solution = new Solution02901();

System.out.println(solution.divide(10, 3));

System.out.println(solution.divide(7, -3));

System.out.println(solution.divide(0, 1));

System.out.println(solution.divide(1, 1));

System.out.println(solution.divide(1, 0));

System.out.println(solution.divide(-2147483648, -1));

}

}

class Solution02901 {

public int divide(int dividend, int divisor) {

// 处理特殊情况

if (dividend == Integer.MIN_VALUE && divisor == -1) {

return Integer.MAX_VALUE;

}

// 符号处理

boolean negative = (dividend < 0) ^ (divisor < 0);

long ldividend = Math.abs((long)dividend);

long ldivisor = Math.abs((long)divisor);

long result = 0;

while (ldividend >= ldivisor) {

ldividend -= ldivisor;

result++;

}

return negative ? (int)-result : (int)result;

}

}

很遗憾，前 5 个测试用例都是可以顺利通过的，但最后 1 个测试用例耗时会特别长，因为

要计算 2147483648 / 1 次，这个数太大了，所以我们要想办法优化一下。

优化减法实现除法的关键在于减少需要执行的减法操作次数，对吧？

我们可以结合减法和倍增思想，每次减去 divisor 的倍数，这样就可以减少减法的次数。

• 初始时，令一个临时除数等于除数，每次尝试从被除数中减去临时除数。

• 如果可以减去，更新被除数（减去临时除数），临时除数倍增（乘以 2），同时记录

下减去的次数。

• 如果不可以减去，则临时除数回退到除数，继续尝试减去直到被除数小于除数。

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

long ldividend = Math.abs((long) dividend);

long ldivisor = Math.abs((long) divisor);

long result = 0;

while (ldividend >= ldivisor) {

long tempDivisor = ldivisor, multiple = 1;

while (ldividend >= tempDivisor + tempDivisor) {

tempDivisor += tempDivisor; // 加倍除数

multiple += multiple; // 记录加倍次数

}

ldividend -= tempDivisor; // 减去加倍后的除数

result += multiple; // 累加倍数

}

return negative ? (int)-result : (int)result;

}

}

内层 while 循环，确定能够从被除数中减去的最大的除数的倍数。

这个循环通过不断地加倍除数（乘以 2），寻找最接近且不超过被除数的那个除数的倍

数。这个过程实际上是在模拟除法的过程，尝试找到一个合适的倍数，使得除数 × 倍数 ≤

被除数，且尽可能地大。

while (ldividend >= tempDivisor + tempDivisor) {

tempDivisor += tempDivisor; // 加倍除数

multiple += multiple; // 记录加倍次数

}

• tempDivisor 从原始的除数开始，每次循环加倍（相当于 tempDivisor * 2），试图

接近但不超过 ldividend。

• multiple 记录了加倍的次数，也就是说，如果 tempDivisor 加倍了，那么 multiple 也

加倍，表示除数增加了多少倍。

外层 while 循环，使用上一个循环确定的最大倍数来更新被除数，并累加到最终结果中。

当第一个循环结束后，我们找到了最接近且不超过被除数的那个除数的倍数。然后，我们

从被除数中减去这个加倍后的除数，并将对应的倍数累加到最终结果中。如果更新后的被

除数仍然大于或等于原始除数，这个过程会重复进行。

ldividend -= tempDivisor; // 减去加倍后的除数

result += multiple; // 累加倍数

• ldividend -= tempDivisor;更新被除数，减去了找到的最大可减的加倍后的除数。

• result += multiple;将这一步中减去的除数的倍数累加到 result 中，因为这表示了我

们在这一步中“除以了多少个”除数。

来看一下运行效率，还挺高：

029.%E4%B8%A4%E6%95%B0%E7%9B%B8%E9%99%A4-20240222115508.png

分析 3

减法和倍增的另外一种变体就是使用位移（我在二哥的 Java 进阶之路里有讲过），我们

来看一下题解：

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

long ldividend = Math.abs((long)dividend);

long ldivisor = Math.abs((long)divisor);

long result = 0;

while (ldividend >= ldivisor) {

long temp = ldivisor, multiple = 1;

while (ldividend >= (temp << 1)) {

temp <<= 1;

multiple <<= 1;

}

ldividend -= temp;

result += multiple;

}

return negative ? (int)-result : (int)result;

 }

}

在二进制表示中，每向左移动一位，其实就等价于将这个数乘以 2。所以，我们可以通过

位移来实现倍增。

while (ldividend >= (temp << 1)) {

temp <<= 1;

multiple <<= 1;

}

假设 temp 的值为 3，其二进制表示为 0011（这里为了简化，只展示了四位二进制）。当

执行 temp << 1 操作时，temp 的二进制表示会向左移动一位，变为 0110，此时 temp 的

值就变成了 6。可以看到，3 * 2 = 6，这正是位左移一位的效果。

这里穿插一点补码的知识，我就不讲了，看这个视频：

补码怎么来的？

还有这个小姐姐讲的 位运算符(左移,右移,按位或，与，异或)

029.%E4%B8%A4%E6%95%B0%E7%9B%B8%E9%99%A4-20240222153351.png

题解的效率和之前一样，都是轻松击败了 100% 的用户。

029.%E4%B8%A4%E6%95%B0%E7%9B%B8%E9%99%A4-20240222153829.png

分析 4

我们还可以使用二分法来实现除法，这个方法是最优的，也是最常用的。

二分法的思路是：我们可以将除数不断地向左移位，直到它大于被除数。因为这样可以最

大限度地减小被除数，使得被除数减去除数的次数最少。

我们来看一下题解：

class Solution {

public int divide(int dividend, int divisor) {

// 处理特殊情况：Integer.MIN_VALUE 除以-1 会溢出

if (dividend == Integer.MIN_VALUE && divisor == -1) {

return Integer.MAX_VALUE;

}

// 使用异或运算确定结果的正负性，不同号为负

boolean negative = (dividend < 0) ^ (divisor < 0);

// 将被除数和除数都转换为正数，使用 long 类型避免溢出

long ldividend = Math.abs((long)dividend);

long ldivisor = Math.abs((long)divisor);

// 初始化结果变量

long result = 0;

// 从最高位开始检查，对 32 位整数而言，这是 31 位

for (int i = 31; i >= 0; i--) {

// 检查 ldividend 右移 i 位后是否仍然大于等于 ldivisor

if ((ldividend >> i) >= ldivisor) {

// 如果是，说明在 2^i 的位置上有一个 ldivisor，将 2^i 累加到结果中

result += 1L << i;

// 同时，从 ldividend 中减去 ldivisor 左移 i 位的值，即减去了 ldivisor 的 2^i 倍

ldividend -= ldivisor << i;

}

}

// 根据之前确定的正负性，返回正确的结果

return negative ? (int)-result : (int)result;

}

}

这个题解虽然没有直接采用传统的二分搜索算法框架，但它实质上利用了二分思想的核心

——每次操作都在减少搜索范围，逐步逼近目标值。

在这个问题中，目标是找到一个数 x，使得 x * divisor ≈ dividend。通过位操作，每次将

dividend 右移，实际上是在缩小搜索范围。

这个过程可以看作是对商的二进制表示的逐位确认：

• 高位到低位逼近：从 dividend 的最高位开始，逐步向下检查每一位，看在当前位上

divisor 是否能“放入”。这里，“放入”的意思是，看乘以 2^i（通过左移 i 位实现）后

的 divisor 是否不超过当前的 dividend。这相当于在二分搜索的每一步中，决定这一位

上的商是 0 还是 1。

• 动态调整搜索范围：通过不断地调整 ldividend（即减去已经确定能够放入的 divisor

的倍数），实际上是在缩小搜索范围，因为每次操作后的 ldividend 代表了尚未被除

尽的余数。

不过，题解涉及到了很多位移运算，对于新手来说，并不特别友好，所以我还是推荐大家

用减法+倍增的方法来实现除法。

总结

在数学中，加法是加减乘除的基础，减法是加法的逆运算，乘法是加法的倍增，除法是乘

法的逆运算。

两数相乘，可以用加法来实现，两数相除，可以用减法来实现，这是最基本的思路。

比如说 10/2，我们可以用 10-2-2-2-2-2=0 来实现，这样就得到了商 5。

比如说 10/3，我们可以用 10-3-3-3-1=0 来实现，这样就得到了商 3 余 1。

我想吃棒棒糖，我有 10 块钱，一根棒棒糖 3 块钱，我可以买几根棒棒糖呢？我可以用

10-3-3-3-1=0 来实现，这样就算出来了，我可以买 3 根棒棒糖，还剩 1 块钱。

?

时娃我

。在 旁 ，

小，当娃在旁

）

（

下

一

念

，

路

思

个

了

画

意

特 边， 我 还特 意 给她画 了 这个 思 路 ， 纪念 一 下 （ ? ） 。

029.%E4%B8%A4%E6%95%B0%E7%9B%B8%E9%99%A4-20240222165738.png

那关于计算机是如何实现除法的呢？这里有一个小姐姐的视频，讲的非常棒：

计算机是如何实现除法的？

029.%E4%B8%A4%E6%95%B0%E7%9B%B8%E9%99%A4-20240222162549.png

当然了，当被除数非常大，除数非常小的时候，我们要用倍增的思路来实现，这样可以减

少减法的次数，提高效率。

比如说 100/1，我们可以让除数倍增，1+1=2,2+2=4,4+4=8,8+8=16,16+16=32,32+32=64。

然后 100-64=36，就得出了第一次倍增后还剩余的被除数，再计算 36/1，我们可以让除

数继续倍增，1+1=2,2+2=4,4+4=8,8+8=16,16+16=32。

然后 36-32=4，就得出了第二次倍增后还剩余的被除数，再计算 4/1，我们可以让除数继

续倍增，1+1=2,2+2=4。

然后 4-4=0，就得出了第三次倍增后还剩余的被除数，三次倍增后的商就是

64+32+4=100。

速度是不是就快多了？

可以通过下面这个 ACM 模式的代码进行 debug 模拟：

class Main02902 {

public static void main(String[] args) {

Solution02902 solution = new Solution02902();

System.out.println(solution.divide(100, 1));

System.out.println(solution.divide(7, -3));

System.out.println(solution.divide(0, 1));

System.out.println(solution.divide(1, 1));

System.out.println(solution.divide(1, 0));

System.out.println(solution.divide(-2147483648, -1));

}

}

class Solution02902 {

public int divide(int dividend, int divisor) {

// 处理特殊情况

if (dividend == Integer.MIN_VALUE && divisor == -1) {

return Integer.MAX_VALUE;

}

boolean negative = (dividend < 0) ^ (divisor < 0);

long ldividend = Math.abs((long) dividend);

long ldivisor = Math.abs((long) divisor);

long result = 0;

while (ldividend >= ldivisor) {

long tempDivisor = ldivisor, multiple = 1;

while (ldividend >= tempDivisor + tempDivisor) {

tempDivisor += tempDivisor; // 加倍除数

multiple += multiple; // 记录加倍次数

}

ldividend -= tempDivisor; // 减去加倍后的除数

result += multiple; // 累加倍数

}

return negative ? (int)-result : (int)result;

}

}

总结一下这道题，其实用的就是一种很基础的数学思维。

力扣链接：https://leetcode.cn/problems/divide-two-integers/