Divide Two Integers

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

这题有两种想法，第一种是被除数-除数，看一共要减多少次。复杂度O(n)。第二种是利用一个性质，任何数num都能分解成
num=a_02^0+a_12^1+a_2*22+...+a_n*2^n

先复习一下运算符：
<<左移运算符，num << 1,相当于num乘以2
>>右移运算符，num >> 1,相当于num除以2
好了，这题是利用这两个运算符和「除法分配律」。比如对于19/3，先找到对于3 * 2^n < 19 最大的n，然后用19减去，迭代。
19/3 = 12/3 + 7/3 = 3 * 2^2 + 3 * 2^1
那么结果就是2^2 + 2^1 = 6
但是这题的corner case 太多。。。这题切记一定要把Integer转换成long...

    long pDividend = Math.abs((long)dividend);

否则INTEGER.MAX_VALUE 除以1，除以2都算不出来，numShift会循环到32然后又从0开始，我TM不知道是什么鬼。。搞死我了，日。fin，睡觉了。

洗澡时又想了下，发现了原因：
System.out.println(1 << 31);会打印-2147483648。
System.out.println(1 << 32);会打印1。
然后循环。
System.out.println((long)1 << 32);才能打印超越MAXINT的值。

所以如果不转换成long，当pDividend是MAXINT， while(pDividend>=pDivisor){}永远都会true。
睡觉。

http://www.programcreek.com/2014/05/leetcode-divide-two-integers-java/

    //handle special cases
    if(divisor==0) return Integer.MAX_VALUE;
    if(divisor==-1 && dividend == Integer.MIN_VALUE)
        return Integer.MAX_VALUE;
 
    //get positive values
    long pDividend = Math.abs((long)dividend);
    long pDivisor = Math.abs((long)divisor);
 
    int result = 0;
    while(pDividend>=pDivisor){
        //calculate number of left shifts
        int numShift = 0;    
        while(pDividend>=(pDivisor<<numShift)){
            numShift++;
        }
 
        //dividend minus the largest shifted divisor
        result += 1<<(numShift-1);
        pDividend -= (pDivisor<<(numShift-1));
    }
 
    if((dividend>0 && divisor>0) || (dividend<0 && divisor<0)){
        return result;
    }else{
        return -result;
    }
}