[LeetCode]29 两数相除

题目描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例1:

输入: dividend = 10, divisor = 3
输出: 3

示例2:

输入: dividend = 7, divisor = -3
输出: -2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        MAX_INT = 2**31 -1
        MIN_INT = -2**31
        
        if divisor == 0:
            raise ZeroDivisionError()
        
        sign = 1
        if min(dividend, divisor) < 0 and max(dividend, divisor) > 0:
            sign = -1
        
        dividend = abs(dividend)
        divisor = abs(divisor)

        quotient = self.__divide(dividend, divisor)

        if sign == -1:
            quotient = -quotient
        if quotient > MAX_INT or quotient < MIN_INT:
            return MAX_INT
        return quotient


    def __divide(self, dividend, divisor):
        quotient = 0; # 商    
        origin_divisor = divisor
        i = 1
        while dividend >= divisor:
            quotient += i
            dividend -= divisor
            divisor += divisor
            i += i
        if dividend >= origin_divisor:
            quotient += self.__divide(dividend, origin_divisor)
        return quotient