Problem

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

If it is overflow, return 2147483647.

Example

Given dividend = 100 and divisor = 9, return 11.

Note

首先，分析溢出条件，设置符号位，然后取绝对值运算。
原理如下，被除数a，除数b，设c等于b。
在b<=a时，令除数c每次乘以2，增大到小于等于被除数a的时候，c乘了几次，商里就会有一个2的几次方。如25 / 4，4 * 4 < 25，4 * 8 > 25，所以商里必定有一个4（2的2次方）存入temp，然后res += temp。
然后被除数a减去c，继续check。a = 25 - 4 * 4 = 9，c = 4 * 2 = 8，所以商里必定有一个8 / 4 = 2（2的1次方）存入temp。此时a = 9 - 8 = 1，a < b，循环结束。res = 4 + 2 = 6，为所求。

再举一个例子:

13 / 3, a = 13, b = 3, c = 3:
c = 3, temp = 1; c = 6, temp = 2; c = 12; temp = 4;
c = 3, res = 4, a = 1, a < b, return res = 4.

Solution

public class Solution {
    public int divide(int dividend, int divisor) {
        long res = 0;
        boolean neg = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0);
        long a = Math.abs((long)dividend);
        long b= Math.abs((long)divisor);
        while (a >= b) {
            long c = b;
            long temp = 0;
            while (c <= a) {
                temp = temp == 0 ? 1 : temp << 1;
                c = c << 1;
            }
            c = c >> 1;
            a -= c;
            res += temp;
        }
        if (res >= Integer.MAX_VALUE) res = neg ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        else if (neg) res = -res;
        return (int)res;
    }
}