29. 两数相除

29. 两数相除

class Solution {
    public int divide(int dividend, int divisor) {
        long result = 0;
        boolean isNeg = false;
        long x = dividend;
        long y = divisor;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) 
            isNeg = true;
        x = Math.abs(x);
        y = Math.abs(y);
        long left = 0;
        long right = x;
        while (left < right) {
            long mid = (left + right + 1) >> 1;
            if (quickMul(y, mid) <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        result = isNeg ? -left : left;
        if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE)
            return Integer.MAX_VALUE;
        return (int)result;
    }
    public long quickMul(long a, long b) {
        // 快速乘法, 本题中只考虑正数
        long result = 0;
        while (b > 0) {
            if ((b & 1) == 1) {
                result += a;
            }
            b >>= 1;
            a += a;
        }
        return result;
    }
}