029.两数相除

作者：沉默王二
发布时间：2024-02-22T17:19:05.471+0800

---

鲁迅说过，人生最大的快乐就在不断的求知，不断地进步，在刷 LeetCode 的过程中强化自己的基础知识，二哥的 LeetCode 刷题笔记正给了我这样进步的快乐。

技术派阅读地址：https://paicoding.com/column/7/29

• 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

• 这道题可以说完全重写了，给出 1 道大家完全都能掌握的题解（除法用减法去实现，再加一点倍增）。

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

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

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

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

难度

中等

示例

输入: dividend = 10, divisor = 3

解释: 10/3 = 3.33333.. ，向零截断后得到 3 。
输入: dividend = 7, divisor = -3输出: -2解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。

分析 1

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

class Solution {

    // 直接使用除法计算结果        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;    }}

来看一下运行结果：

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

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

分析 2

题目要求不能用除法，不过我们处理溢出情况的写法，后面还是要用到的，尤其是 (long) dividend 这个强转的处理，其实就考察了**基本数据类型的转换问题 **，包括最后返回的 (int) result，都是很细节的问题，但却很重要。

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

用减法。

除法基本上是减法的逆运算，它表示将一个数（被除数）分成几个相等的部分（除数）时，可以得到多少个这样的部分（商）。如果用减法来实现除法，本质上是在问：“我可以从被除数中减去多少次除数？”每减去一次，就相当于得到了一个单位的商。

假设我们要计算 dividend / divisor = quotient（被除数 / 除数 = 商），其中 dividend 和 divisor 是已知的，我们要找到 quotient。

①、初始化计数器：设置一个计数器 count，初始值为 0。这个计数器将用来记录我们能从被除数中减去多少次除数。

②、循环减除数：只要被除数 dividend 大于或等于除数 divisor，就从被除数中减去除数，并且计数器 count 加一。

while (dividend >= divisor) {

count++;}

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

假设我们要计算 10 / 3：

• 初始时，dividend = 10，divisor = 3，count = 0。
• 10 >= 3，执行减法 10 - 3 = 7，count = 1。
• 7 >= 3，再次执行减法 7 - 3 = 4，count = 2。
• 4 >= 3，再次执行减法 4 - 3 = 1，count = 3。
• 此时，1 < 3，循环结束，count = 3 是商，1 是余数。

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

class Main02901 {

    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 {

    // 处理特殊情况        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) {

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

• tempDivisor 从原始的除数开始，每次循环加倍（相当于tempDivisor * 2），试图接近但不超过 ldividend。
• multiple 记录了加倍的次数，也就是说，如果 tempDivisor 加倍了，那么 multiple 也加倍，表示除数增加了多少倍。

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

当第一个循环结束后，我们找到了最接近且不超过被除数的那个除数的倍数。然后，我们从被除数中减去这个加倍后的除数，并将对应的倍数累加到最终结果中。如果更新后的被除数仍然大于或等于原始除数，这个过程会重复进行。

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

• ldividend -= tempDivisor;更新被除数，减去了找到的最大可减的加倍后的除数。
• result += multiple;将这一步中减去的除数的倍数累加到 result 中，因为这表示了我们在这一步中“除以了多少个”除数。

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

分析 3

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

class Solution {

    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     multiple <<= 1;}

假设 temp 的值为 3，其二进制表示为 0011（这里为了简化，只展示了四位二进制）。当执行 temp << 1 操作时，temp 的二进制表示会向左移动一位，变为 0110，此时 temp 的值就变成了 6。可以看到，3 * 2 = 6，这正是位左移一位的效果。

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

**[补码怎么来的？](https://www.bilibili.com/video/BV16U4y1t7LD)**

还有这个小姐姐讲的 **[位运算符(左移,右移,按位或，与，异或)](https://www.bilibili.com/video/BV1Ha4y157MU)**

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_20.png)

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

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_21.png)

### **分析 4**

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

二分法的思路是：我们可以将除数不断地向左移位，直到它大于被除数。因为这样可以最大限度地减小被除数，使得被除数减去除数的次数最少。

我们来看一下题解：

class Solution {

        // 处理特殊情况：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 块钱。

小计，当时娃在旁边，我还特意给她画了这个思路，纪念一下（😂）。

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_22.png)

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

**[计算机是如何实现除法的？](https://www.bilibili.com/video/BV1Rg4y1w7Mm/)**

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_23.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 {

        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/](https://leetcode.cn/problems/divide-two-integers/)**

### **一步一个脚印**

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100 天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**[二哥编程星球](https://javabetter.cn/zhishixingqiu/)**的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_24.png)

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

        
        
鲁迅说过，人生最大的快乐就在不断的求知，不断地进步，在刷 LeetCode 的过程中强化自己的基础知识，二哥的 LeetCode 刷题笔记正给了我这样进步的快乐。

技术派阅读地址：[https://paicoding.com/column/7/29](https://paicoding.com/column/7/29)

- 语雀专栏地址+密码可通过星球置顶帖查看：[https://t.zsxq.com/15rEo9Pdu](https://t.zsxq.com/15rEo9Pdu)
- 这道题可以说完全重写了，给出  1 道大家完全都能掌握的题解（除法用减法去实现，再加一点倍增）。

- 增加代码注释，这样大家更容易看懂并掌握题解；
- 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
- 增加手绘图，这样大家更容易理解解题思路；
- 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
- 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
- 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
- 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

### **题意**

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

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

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

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_17.png)

### **难度**

中等

### **示例**

输入: dividend = 10, divisor = 3

解释: 10/3 = 3.33333.. ，向零截断后得到 3 。
输入: dividend = 7, divisor = -3输出: -2解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。

### **分析 1**

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

class Solution {

        // 直接使用除法计算结果        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;    }}

来看一下运行结果：

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_18.png)

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

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

### **分析 2**

题目要求不能用除法，不过我们处理溢出情况的写法，后面还是要用到的，尤其是 (long) dividend 这个强转的处理，其实就考察了**[基本数据类型的转换问题](https://javabetter.cn/basic-grammar/type-cast.html)**，包括最后返回的 (int) result，都是很细节的问题，但却很重要。

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

**用减法**。

除法基本上是减法的逆运算，它表示将一个数（被除数）分成几个相等的部分（除数）时，可以得到多少个这样的部分（商）。如果用减法来实现除法，本质上是在问：“我可以从被除数中减去多少次除数？”每减去一次，就相当于得到了一个单位的商。

假设我们要计算 dividend / divisor = quotient（被除数 / 除数 = 商），其中 dividend 和 divisor 是已知的，我们要找到 quotient。

①、**初始化计数器**：设置一个计数器 count，初始值为 0。这个计数器将用来记录我们能从被除数中减去多少次除数。

②、**循环减除数**：只要被除数 dividend 大于或等于除数 divisor，就从被除数中减去除数，并且计数器 count 加一。

while (dividend >= divisor) {

    count++;}

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

假设我们要计算 10 / 3：

- 初始时，dividend = 10，divisor = 3，count = 0。
- 10 >= 3，执行减法 10 - 3 = 7，count = 1。
- 7 >= 3，再次执行减法 7 - 3 = 4，count = 2。
- 4 >= 3，再次执行减法 4 - 3 = 1，count = 3。
- 此时，1 < 3，循环结束，count = 3 是商，1 是余数。

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

class Main02901 {

        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 {

        // 处理特殊情况        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) {

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

- tempDivisor 从原始的除数开始，每次循环加倍（相当于tempDivisor * 2），试图接近但不超过 ldividend。
- multiple 记录了加倍的次数，也就是说，如果 tempDivisor 加倍了，那么 multiple 也加倍，表示除数增加了多少倍。

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

当第一个循环结束后，我们找到了最接近且不超过被除数的那个除数的倍数。然后，我们从被除数中减去这个加倍后的除数，并将对应的倍数累加到最终结果中。如果更新后的被除数仍然大于或等于原始除数，这个过程会重复进行。

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

- ldividend -= tempDivisor;更新被除数，减去了找到的最大可减的加倍后的除数。
- result += multiple;将这一步中减去的除数的倍数累加到 result 中，因为这表示了我们在这一步中“除以了多少个”除数。

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

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_19.png)

### **分析 3**

减法和倍增的另外一种变体就是使用**[位移](https://javabetter.cn/basic-grammar/operator.html#_03%E3%80%81%E4%BD%8D%E8%BF%90%E7%AE%97%E7%AC%A6)**（我在二哥的 Java 进阶之路里有讲过），我们来看一下题解：

class Solution {

        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 multiple <<= 1;}

假设 temp 的值为 3，其二进制表示为 0011（这里为了简化，只展示了四位二进制）。当执行 temp << 1 操作时，temp 的二进制表示会向左移动一位，变为 0110，此时 temp 的值就变成了 6。可以看到，3 * 2 = 6，这正是位左移一位的效果。

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

补码怎么来的？

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

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

分析 4

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

二分法的思路是：我们可以将除数不断地向左移位，直到它大于被除数。因为这样可以最大限度地减小被除数，使得被除数减去除数的次数最少。

我们来看一下题解：

class Solution {

    // 处理特殊情况：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 块钱。

小计，当时娃在旁边，我还特意给她画了这个思路，纪念一下（😂）。

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

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

当然了，当被除数非常大，除数非常小的时候，我们要用倍增的思路来实现，这样可以减少减法的次数，提高效率。

比如说 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 {

    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/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100 天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

鲁迅说过，人生最大的快乐就在不断的求知，不断地进步，在刷 LeetCode 的过程中强化自己的基础知识，二哥的 LeetCode 刷题笔记正给了我这样进步的快乐。

技术派阅读地址：https://paicoding.com/column/7/29

• 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

• 这道题可以说完全重写了，给出 1 道大家完全都能掌握的题解（除法用减法去实现，再加一点倍增）。

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

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

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

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

难度

中等

示例

输入: dividend = 10, divisor = 3

解释: 10/3 = 3.33333.. ，向零截断后得到 3 。
输入: dividend = 7, divisor = -3输出: -2解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。

分析 1

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

class Solution {

    // 直接使用除法计算结果        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;    }}

来看一下运行结果：

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

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

分析 2

题目要求不能用除法，不过我们处理溢出情况的写法，后面还是要用到的，尤其是 (long) dividend 这个强转的处理，其实就考察了**基本数据类型的转换问题 **，包括最后返回的 (int) result，都是很细节的问题，但却很重要。

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

用减法。

除法基本上是减法的逆运算，它表示将一个数（被除数）分成几个相等的部分（除数）时，可以得到多少个这样的部分（商）。如果用减法来实现除法，本质上是在问：“我可以从被除数中减去多少次除数？”每减去一次，就相当于得到了一个单位的商。

假设我们要计算 dividend / divisor = quotient（被除数 / 除数 = 商），其中 dividend 和 divisor 是已知的，我们要找到 quotient。

①、初始化计数器：设置一个计数器 count，初始值为 0。这个计数器将用来记录我们能从被除数中减去多少次除数。

②、循环减除数：只要被除数 dividend 大于或等于除数 divisor，就从被除数中减去除数，并且计数器 count 加一。

while (dividend >= divisor) {

count++;}

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

假设我们要计算 10 / 3：

• 初始时，dividend = 10，divisor = 3，count = 0。
• 10 >= 3，执行减法 10 - 3 = 7，count = 1。
• 7 >= 3，再次执行减法 7 - 3 = 4，count = 2。
• 4 >= 3，再次执行减法 4 - 3 = 1，count = 3。
• 此时，1 < 3，循环结束，count = 3 是商，1 是余数。

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

class Main02901 {

    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 {

    // 处理特殊情况        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) {

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

• tempDivisor 从原始的除数开始，每次循环加倍（相当于tempDivisor * 2），试图接近但不超过 ldividend。
• multiple 记录了加倍的次数，也就是说，如果 tempDivisor 加倍了，那么 multiple 也加倍，表示除数增加了多少倍。

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

当第一个循环结束后，我们找到了最接近且不超过被除数的那个除数的倍数。然后，我们从被除数中减去这个加倍后的除数，并将对应的倍数累加到最终结果中。如果更新后的被除数仍然大于或等于原始除数，这个过程会重复进行。

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

• ldividend -= tempDivisor;更新被除数，减去了找到的最大可减的加倍后的除数。
• result += multiple;将这一步中减去的除数的倍数累加到 result 中，因为这表示了我们在这一步中“除以了多少个”除数。

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

分析 3

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

class Solution {

    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     multiple <<= 1;}

假设 temp 的值为 3，其二进制表示为 0011（这里为了简化，只展示了四位二进制）。当执行 temp << 1 操作时，temp 的二进制表示会向左移动一位，变为 0110，此时 temp 的值就变成了 6。可以看到，3 * 2 = 6，这正是位左移一位的效果。

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

**[补码怎么来的？](https://www.bilibili.com/video/BV16U4y1t7LD)**

还有这个小姐姐讲的 **[位运算符(左移,右移,按位或，与，异或)](https://www.bilibili.com/video/BV1Ha4y157MU)**

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_20.png)

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

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_21.png)

### **分析 4**

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

二分法的思路是：我们可以将除数不断地向左移位，直到它大于被除数。因为这样可以最大限度地减小被除数，使得被除数减去除数的次数最少。

我们来看一下题解：

class Solution {

        // 处理特殊情况：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 块钱。

小计，当时娃在旁边，我还特意给她画了这个思路，纪念一下（😂）。

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_22.png)

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

**[计算机是如何实现除法的？](https://www.bilibili.com/video/BV1Rg4y1w7Mm/)**

![图片](https://clxhxhhr.top/uploads/weblog/erge/erge_lc_image_23.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 {

    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/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100 天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412