29. Divide Two Integers

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

If it is overflow, return MAX_INT.

分析

不能用除法，所以使用减法不断减 除数，同时对 除数 倍乘，进行加速

除数：3 -> 6 -> 12 ...

边界条件：

1 除数为0，溢出

2 被除数 INT_MIN，同时除数 -1，溢出，因为labs(MIN_INT) = INT_MAX + 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { public:     int divide(int dividend, int divisor) {         if( !divisor || (dividend == INT_MIN && divisor == -1))             return INT_MAX;         int sign = (dividend<0) ^ (divisor<0)? -1: 1;         long long a = labs(dividend);         long long b = labs(divisor);         long long result = 0;         while( a >= b){             for(long long i = 1, d = b; a >= d; ++i, d <<= 1){                 a -= d;                 result += 1 << (i-1);             }         }         return result*sign;     } };

null