Divide Integers

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

Return the floor of the result of the division.

Example:

5 / 2 = 2

Also, consider if there can be overflow cases. For overflow case, return INT_MAX.

Method:

The key observation is that the quotient of a division is just the number of times that we can subtract the divisor from the dividend without making it negative.

Suppose dividend = 15 and divisor = 3, 15 - 3 > 0. We now try to subtract more by shifting 3 to the left by 1 bit (6). Since 15 - 6 > 0, shift 6 again to 12. Now 15 - 12 > 0, shift 12 again to 24, which is larger than 15. So we can at most subtract 12 from 15. Since 12 is obtained by shifting 3 to left twice, it is 1 << 2 = 4 times of 3. We add 4 to an answer variable (initialized to be 0). The above process is like 15 = 3 * 4 + 3. We now get part of the quotient (4), with a remaining dividend 3.

Then we repeat the above process by subtracting divisor = 3 from the remaining dividend = 3 and obtain 0. We are done. In this case, no shift happens. We simply add 1 << 0 = 1 to the answer variable.

This is the full algorithm to perform division using bit manipulations. The sign also needs to be taken into consideration. And we still need to handle one overflow case: dividend = INT_MIN and divisor = -1.

Solution:

Time: O(logn * logn)
Space: O(1)

public class Solution {
    public int divide(int A, int B) {
        if (B == 0 || A == Integer.MIN_VALUE && B == -1) {
            return Integer.MAX_VALUE;
        }
        int sign = (A < 0) ^ (B < 0) ? -1 : 1;
        int result = 0;
        long dividend = Math.abs((long) A);
        long divisor = Math.abs((long) B);
        while (divisor <= dividend) {
            long temp = divisor;
            int times = 1;
            while (temp << 1 < dividend) {
                temp <<= 1;
                times <<= 1;
            }
            dividend -= temp;
            result += times;
        }
        return sign == -1 ? -result : result;
    }
}