LeetCode刷题Java版029.两数相除

作者：沉默王二
发布时间：2022-08-22T09:41:01.443+0800

---

029.两数相除

题意

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

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

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

难度

中等

示例

输入: dividend = 10, divisor = 3

解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

分析

不能用除法，也不能利用乘法，还有 “模法（%）”，我们应该怎么去计算两数相除呢？

想想我们小学时候学习的列竖式，是不是反向利用了乘法来得出除法的结果？

那时候我们凭借感觉去一个个 “试”，但是计算机没有这样的感觉，它只能通过对一个个的 0 和 1 进行操作，也就是位运算。

有没有通过其他运算符来实现 乘法 呢？

有——加法！

累加就是一种乘法，2+2+2=6 也就是 2*=6，对吧？

但是……如果我们要计算 1 * 100000000，岂不是要计算整整100000000次？！

虽然这有点夸张，但我们必须要考虑到，一个个的累加实在是太慢了……

来看看这样子的一个情形， ，换个表达方式，就是

所以说18可以被唯一的多个二的幂次方分解，原因嘛……当然是十进制都对应着唯一的二进制啦。

可这跟乘法又有什么关系呢？

要知道，二进制的每一位都是后面位数的 两倍 ，所以一个数如果要计算乘 2 的话，实际上是将它的二进制向左边移动了一位（也就是在右边补充一个 0），同理，如果要计算一个数除以 2 的话，就是反向的将它的二进制向右移动了一位（也就是直接去掉右边最后一个1/0）,这样子就能直接除以 2 并且向下取整了。

我们再来看看这样一段代码：

int quickMul(int num1,int num2){

    while(num2 != 0){        if((num2 & 1) == 1)            res += num1;        num1 = num1 + num1;        num2 >>= 1;    }    return true;}

假设num1 = 3、num2 = 7我们来模拟一遍这个过程

res    num1    num2

因为 7 的二进制为 111 所以 111 & 1 = 1,res += num1,且num2右移一位,就变成11,即3,而num1 += num13      6       3同理 3 的二进制为 11 所以 11 & 1 = 1，res += num1,num2继续右移,变成了19      12      1最终,res += num1,完成了最后一步，我们来看看答案……21     24      0

21!!!!!

wow，我们没有用到乘法，也没有计算num2次的加法，就得到了3 * 7 的结果！

而上述的操作，实际上是将num2的二进制遍历了一遍，并且每次对num1 进行自身+自身 的操作，实际上和二进制的左移是一样的，这样子就可以快速的算出了乘法的结果。

这个计算过程快吗？

这个过程就相当于在考虑一个数的二进制有多少位，等价询问：小于这个数的最大的二的幂是多少？

即，让这个式子中的最大，那么就是……,所以我们的时间复杂度是的。

好了，回到题目来，小时候，我们利用 感觉 来猜测列竖式的乘积，那么计算机能不能有一种比较类似的 感觉 呢？

有！！那就是二分！

现在已经有了乘法，怎么快速计算除法呢？

难道我们要挨个枚举去乘？这样子就会遇到 1000000 / 1的情况，效率会非常的低。

计算机每猜一个值，都是能够知道比目标值小还是大的，所以我们能不能考虑 步子迈得大一点 ？

平常，我们总说步子太大容易扯着，但是这次不一样，我们可以很快就知道我们是不是步子迈得大了，迈大了就及时调整。

二分就是一个可以让我们迈步子迈得刚刚好的方法。

我们定义一个left 和一个right，每次看一下left和right中间的值是否 刚刚好 ，如果是，那就直接结束，如果不是，那就看看是大了还是小了，小了就说明，比这个中间值更小的都不可行，一下子我们就排除掉了(right - left) / 2个答案，这样就可以迈很大一步，同理，如果大了说明比它更大的都不可行，还是可以排除(right - left) / 2个答案。

此时，你可能要问，题目要求不能使用除法了，怎么算left和right中间的值mid呢？

我们知道，mid = (left + right) / 2，回到之前提到的二进制，一个数除以 2 要怎么计算呢？

右移！

所以到此为止，我们已经完成了所有的准备工作了，接下来只要按步骤进行……

• 设置left和right为可能的答案边界——1和Integer.MAX_VALUE，为什么没有考虑负数呢？因为其实一个数除以另外一个数，答案的绝对值跟正负其实是无关的，而正负则跟二者的符号是否一致有关。
• 求出mid = (left + right) >> 1，然后利用 二进制分解 也就是上文的quickMul()方法，计算mid *divisor
• 将结果和dividend比较，观察是小了还是大了，如果小了则让left = mid + 1，大了就让right = mid - 1，因为我们不能事先就知道是不是刚刚好，但是我们知道ans * divisor <= dividend，所以我们要的就是最大的left，每次记录left的值即可，然后继续执行2步骤，直到——left == right因为如果left == right的话，二者的平均值与二者本身相等，就没有继续计算下去的必要了。

思路有了，这道题目仍然是有许多坑点，因为Leetcode的数据将每个边界条件都卡得刚刚好，而题目也说了我们只能使用32位整型，所以我们对每一个边界都要小心翼翼的去判断，看它是否超过。

class Solution {

        int res = 0;        while(num2 != 0){            if((num2 & 1) == 1){                if(res < com - num1)                    return false;                res += num1;            }            if(num2 != 1){                if(num1 < com - num1)                    return false;                num1 = num1 + num1;            }            num2 >>= 1;        }        return true;    }    public int divide(int dividend, int divisor) {        if(divisor == 0)            return 0;        if(dividend == Integer.MIN_VALUE){            if(divisor == 1)                return Integer.MIN_VALUE;            if(divisor == -1)                return Integer.MAX_VALUE;        }        if (divisor == Integer.MIN_VALUE) {            return dividend == Integer.MIN_VALUE ? 1 : 0;        }        if (dividend == Integer.MAX_VALUE && divisor == 1)            return dividend;        boolean rev = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);        dividend = -Math.abs(dividend);        divisor = -Math.abs(divisor);        int lef = 1,rig = Integer.MAX_VALUE;        int ans = 0;        while(lef <= rig){            int mid = lef + ((rig - lef) >> 1);            if(quickMul(divisor, mid, dividend)){                ans = mid;                lef = mid + 1;            }            else                rig = mid - 1;        }        return rev ? -1 * ans :  ans;    }}

代码中将两个数都转化成了负数，其实是为了拿到更大的范围来方便我们的判断，因为如果以0为分界点，32位整型能表示的负数要比正数多1，所以我们就将二者都转化为负数。

总结

本题考察了两个知识点——二分和二进制拆分，二者都跟 2 有密不可分的关系，实际上是和计算机有密不可分的关系，因为计算机是由一个个的1和0来组成的，所以我们在学习算法的时候，要能一步步的走向计算机的底层，学习计算机最精华的内容，才能够在解题的时候举一反三。

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

一步一个脚印

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

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 670 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

029.两数相除

题意

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

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

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

难度

中等

示例

输入: dividend = 10, divisor = 3

解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

分析

不能用除法，也不能利用乘法，还有 “模法（%）”，我们应该怎么去计算两数相除呢？

想想我们小学时候学习的列竖式，是不是反向利用了乘法来得出除法的结果？

那时候我们凭借感觉去一个个 “试”，但是计算机没有这样的感觉，它只能通过对一个个的 0 和 1 进行操作，也就是位运算。

有没有通过其他运算符来实现 乘法 呢？

有——加法！

累加就是一种乘法，2+2+2=6 也就是 2*=6，对吧？

但是……如果我们要计算 1 * 100000000，岂不是要计算整整100000000次？！

虽然这有点夸张，但我们必须要考虑到，一个个的累加实在是太慢了……

来看看这样子的一个情形， ，换个表达方式，就是

所以说18可以被唯一的多个二的幂次方分解，原因嘛……当然是十进制都对应着唯一的二进制啦。

可这跟乘法又有什么关系呢？

要知道，二进制的每一位都是后面位数的 两倍 ，所以一个数如果要计算乘 2 的话，实际上是将它的二进制向左边移动了一位（也就是在右边补充一个 0），同理，如果要计算一个数除以 2 的话，就是反向的将它的二进制向右移动了一位（也就是直接去掉右边最后一个1/0）,这样子就能直接除以 2 并且向下取整了。

我们再来看看这样一段代码：

int quickMul(int num1,int num2){

    while(num2 != 0){        if((num2 & 1) == 1)            res += num1;        num1 = num1 + num1;        num2 >>= 1;    }    return true;}

假设num1 = 3、num2 = 7我们来模拟一遍这个过程

res    num1    num2

因为 7 的二进制为 111 所以 111 & 1 = 1,res += num1,且num2右移一位,就变成11,即3,而num1 += num13      6       3同理 3 的二进制为 11 所以 11 & 1 = 1，res += num1,num2继续右移,变成了19      12      1最终,res += num1,完成了最后一步，我们来看看答案……21     24      0

21!!!!!

wow，我们没有用到乘法，也没有计算num2次的加法，就得到了3 * 7 的结果！

而上述的操作，实际上是将num2的二进制遍历了一遍，并且每次对num1 进行自身+自身 的操作，实际上和二进制的左移是一样的，这样子就可以快速的算出了乘法的结果。

这个计算过程快吗？

这个过程就相当于在考虑一个数的二进制有多少位，等价询问：小于这个数的最大的二的幂是多少？

即，让这个式子中的最大，那么就是……,所以我们的时间复杂度是的。

好了，回到题目来，小时候，我们利用 感觉 来猜测列竖式的乘积，那么计算机能不能有一种比较类似的 感觉 呢？

有！！那就是二分！

现在已经有了乘法，怎么快速计算除法呢？

难道我们要挨个枚举去乘？这样子就会遇到 1000000 / 1的情况，效率会非常的低。

计算机每猜一个值，都是能够知道比目标值小还是大的，所以我们能不能考虑 步子迈得大一点 ？

平常，我们总说步子太大容易扯着，但是这次不一样，我们可以很快就知道我们是不是步子迈得大了，迈大了就及时调整。

二分就是一个可以让我们迈步子迈得刚刚好的方法。

我们定义一个left 和一个right，每次看一下left和right中间的值是否 刚刚好 ，如果是，那就直接结束，如果不是，那就看看是大了还是小了，小了就说明，比这个中间值更小的都不可行，一下子我们就排除掉了(right - left) / 2个答案，这样就可以迈很大一步，同理，如果大了说明比它更大的都不可行，还是可以排除(right - left) / 2个答案。

此时，你可能要问，题目要求不能使用除法了，怎么算left和right中间的值mid呢？

我们知道，mid = (left + right) / 2，回到之前提到的二进制，一个数除以 2 要怎么计算呢？

右移！

所以到此为止，我们已经完成了所有的准备工作了，接下来只要按步骤进行……

• 设置left和right为可能的答案边界——1和Integer.MAX_VALUE，为什么没有考虑负数呢？因为其实一个数除以另外一个数，答案的绝对值跟正负其实是无关的，而正负则跟二者的符号是否一致有关。
• 求出mid = (left + right) >> 1，然后利用 二进制分解 也就是上文的quickMul()方法，计算mid *divisor
• 将结果和dividend比较，观察是小了还是大了，如果小了则让left = mid + 1，大了就让right = mid - 1，因为我们不能事先就知道是不是刚刚好，但是我们知道ans * divisor <= dividend，所以我们要的就是最大的left，每次记录left的值即可，然后继续执行2步骤，直到——left == right因为如果left == right的话，二者的平均值与二者本身相等，就没有继续计算下去的必要了。

思路有了，这道题目仍然是有许多坑点，因为Leetcode的数据将每个边界条件都卡得刚刚好，而题目也说了我们只能使用32位整型，所以我们对每一个边界都要小心翼翼的去判断，看它是否超过。

class Solution {

        int res = 0;        while(num2 != 0){            if((num2 & 1) == 1){                if(res < com - num1)                    return false;                res += num1;            }            if(num2 != 1){                if(num1 < com - num1)                    return false;                num1 = num1 + num1;            }            num2 >>= 1;        }        return true;    }    public int divide(int dividend, int divisor) {        if(divisor == 0)            return 0;        if(dividend == Integer.MIN_VALUE){            if(divisor == 1)                return Integer.MIN_VALUE;            if(divisor == -1)                return Integer.MAX_VALUE;        }        if (divisor == Integer.MIN_VALUE) {            return dividend == Integer.MIN_VALUE ? 1 : 0;        }        if (dividend == Integer.MAX_VALUE && divisor == 1)            return dividend;        boolean rev = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);        dividend = -Math.abs(dividend);        divisor = -Math.abs(divisor);        int lef = 1,rig = Integer.MAX_VALUE;        int ans = 0;        while(lef <= rig){            int mid = lef + ((rig - lef) >> 1);            if(quickMul(divisor, mid, dividend)){                ans = mid;                lef = mid + 1;            }            else                rig = mid - 1;        }        return rev ? -1 * ans :  ans;    }}

代码中将两个数都转化成了负数，其实是为了拿到更大的范围来方便我们的判断，因为如果以0为分界点，32位整型能表示的负数要比正数多1，所以我们就将二者都转化为负数。

总结

本题考察了两个知识点——二分和二进制拆分，二者都跟 2 有密不可分的关系，实际上是和计算机有密不可分的关系，因为计算机是由一个个的1和0来组成的，所以我们在学习算法的时候，要能一步步的走向计算机的底层，学习计算机最精华的内容，才能够在解题的时候举一反三。

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

一步一个脚印

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

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 670 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

029.两数相除

题意

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

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

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

难度

中等

示例

输入: dividend = 10, divisor = 3

解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

分析

不能用除法，也不能利用乘法，还有 “模法（%）”，我们应该怎么去计算两数相除呢？

想想我们小学时候学习的列竖式，是不是反向利用了乘法来得出除法的结果？

那时候我们凭借感觉去一个个 “试”，但是计算机没有这样的感觉，它只能通过对一个个的 0 和 1 进行操作，也就是位运算。

有没有通过其他运算符来实现 乘法 呢？

有——加法！

累加就是一种乘法，2+2+2=6 也就是 2*=6，对吧？

但是……如果我们要计算 1 * 100000000，岂不是要计算整整100000000次？！

虽然这有点夸张，但我们必须要考虑到，一个个的累加实在是太慢了……

来看看这样子的一个情形， ，换个表达方式，就是

所以说18可以被唯一的多个二的幂次方分解，原因嘛……当然是十进制都对应着唯一的二进制啦。

可这跟乘法又有什么关系呢？

要知道，二进制的每一位都是后面位数的 两倍 ，所以一个数如果要计算乘 2 的话，实际上是将它的二进制向左边移动了一位（也就是在右边补充一个 0），同理，如果要计算一个数除以 2 的话，就是反向的将它的二进制向右移动了一位（也就是直接去掉右边最后一个1/0）,这样子就能直接除以 2 并且向下取整了。

我们再来看看这样一段代码：

int quickMul(int num1,int num2){

    while(num2 != 0){        if((num2 & 1) == 1)            res += num1;        num1 = num1 + num1;        num2 >>= 1;    }    return true;}

假设num1 = 3、num2 = 7我们来模拟一遍这个过程

res    num1    num2

因为 7 的二进制为 111 所以 111 & 1 = 1,res += num1,且num2右移一位,就变成11,即3,而num1 += num13      6       3同理 3 的二进制为 11 所以 11 & 1 = 1，res += num1,num2继续右移,变成了19      12      1最终,res += num1,完成了最后一步，我们来看看答案……21     24      0

21!!!!!

wow，我们没有用到乘法，也没有计算num2次的加法，就得到了3 * 7 的结果！

而上述的操作，实际上是将num2的二进制遍历了一遍，并且每次对num1 进行自身+自身 的操作，实际上和二进制的左移是一样的，这样子就可以快速的算出了乘法的结果。

这个计算过程快吗？

这个过程就相当于在考虑一个数的二进制有多少位，等价询问：小于这个数的最大的二的幂是多少？

即，让这个式子中的最大，那么就是……,所以我们的时间复杂度是的。

好了，回到题目来，小时候，我们利用 感觉 来猜测列竖式的乘积，那么计算机能不能有一种比较类似的 感觉 呢？

有！！那就是二分！

现在已经有了乘法，怎么快速计算除法呢？

难道我们要挨个枚举去乘？这样子就会遇到 1000000 / 1的情况，效率会非常的低。

计算机每猜一个值，都是能够知道比目标值小还是大的，所以我们能不能考虑 步子迈得大一点 ？

平常，我们总说步子太大容易扯着，但是这次不一样，我们可以很快就知道我们是不是步子迈得大了，迈大了就及时调整。

二分就是一个可以让我们迈步子迈得刚刚好的方法。

我们定义一个left 和一个right，每次看一下left和right中间的值是否 刚刚好 ，如果是，那就直接结束，如果不是，那就看看是大了还是小了，小了就说明，比这个中间值更小的都不可行，一下子我们就排除掉了(right - left) / 2个答案，这样就可以迈很大一步，同理，如果大了说明比它更大的都不可行，还是可以排除(right - left) / 2个答案。

此时，你可能要问，题目要求不能使用除法了，怎么算left和right中间的值mid呢？

我们知道，mid = (left + right) / 2，回到之前提到的二进制，一个数除以 2 要怎么计算呢？

右移！

所以到此为止，我们已经完成了所有的准备工作了，接下来只要按步骤进行……

• 设置left和right为可能的答案边界——1和Integer.MAX_VALUE，为什么没有考虑负数呢？因为其实一个数除以另外一个数，答案的绝对值跟正负其实是无关的，而正负则跟二者的符号是否一致有关。
• 求出mid = (left + right) >> 1，然后利用 二进制分解 也就是上文的quickMul()方法，计算mid *divisor
• 将结果和dividend比较，观察是小了还是大了，如果小了则让left = mid + 1，大了就让right = mid - 1，因为我们不能事先就知道是不是刚刚好，但是我们知道ans * divisor <= dividend，所以我们要的就是最大的left，每次记录left的值即可，然后继续执行2步骤，直到——left == right因为如果left == right的话，二者的平均值与二者本身相等，就没有继续计算下去的必要了。

思路有了，这道题目仍然是有许多坑点，因为Leetcode的数据将每个边界条件都卡得刚刚好，而题目也说了我们只能使用32位整型，所以我们对每一个边界都要小心翼翼的去判断，看它是否超过。

class Solution {

        int res = 0;        while(num2 != 0){            if((num2 & 1) == 1){                if(res < com - num1)                    return false;                res += num1;            }            if(num2 != 1){                if(num1 < com - num1)                    return false;                num1 = num1 + num1;            }            num2 >>= 1;        }        return true;    }    public int divide(int dividend, int divisor) {        if(divisor == 0)            return 0;        if(dividend == Integer.MIN_VALUE){            if(divisor == 1)                return Integer.MIN_VALUE;            if(divisor == -1)                return Integer.MAX_VALUE;        }        if (divisor == Integer.MIN_VALUE) {            return dividend == Integer.MIN_VALUE ? 1 : 0;        }        if (dividend == Integer.MAX_VALUE && divisor == 1)            return dividend;        boolean rev = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);        dividend = -Math.abs(dividend);        divisor = -Math.abs(divisor);        int lef = 1,rig = Integer.MAX_VALUE;        int ans = 0;        while(lef <= rig){            int mid = lef + ((rig - lef) >> 1);            if(quickMul(divisor, mid, dividend)){                ans = mid;                lef = mid + 1;            }            else                rig = mid - 1;        }        return rev ? -1 * ans :  ans;    }}

代码中将两个数都转化成了负数，其实是为了拿到更大的范围来方便我们的判断，因为如果以0为分界点，32位整型能表示的负数要比正数多1，所以我们就将二者都转化为负数。

总结

本题考察了两个知识点——二分和二进制拆分，二者都跟 2 有密不可分的关系，实际上是和计算机有密不可分的关系，因为计算机是由一个个的1和0来组成的，所以我们在学习算法的时候，要能一步步的走向计算机的底层，学习计算机最精华的内容，才能够在解题的时候举一反三。

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

一步一个脚印

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

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 670 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

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