LeetCode 29 Divide Two Integers

Posted on | In | 阅读

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

If it is overflow, return MAX_INT.

overflow特殊情况：-2147483648 / (-1) = MAX_INT = 2147483647

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
class Solution:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if dividend == -2147483648 and divisor == -1:
            return 2147483647
        a = abs(dividend)
        b = abs(divisor)
        arr = []
        while(b <= a):
            arr.append(b)
            b <<= 1
        sum = 0
        ret = 0
        for i in range(len(arr)-1, -1, -1):
            if sum + arr[i] <= a:
                sum += arr[i]
                ret += (1<<i)
        if(((dividend > 0) and (divisor < 0)) or ((dividend < 0) and (divisor > 0))):
            return -ret
        else:
            return ret