整数相除

1. 来源：https://leetcode-cn.com/problems/xoh6Oh/

2.思路

为了方便描述，我们考虑a和b都为正数的情况，之后再考虑其他情况。

最直接的思路就是将b一个一个的累加，至到累加的结果超过了a，即可得到答案。以a=18，b=5为例，此过程如下图所示：

这个作法通俗易懂，但效率不高，举个极端例子，当a=2^31-1 、b=1时，要将b加2^31-1次才能算出结果。下面给出优化算法。

3.优化

在上述算法中，我们每次给v加一个b，事实上我们可以考虑每次让v翻倍增加，也就是说，上图中的v不是一个b一个b地增加，而是每次让v=v+v。当v大于a时，我们将a更改为a-(v/2)，并重复此操作，直到a小于b。那么我们怎么得到结果呢？注意到每次v大于a时，我们都可以得到v/2里面包含有k个b，将k累计到结果里面即可。如下图所示：

4. 边界条件

上述过程我们考虑了a和b都是正数的情况，当两个都为负数或者一正一负的时候，我们可以考虑将其都转换为正数计算，然后根据负数的个数改变结果的正负号即可（即当a和b中有一个为负数时，给结果加个负号），下面的情况也是必须要考虑的：

32位整数的范围：最小值为-2^31= -2147483648，最大值为2^31-1= 2147483647

① 当a为-2147483648时，将a变为正数计算会越出最大值，因此我们考虑将a和b均转为负数计算，思路和两个正数计算相同，不再赘述。

② 当a=-2147483648，b=-1时，计算结果为ret为2147483648，超过32位正数的最大值，此时直接返回2147483647即可。

5.代码（Java）

class Solution{
    public int devide(int a, int b){
        if(a == Integer.MIN_VALUE && b == -1) return Integer.MAX_VALUE;

        int negCount = 0;   //记录a和b中负数的个数
        if(a<0) negCount++; else a = -a;    //将a确定为负数，更新negCount
        if(b<0) negCount++; else b = -b;    //将b确定为负数，更新negCount

        int ret = 0;            //返回值

        while(a<=b){    //循环条件：a还能分为若干个b
            int v = b;
            int k = 1;
            while (v>=Integer.MIN_VALUE/2 && a<=v+v){ //v+v有可能越过最小值，因此v不能小于最小值的一半
                v = v+v;
                k = k+k;
            }
            a = a-v;
            ret+=k;
        }
        return negCount==1? -ret:ret;   //当且仅当a和b有一个为负数时，结果为负
    }
}

6.性能