给定两个整数，被除数 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。
思路
除法其实可以用加法的思路做，循环减去divisor就好了，这样的时间复杂度是\(O(dividend)\)，遗憾的是这样是过不了的。所以要另辟蹊径，用位运算。
\(dividend = quotient*divisor + remainder\)
解法：
- 枚举\(i\)（降序）找到使得$divisor << i \(能够比\)dividend$小的，规定一个暂时变量tmp，更新tmp
- 不断更新\(tmp + (divisor << i)\)比\(dividend\)小的位置\(i\)，并记录下来
代码
class Solution(object):
def divide(self, dividend, divisor):
"""
:type dividend: int
:type divisor: int
:rtype: int
"""
if dividend == 0: return 0
if divisor == 0: return
sign = -1 if ((dividend < 0) ^ (divisor < 0)) else 1 #标记是否为负
dividend = abs(dividend)
divisor = abs(divisor)
quotient = 0
tmp = 0
for i in range(32,-1,-1): #逆序枚举，范围为[0,32]
if tmp + (divisor << i) <= dividend:
tmp += divisor << i #更新tmp的值
quotient |= 1 << i #记录i的位置，从2进制的或运算就是有1就为1
quotient *= sign #虽然题目说了不要用乘法，但是为了代码的简洁这里还是用了
if quotient < -(2 ** 31) or quotient > 2 ** 31 - 1:
return 2 ** 31 - 1
else:
return quotient