图解LeetCode：整数相除

骑猪看日落 2022-12-31 03:27 131阅读 0赞

这是LeetCode的第29号题目，Divide Two Integers，题目要求计算两个数相除是多少，最后返回整数就可以。

比如给定10和4，那10/4是2；给定7和-3，那么7/(-3)应该返回2，题目要求**不能用乘法、除法和取余操作**。如果在面试时遇到这个题目该怎么求解呢？

#### 我的思路 ####

首先我们可以将除数和被除数都转为正数以简化操作，而对于除法来说其本质上就是**减法**，比如对于100/4，其本质上无非就是100可以减去多少个4直到剩下数无法再减去4为止，如图所示：

![format_png][]

将右边的1累加最后会得到25，这也就是100/4。

如果让你将上述过程用代码实现应该很简单吧，但是这个算法是在运行起来很慢，假设给定除数是1，被除数是10亿，那么上述算法要运行10亿次，该如何改进呢？

#### 算法优化 ####

实际上这个问题的实现思路也就是用减法来模拟除法了，就像上图那样，这里的关键就在于该**如何优化这个过程**。

让我们再来看一下上图的求解过程，每次都简单的减去除数，在这种算法下将被除数减到小于除数是很慢的，该如何加速这个过程呢？仔细想一想。

我们为什么要老老实实的减去一个除数呢？能不能一次多减几个除数？

因此我们每次可以将除数翻倍，**直到被除数小于翻倍后的除数为止**，此时如果被除数依然大于原始的除数那么继续上述过程，只不过这次除数要从初始值开始翻倍，还是以100/4为例，如图所示：

![format_png 1][]

由于除数每次翻倍，这样上述过程可以快速的计算完毕，然后再讲右边的计数累加，算一下，1+2+4+8+1+2+4+1+2同样是25。

有的同学可能会有疑问，为什么每次除数都翻倍而不是x3呢，不要忘了题目要求不可以使用乘法，翻倍可以简单的将该数的二进制左移一位得到，这样我们可以在不是用乘法的操作下模拟除法了。

有了这些分析代码还会很难实现吗？

#### 代码实现 ####

该代码仅仅就是将上图的计算过程翻译成C++代码，唯一需要注意的一点是溢出情况的处理。

int divide(int dividend, int divisor) {
        int sign = (dividend^divisor)>=0?1:-1;
        long int a = dividend;
        long int b = divisor;
        a = a>0?a:-a;
        b = b>0?b:-b;
        long int t = b;
        long int r = 0;
        long int i = 1;
        while(a-b>=0){
            a-=t;
            r+=i;
            i=(i<<1);
            t=(t<<1);
            if (a-t<0){
                i=1;
                t=b;
            }
        }
    
    
        if (sign<0&&(-r)<(int)0x80000000 ||
           sign>0&&r>(int)0x7fffffff)
          return 0x7fffffff;
        return sign>0?r:(-r);
    }

####     ####

#### 总结 ####

这个题目的难点不在于思路，关于在于基于该思路的优化，实际上这个题目的优化在思想上和二分查找有些类似，二分查找的思想是每次排除掉一半的数据量从而加快查找速度，而这里是每次将除数翻倍从而加快收敛速度，因此如果你真的深刻理解了二分查找的话，那么这个问题对于来说应该不在话下。

--------------------

![format_png 2][]

PS：微信公众号从去年开始限制了留言功能，如果你有任何问题欢迎直接在公众号留言。

[format_png]: /images/20221120/1db299924bd146adbea8e1ead88f956e.png
[format_png 1]: /images/20221120/08e9e22c31f343a49a1130648d1ccea5.png
[format_png 2]: /images/20221120/8f35ac489d174dd8814d19a0d339f0dd.png