给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
说明:
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [?231, 231 ? 1]。本题中，如果除法结果溢出，则返回 231 ? 1。
class Solution:
def divide(self, dividend, divisor):
is_positive = 1 if (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0) else -1
dividend = dividend if dividend > 0 else -dividend
divisor = divisor if divisor > 0 else -divisor
# 除数大于被余数，商为0
if dividend < divisor:
return 0
# 除数为-1或1，商为被除数
if divisor == 1:
return is_positive * dividend if -2 ** 31 <= is_positive * dividend <= 2 ** 31 - 1 else 2 ** 31 - 1
quotient = 0
# 当被除数大于除数
while dividend >= divisor:
tmp = divisor
cnt = 1
# 除数左移一位（即乘以2的1次方），直到找到最大的除数(除数*cnt)
while tmp << 1 <= dividend:
cnt = cnt << 1
tmp = tmp << 1
# 如果商为上次商值+cnt，如果不左移cnt=1
quotient += cnt
# 被除数减去除数，如果不左移tmp=divisor
dividend -= tmp
return is_positive * quotient if -2 ** 31 <= is_positive * quotient <= 2 ** 31 - 1 else 2 ** 31 - 1
