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

If it is overflow, return MAX_INT.

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
/*
这里需要注意的就是溢出的问题，我们知道，int的范围为
-2147483648 ~ 2147483647
所以需要考虑的情况就是当-2147483648 / -1时，会溢出
*/
class Solution {
public:
    int divide(int dividend, int divisor) {
        long long a = dividend >= 0 ? dividend : -(long long) dividend;
        long long b = divisor >= 0 ? divisor : -(long long) divisor;
        long long result = 0;
        while (a >= b) {
            long long c = b;
            for (int i = 0; a >= c; ++i, c <<= 1) {
                a -= c;
                result += 1 << i;
            }
        }
        result = ((dividend ^ divisor) >> 31) ? -result : result;
        return result >= INT_MAX ? INT_MAX : result;
    }
};