图解LeetCode：整数相除

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

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

我的思路

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

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

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

算法优化

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

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

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

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

由于除数每次翻倍，这样上述过程可以快速的计算完毕，然后再讲右边的计数累加，算一下，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);}

总结

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