1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

    //定义移位边界，防止左移溢出
    private static final int BOUND = Integer.MIN_VALUE>>1;

    //被除数是最小负数，除数是-1，返回最大正数
    public int divide(int a,int b){
        if(a==Integer.MIN_VALUE&&b==-1){
            return Integer.MAX_VALUE;
        }

        if(a==0||b==1){
            return a;
        }else if(b == -1){
            return -a;
        }

        int negative = 2;
        // 统一转为负数计算，避免MIN_VALUE取反溢出
        if(a>0){
            negative--;
            a=-a;
        }

        //仅处理a、b均为负数的情况，返回正的商
        if(b>0){
            negative--;
            b=-b;
        }

        int ans = helpDivide(a,b);
        return negative == 1 ? -ans : ans;
    }

    private int helpDivide(int a,int b){
        // 被除数绝对值 == 除数绝对值，商为1
       if(a==b){
        return 1;
       } 
       int res = 0;
       int shift = getMaxShift(a,b);
       while(a<=b){
        while (a>(b<<shift)) {
            shift--;
        }
        a-=(b<<shift);// 减去 b×2^shift
        res+=(1<<shift);// 商累加 2^shift
       }
       return res;
    }

    // 获取除数b的最大有效移位次数
    private int getMaxShift(int a,int b){
        int shift = 0;
        int tmp = b;

        while(tmp>a && tmp>=BOUND){
            tmp<<=1;
            shift++;
        }
        return shift;
    }