Leetcode #29 Divide Two Integers

[yokostan]

public int divide(int dividend, int divisor) {

        long ldividend = (long) dividend, ldivisor = (long) divisor;

        boolean signNegative = false;
        if (ldividend < 0) {
            signNegative = !signNegative;
            ldividend = -ldividend;
        }
        if (ldivisor < 0) {
            signNegative = !signNegative;
            ldivisor = -ldivisor;
        }

        long result = divideRecur(ldividend, ldivisor);

        if (result > Integer.MAX_VALUE && !signNegative) {
            result = Integer.MAX_VALUE;
        } else if (result < Integer.MIN_VALUE) {
            result = Integer.MIN_VALUE;
        }

        return signNegative ? (int) -result : (int) result;
    }

    private long divideRecur(long dividend, long divisor) {

        if (dividend < divisor)
            return 0;

        long sum = divisor, quotient = 1;
        while (sum + sum < dividend) {
            sum += sum;
            quotient += quotient;
        }

        return quotient + divideRecur(dividend - sum, divisor);
    }

This is one I need to understand better... about how the binary search is conducted and how we deal with edge cases. Here is some solution with explanation:

private long ldivide(long ldividend, long ldivisor) {
    // Recursion exit condition
    if (ldividend < ldivisor) return 0;

    //  Find the largest multiple so that (divisor * multiple <= dividend), 
    //  whereas we are moving with stride 1, 2, 4, 8, 16...2^n for performance reason.
    //  Think this as a binary search.
    long sum = ldivisor;
    long multiple = 1;
    while ((sum+sum) <= ldividend) {
        sum += sum;
        multiple += multiple;
    }
    //Look for additional value for the multiple from the reminder (dividend - sum) recursively.
    return multiple + ldivide(ldividend - sum, ldivisor);
}

Here is some template for us to handle overflow:

if (lans > Integer.MAX_VALUE){ //Handle overflow.
        ans = (sign == 1)? Integer.MAX_VALUE : Integer.MIN_VALUE;
    }

The absolute value of MIN_VALUE is one digit bigger than MAX_VALUE, and we are setting numbers >= MAX_VALUE to MAX_VALUE and numbers <= MIN_VALUE to MIN_VALUE. So we can assign MAX_VALUE to numbers > MAX_VALUE, which is the range of Math.abs that numbers are <= MIN_VALUE. We included the edge that number == MIN_VALUE, which is fine, for we are setting that to MIN_VALUE anyways, so it doesn't change.

From last post, we were building up the integer and checked whether it would overflow one digit in advance, where we also took advantage of this one digit difference. It simplified things a lot!