Leetcode29:两数相除

  public static int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            return 1;
        }
        if (a != Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            return 0;
        }
        if (a == Integer.MIN_VALUE) {
            if (b == -1) {
                return Integer.MAX_VALUE;
            }
            /**
             * 系统最小值没办法取绝对值，使用分配律解决
             *
             * 要计算Integer.MIN_VALUE ÷ b：
             * 先计算（Integer.MIN_VALUE+1）÷ b = c
             * c*b = a
             * [（Integer.MIN_VALUE+1）- a] / b = d
             * 商=c+d
             */
            int i = divideNormal(add(a, 1), b);
            int multiplyRes = multiply(i, b);
            int minusRes = minus(a, multiplyRes);
            int subRes = divideNormal(minusRes, b);
            return add(i, subRes);
        }
        return divideNormal(a, b);
    }

    /**
     * 正常除法（不包含系统最小）
     * @param a
     * @param b
     * @return
     */
    private static int divideNormal(int a, int b) {
        boolean negativeA = isNegative(a);
        boolean negativeB = isNegative(b);
        a = negativeA ? oppositeNum(a) : a;
        b = negativeB ? oppositeNum(b) : b;
        int result = 0;
        // int整型一共32位，一位一位的移动去尝试
        for (int i = 30; i >= 0; i = minus(i, 1)) {
            if ((a >> i) >= b) {
                //说明第i位是1，使用|运算，让数字和1<
                result = result | (1 << i); 
                a = minus(a, b << i); //a = a-(b<
            }
        }
        return negativeA != negativeB ? oppositeNum(result) : result;
    }

    /**
     * 判断一个数是否是负数
     * @param a
     * @return
     */
    public static boolean isNegative(int a) {
        return a < 0;
    }

    /**
     * 取相反数
     * @param a
     * @return
     */
    public static int oppositeNum(int a){
        return ~a+1;
    }

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
61
62
63
64
65
66
67
68
69
70

完整题解：

class Solution {

    public int divide(int dividend, int divisor) {  
        if (dividend == Integer.MIN_VALUE && divisor == Integer.MIN_VALUE) {
            return 1;
        }
        if (dividend != Integer.MIN_VALUE && divisor == Integer.MIN_VALUE) {
            return 0;
        }
        if (dividend == Integer.MIN_VALUE) {
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
            int i = divideNormal(add(dividend, 1), divisor);
            int multiplyRes = multiply(i, divisor);
            int minusRes = minus(dividend, multiplyRes);
            int subRes = divideNormal(minusRes, divisor);
            return add(i, subRes);
        }
        return divideNormal(dividend, divisor);
    }

    public int divideNormal(int dividend, int divisor) {
        boolean isNegativeA = isNegative(dividend);
        boolean isNegativeB = isNegative(divisor);
        dividend = isNegativeA? oppositeNum(dividend):dividend;
        divisor = isNegativeB? oppositeNum(divisor):divisor;
        int result = 0;
        for(int i=30;i>=0;i = minus(i,1)){
            if(dividend>>i >= divisor){
                result |= 1<<i;
                //dividend = dividend - divisor<
                dividend = minus(dividend,divisor<<i);
            }
        }
        return isNegativeA!=isNegativeB ? oppositeNum(result) : result;
    }

    public boolean isNegative(int a){
        return a<0;
    }

    public int add(int a ,int b){
        //相同为0，不同为1，当两个要相加的时候，相同进位为0，不同1+0=0，缺少进位信息
        int result = a ^ b;
        // 相同为1，不同为0；相同进位，左移一位刚好为进位信息
        int carry = (a & b) << 1;
        if(carry!=0){
            return add(result,carry);
        }
        return result;
    }

    public int minus(int a,int b){
        return add(a,oppositeNum(b));
    }

    public int multiply(int a,int b){
        int result = 0;
        while(b!=0){
            int res = b&1;
            if(res == 1){
                result = add(a,result);
            }
            a = a<<1;
            b = b>>>1;
        }
        return result;
    }

    public int oppositeNum(int a){
        return add(~a,1);
    }
}
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74