Divide Two Integers

Question Description

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

If it is overflow, return MAX_INT.

Solution

Because dividend = divisor (? 2^0 + ? 2^1 + ... + ? 2^i), ? could be 0 or 1. So we first find i that satisfies divisor 2^i <= dividend < divisor 2^(i+1). Then we reduce the dividend for all the is that satisfying divisor 2^i <= remain < divisor 2^(i + 1) until dividend < divisor. Then we get the result.

Because multiplication is not allowed here so we use left shift to replace.

Another key in this questions is the corner cases.

1. Dividend and divisor could be negative values.
2. When divisor is -1, dividend is -2147483648, result will overflow.
3. When divisor is 0, we need to deal with overflow.

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if divisor == 0:
            return 2147483647 if dividend >= 0 else -2147483648
        elif divisor == -1:
            return 2147483647 if dividend == -2147483648 else -dividend
        sig = True if (dividend > 0 and divisor) < 0 or (dividend < 0 and divisor > 0) else False
        dividend, divisor, result, i = long(abs(dividend)), long(abs(divisor)), 0, 0
        while divisor << (i + 1) <= dividend:
            i += 1
        while dividend >= divisor:
            if dividend >= divisor << i:
                dividend -= divisor << i
                result += 1 << i
            i -= 1
        return -result if sig else result