/
Divide Two Integers.py
71 lines (62 loc) · 1.79 KB
/
Divide Two Integers.py
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import sys
class Solution:
# @param {integer} dividend
# @param {integer} divisor
# @return {integer}
def divide(self, dividend, divisor):
maxint = (1 << 31) - 1
minint = - 1 << 31
if divisor == 0:
return maxint
neg = False
if dividend * divisor < 0:
neg = True
dividend, divisor = abs(dividend), abs(divisor)
res, cur, minimum = 0, 1, divisor
while dividend >= minimum:
while (divisor << 1) <= dividend:
divisor <<= 1
cur <<= 1
dividend -= divisor
res += cur
while divisor > dividend:
divisor >>= 1 # cannot become minus
cur >>= 1
if neg:
res = -res
return max(minint, min(res, maxint))
class Solution:
# @return an integer
def divide(self, dividend, divisor):
if divisor == 0:
return (1 << 31) - 1
elif dividend == 0:
return 0
else:
a = abs(dividend)
b = abs(divisor)
count = 1
res = 0
while b > 0 and a > 0:
if a >= b:
a -= b
res += count
if b << 1 <= a:
b <<= 1
count <<= 1
elif a < b:
count >>= 1
b >>= 1
if dividend < 0:
res = 0 - res
if divisor < 0:
res = 0 - res
if res >= 2147483648:
return 2147483647
return res
if __name__ == '__main__':
a = Solution()
if len(sys.argv) == 1:
print a.divide(-2147483648, 1)
else:
print a.divide(int(sys.argv[1]), int(sys.argv[2]))