29. Divide Two Integers

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

If it is overflow, return MAX_INT.

Solution:

There are a few corner case to deal with first.

To avoid overflow, we set dividend and divisor to long.

The idea is try to double divisor each time and check until it exceeds dividend.

When this happens, we can subtract the dividend by previous doubled divisor, and increase the result.

We do it again until dividend < divisor.



Code:

public class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == 0) {
            return dividend >= 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        int result = 0;
        while (a >= b) {
            int shift = 0;
            while (a >= (b << shift)) {
                shift++;
            }
            a -= (b << (shift - 1));
            result += (1 << (shift - 1));
        }
        return sign * result;
    }
}