描述
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。1
2
3
4
5
6
7示例 1:
输入: dividend = 10, divisor = 3
输出: 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
说明:
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−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
32
33def getsign(num):
# 取一个数的符号，看是正还是负
# 负数返回0xffffffff（-1），正数返回0x00000000（0）
return num 31
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
MAX = 2147483647
# 被除数和除数是否同号
diff_sign = getsign(divisor) ^ getsign(dividend)
a = abs(dividend)
b = abs(divisor)
# 想法是：让被除数去减除数*n倍，找到这个最大能减的n
# 这里采用类似"二分"查找的思路，先从最大2的31次方开始试探
ans = 0
i = 31
while i >= 0:
# 比较a是否大于b*(1<<i)=b<<i
# 这里有可能b<<i会溢出，换个方向，将a右移i位，即a>>i
if (a i) >= b: # 如果够减
ans += 1 << i
a -= (b << i)
i -= 1
# 如果两个数异号，商肯定是负数
if diff_sign != 0:
ans = ~ans + 1 # 取一个数的相反数，操作是按位取反+1
# 判断一下是否商溢出
if ans > MAX:
return MAX
else:
return ans
是可以通过的，但是效率也不很高，内存开销比较大，对这方面了解不深，麻烦知道的朋友下面留个言交流一下。
