LeetCode 剑指 Offer II 001. 整数除法

LeetCode 剑指 Offer II 001. 整数除法

思路：

如果不能使用 / 号 只能用减法去计算除法，但是如果a很大但是b很小，算法就是O(n)的，会TLE，所以我们可以在减法的时候优化一下，成倍的去减，即每次计算a比2 的 多少次幂大，然后去不断的做减法。

最大的正数为 2^{31-1,最小的负数为 -2}31,如果将负数转化为正数会溢出，所以可以将正数都转化为负数计算

这里要限制一下value，即2 的多少次幂，如果value <= 0xc0000000(注意我们这里都是使用负数计算的)，下一次就会爆int。

代码：

class Solution {
public:
    int divide(int a, int b) {
        if(a == INT_MIN){
            if(b == -1) return INT_MAX;
            if(b == 1) return INT_MIN;
        } 
        bool flag = false;
        if((a < 0) ^ (b < 0)) flag = true;
        //因为会爆int  所以用负数去算
        if(a > 0) a = -a;
        if(b > 0) b = -b;

        int res = 0;
        //用二进制去逼近
        while(a <= b){
            int value = b;
            int q = 1;//商
            //如果除数大于 INT_MIN的一半的(绝对值)就停止
            while(value >= 0xc0000000 && a <= value + value){
                q += q;
                value += value;
            }
            res += q;
            a -= value;
        }

        if(flag) return -res;
        return res;
    }
};