29. Divide Two Integers

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31− 1]. For the purpose of this problem, assume that your function returns 2^31− 1 when the division result overflows.

Solution

(1) Java

class Solution {
    public int divide(int dividend, int divisor) {
        int sign = dividend >= 0 && divisor > 0 ? 1 : dividend <= 0 && divisor < 0 ? 1 : -1;
        int rst = 0;
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        } else if (divisor == 1) {
            return dividend;
        } else if (divisor == -1) {
            return -dividend;
        }
        dividend = dividend >= 0 ? -dividend : dividend;
        divisor = divisor > 0 ? -divisor : divisor;
        while (dividend <= divisor) {
            int shift = 1;
            int divisor2 = divisor;
            while (true) {
                if (divisor2<<1 >= 0 || divisor2<<1 < dividend) {
                    rst += shift;
                    dividend -= divisor2;
                    break;
                }
                shift <<= 1;             
                divisor2 <<= 1;
            }
        }
        return sign > 0 ? rst : -rst;
    }
}

(2) Python

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if divisor == 1:
            return dividend
        elif divisor == -1:
            if dividend == -2147483648:
                return 2147483647
            return -dividend
        sign = 1
        if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0):
            sign = -1
        dividend = abs(dividend)
        divisor = abs(divisor)
        rst = 0
        while dividend >= divisor:
            shift = 1
            divisor2 = divisor
            while True:
                if divisor2 << 1 > dividend:
                    rst += shift
                    dividend -= divisor2
                    break
                shift <<= 1
                divisor2 <<= 1
        if sign == 1:
            return rst
        return -rst

Another version

   def divide(self, a, b):
        sig = (a < 0) == (b < 0)
        a, b, res = abs(a), abs(b), 0
        while a >= b:
            x = 0
            while a >= b << (x + 1): x += 1
            res += 1 << x
            a -= b << x
        return min(res if sig else -res, 2147483647)

(3) Scala