题目大意
#
给定两个整数,被除数 dividend 和除数 divisor。要求返回两数相除的商,并且不能使用乘法,除法和取余运算。取值范围在 $[-2^{31}, 2^{31}-1]$。如果结果溢出,则返回 $2^{31} - 1$。
解题思路
#
题目要求不能使用乘法,除法和取余运算。
可以把被除数和除数当做二进制,这样进行运算的时候,就可以通过移位运算来实现二进制的乘除。
代码
#
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
|
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
MIN_INT, MAX_INT = -2147483648, 2147483647
# 标记被除数和除数是否异号
symbol = True if (dividend ^ divisor) < 0 else False
# 将被除数和除数转换为正数处理
if dividend < 0:
dividend = -dividend
if divisor < 0:
divisor = -divisor
# 除数不断左移,移位到位数大于或等于被除数
count = 0
while dividend >= divisor:
count += 1
divisor <<= 1
# 向右移位,不断模拟二进制除法运算
res = 0
while count > 0:
count -= 1
divisor >>= 1
if dividend >= divisor:
res += (1 << count)
dividend -= divisor
if symbol:
res = -res
if MIN_INT <= res <= MAX_INT:
return res
else:
return MAX_INT
|