【LeetCode-剑指offer】--1.两数相除

1.两数相除

方法：使用减法实现除法

用“被减数”能减去几次“减数”来衡量最后的结果，这时候我们想到求x的幂次的快速解法，将x成倍成倍的求幂，这里将减数成倍成倍的增大，次数对应也是成倍成倍的增大，例如：

为方便运算，我们需要将a，b都转为同正or同负，由于INT_MIN转正就越界了，我们只好都转负，这也是都转负的原因；

有一种特殊情况 INT_MIN/(-1)就overflow了 所以直接特殊处理

class Solution {
    public int divide(int a, int b) {
        //产生溢出
        if(a == Integer.MIN_VALUE && b == -1){
            return Integer.MAX_VALUE;
        }
        //异或操作，判断正负号
        int sign = (a > 0) ^ (b > 0) ? -1:1;
        if(a > 0) a = -a;
        if(b > 0) b = -b;
        int res = 0;
        while(a <= b){  //a的绝对值大
            int base = b;
            int k = 1;
            //由于a <= base + base可能溢出，改成a - base <= base
            while( a - base <= base){
                base += base;  //可以减的次数翻倍
                k += k;  //减数也翻倍
            }
            a -= base;
            res += k;
        }
        return sign * res;
    }
}