剑指 Offer II 001. 整数除法

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1

class Solution {
    public int divide(int a, int b) {
        //除数为零，直接返回0
        if(b==0||a==0){
            return 0;
        }
        //如果除数为1，则不需要处理了
        if(b==1){
            return a;
        }
        //除法结果溢出，则商为MAX_INTEGER+1，才会溢出，则除数为-1，被除数为负数最大值
        if(a==Integer.MIN_VALUE&&b==-1){
            return Integer.MAX_VALUE;
        }

        //如果同号，循环减，减到变号前,商就是结果
        int q=0;
        // if((a>0&&b>0)||(a<0&&b<0)){
        //     int temp=a;
        //     while((temp>0&&temp-b>=0)||(temp<0&&temp-b<=0)){
        //         q++;
        //         temp=temp-b;
        //     }
        //     return q;
        // }else{//如果异号，循环加，加到变号，将商-1，再将商取负，就是结果
        //     int temp=a;
        //     while((temp>0&&temp+b>=0)||(temp<0&&temp+b<=0)){
        //         q++;
        //         temp=temp+b;
        //     }
        //     return 0-q;
        // }
        boolean isConSign=((a>0&&b>0)||(a<0&&b<0))? true:false;
        a=(a>0)?-a:a;
        b=(b>0)?-b:b;
        int minB=Integer.MIN_VALUE/2;
        while(a<=b){
            int d=b;
            int c=1;
            while(d>=minB&&d+d>=a){ //看能除的最大的除数是几，以每次翻二倍试探
                c=c+c;
                d=d+d;
            }
            //试探出来，a中至少有一个d,它里面至少有c个b
            a=a-d;
            q=q+c;
        }
        return isConSign? q:-q;
    }
}

为了减少相减的次数，除数弹性伸缩，每次试探到最大的原来除数的2的倍数，然后相减，二分法相减。