[Leetcode] Divide Two Integers

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

Use subtraction to mimic the division. We could continue subtract division from dividend until dividend is smaller than division. On way to speed up is to double the division each time. However, pay attention to some case that might overflow:

1. When double the divisor, it might overflow, so we need some check to prevent this.
2. When change the negative to positive number, if negative is MIN_VALUE, it will overflow, here I use long to avoid this situation.

    public int divide(int dividend, int divisor) {
        boolean sign = true;
        if((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0))
            sign = false;
        long a = dividend, b = divisor;
        a = (a < 0) ? -a : a; // here might overflow
        b = (b < 0) ? -b : b;
        long res = 0;
        while(a >= b) {
            long x = b;
            long cnt = 1;
            while(a - x >= x) {
                x = x << 1;
                cnt = cnt << 1;
            }
            a = a - x;
            res = res + cnt;
        }
        if(sign == false)
            return (int)-res;
        return (int)res;
    }