Leetcode 29: Divide Two Integers

Divide Two Integers

 

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.

这一题中divide two integers 不允许有乘除模操作，利用的数学性质是任何一个整数NUM， 都可以表示成2 ^ n的形式： num = a0 * 2^0 + a1 * 2^1 + .....+ an * 2^n;
利用这个性质，可以利用左移操作<<， 除数也以2倍数增长。 
还要注意可能溢出的情况，当被除数是INT_MIN的， 除数是-1的时候，值会超出INT_MAX。 这种overflow的情况要考虑到。
class Solution {
public:
    int divide(int dividend, int divisor) {
        long long a = dividend;
        long long b = divisor;
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }
        int count = 0;
        int rst  = 0;
        a = abs(a);
        b = abs(b);
       
        while (a >= b) {
            while (a >= (b << count+1)) count++;
            a = a - (b << count);
            rst = rst + (1<< count);
            count = 0;
        }
        return ((dividend < 0) ^ (divisor < 0)) ? -rst : rst;
    }
};