[LeetCode] Divide Two Integers

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

If it is overflow, return MAX_INT.

思路：用 divisor 右移，计算出最大的位数，然后不断比较 更新过的dividend 和 divisor << number, 直到number =0；

Note：1 abs()的原型是abs(int),所以abs(long long int) 会溢出，不能使用，可以使用llabs，我这里直接自己计算了。 

　　#include <stdlib.h>

　　int abs(int j);
　　long int labs(long int j);
　　long long int llabs(long long int j);

　　2 在移位操作中， 不能直接使用1<< num, 要使用1ULL， 如果不写UL后缀,系统默认为:int, 即,有符号整数，如果移位超过32位，将发生溢出。

　　另外，在32bits系统中，long移位32为， 所以为了保证不溢出，要使用64bits 的long long 类型。

    cout << (1 << 31) << endl;
    cout << (1u << 31) << endl;
    cout << (1 << 32) << endl;
    cout << (1ull << 32) << endl;

结果为：

-2147483648
2147483648
0
4294967296

1 为int， 1u 为unsigned int， 1 << 32, 溢出，结果为0， 1ull <<32未溢出。

class Solution {
    public:
        int divide(int dividend, int divisor)
        {
            int leftShiftBits= 0;
            long long divd = dividend;
            long long divr = divisor;
            long long result = 0;
            int sign = 1;

            if( (divd < 0 && divr > 0) || (divd > 0 && divr < 0) )
                sign = -1;
# if 0
            //note abs(int) can't handle abs(long), so abs(INT_MIN) will overflow
            divd = abs(divd);
            divr = abs(divr);
# endif
            if(divd < 0)
                divd = -divd;
            if(divr < 0)
                divr = -divr;

            while( (divr << leftShiftBits) < divd)
            {
                leftShiftBits ++;
            }

            //leftShiftBits --; //the function can work with or without this scentence

            while(leftShiftBits >= 0)
            {
                if(divd >= (divr << leftShiftBits))
                {
                    result += 1ULL << leftShiftBits;
                    divd -= (divr << leftShiftBits);
                }
                leftShiftBits --;
            }

            if((result * sign) > INT_MAX) return INT_MAX;
            else if((result * sign) < INT_MIN) return INT_MIN;
            return result * sign;
        }
};