29. Divide Two Integers (Medium)

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

If it is overflow, return MAX_INT.

Solution 1: Bit Manipulation O(1); O(1)

In this problem, we are asked to divide two integers. However, we are not allowed to use division, multiplication and mod operations. So, what else can we use? Yeah, bit manipulations.

Let’s do an example and see how bit manipulations work.

Suppose we want to divide15by3, so15isdividendand3isdivisor. Well, division simply requires us to find how many times we can subtract thedivisorfrom the thedividendwithout making thedividendnegative.

Let’s get started. We subtract3from15and we get12, which is positive. Let’s try to subtract more. Well, weshift3to the left by1bit and we get6. Subtracting6from15still gives a positive result. Well, we shift again and get12. We subtract12from15and it is still positive. We shift again, obtaining24and we know we can at most subtract12. Well, since12is obtained by shifting3to left twice, we know it is4times of3. How do we obtain this4? Well, we start from1and shift it to left twice at the same time. We add4to an answer (initialized to be0). In fact, the above process is like15 = 3 * 4 + 3. We now get part of the quotient (4), with a remainder3.

Then we repeat the above process again. We subtractdivisor = 3from the remainingdividend = 3and obtain0. We know we are done. No shift happens, so we simply add1 << 0to the answer.

Now we have the full algorithm to perform division.

According to the problem statement, we need to handle some exceptions, such as overflow.

Well, two cases may cause overflow:

1. divisor = 0;
2. dividend = INT_MINanddivisor = -1(becauseabs(INT_MIN) = INT_MAX + 1).

Of course, we also need to take the sign into considerations, which is relatively easy.

Putting all these together, we have the following code.

    public int divide(int dividend, int divisor) {
        if (divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1)) {
            return Integer.MAX_VALUE;
        }

        int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;
        long m = Math.abs((long) dividend);
        long n = Math.abs((long) divisor);

        int res = 0;
        while (m >= n) {
            long temp = n;
            int multiple = 1;
            while (m >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }
            m -= temp;
            res += multiple;
        }
        return sign * res;
    }