Divide Two Integers

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.

Solution:

In the example, the result could be obtained by 100 = 8 * 9 + 2 * 9 + 1 * 9 + 1, where 11 = 8 + 2 + 1. This give us a hint that we can double a number serveral times and multiply it with divisor to approach dividend. Once we found that number, we substract the production from the dividend and add the number of doubled times to result. Repeat these two steps until the remainder is less t han divisor.

Code:

public int divide(int dividend, int divisor) {
    if (divisor == 0) {
        if (dividend >= 0) {
            return Integer.MAX_VALUE;
        } else {
            return Integer.MIN_VALUE;
        }
    }
    if (dividend == 0) {
        return 0;
    }
    //absolute value of Integer.MIN_VALUE will overflow
    if (dividend == Integer.MIN_VALUE && divisor == -1) {
        return Integer.MAX_VALUE;
    }
    boolean isNegative = false;
    if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) {
        isNegative = true;
    }
    long a = Math.abs((long) dividend);
    long b = Math.abs((long) divisor);
    int result = 0;
    while (a >= b) {
        int num = 0;
        while (a >= b << num) {
            num++;
        }
        num--;
        a -= b << num;
        result += 1 << num;
    }
    if (isNegative) {
        result = 0 - result;
    }
    return result;
}