Divide Two Integers

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

If it is overflow, return MAX_INT.

Solution:

Use bit manipulation to find how maximum number of divisors that can occupied within the dividend. Not a typical binary search problem.

public int divide(int dividend, int divisor) {
    if (divisor == 0) {
        return Integer.MAX_VALUE;
    } else if (divisor == -1 && dividend == Integer.MIN_VALUE) {
        return Integer.MAX_VALUE;
    }
    long divd = Math.abs((long)dividend),
         divr = Math.abs((long)divisor);
    int result = 0;
    while (divd >= divr) {
        int multiple = 0;
        while (divd >= (divr << multiple)) {
            multiple++;
        }
        result += (1 << (multiple - 1));
        divd   -= (divr << (multiple - 1));
    }
    if ((dividend < 0 && divisor < 0) ||
        (dividend > 0 && divisor > 0)) {
        return result;    
    } else {
        return -result;
    }
}