Description:

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

最笨的实现方式：
在case为(-2147483648, -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
public int divide(int dividend, int divisor) {
    if (divisor == 0) {
        return Integer.MAX_VALUE;
    }
    if (dividend == 0) {
        return 0;
    }
    int absDividend = Math.abs(dividend);
    if (dividend == Integer.MIN_VALUE) {
        absDividend = -(dividend + 1);
    }
    int absDivisor = Math.abs(divisor);
    int value = 0;
    while (absDividend >= 0) {
        absDividend -= absDivisor;
        if (absDividend >= 0) {
            value++;
        }
    }
    if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) {
        return -value;
    } 
    return value;
}

更好的实现方式：

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
public int divide(int dividend, int divisor) {
    if (divisor == 0) {
        return Integer.MAX_VALUE;
    }
    if (dividend == 0) {
        return 0;
    }
    long absDividend = Math.abs((long) dividend);
    long absDivisor = Math.abs((long) divisor);
    long tempDivisor = absDivisor;
    int length = 0;
    while (tempDivisor != 0) {
        tempDivisor >>= 1;
        length++;
    }
    long result = 0;
    for (int i = 32 - length; i >= 0; i--) {
        if ((absDivisor << i) <= absDividend) {
            result += (1l << i);
            absDividend -= (absDivisor << i);
        }
    }
    if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) {
        return (int)-result;
    }
    if (result > Integer.MAX_VALUE) {
        result = -1 * ((int) result + 1);
    }
    return (int)result;
}

PS :
需要注意几组case：
2147483647,1
2147483647,-1
-2147483648,-1
-2147483648,1