题目描述：给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。
本题中，如果除法结果溢出，则返回 231 − 1。
考虑溢出，当被除数为， 除数为-1，商为
，会溢出
返回被除数 dividend 除以除数 divisor 得到的商。
看到这个题首先考虑到的思路是：不断用被除数去减出除数，然后记下减的次数，假设计算m/n,时间复杂度为O(m/n)，用Python 实现会显示超出时间限制。
在网上尝试找到一个优化的解答方案，利用位运算，意思是任何一个整数可以表示成以2的幂为底的一组基的线性组合，即。基于以上这个公式以及左移一位相当于乘以2，我们先让除数左移直到大于被除数之前得到一个最大的基n的值，说明被除数中至少包含2^m个除数，然后减去这个基数，再依次找到m-1，…，1的值。
迭代次数是按2的幂知道超过结果，所以时间复杂度为O(log(n))。 将所有的基数相加即可得到结果。
def divide (dividend: int, divisor: int) :
sign = -1 if ((dividend<0) ^ (divisor<0)) else 1 ##异或
dividend = abs(dividend)
divisor = abs(divisor)
if divisor==1:
return min(2**31-1, max(-2**31, sign*dividend))
res=0
while dividend >= divisor:
tmp = divisor
p = 1
while dividend >= (tmp<<1):
p <<= 1
tmp <<= 1
res +=p
dividend -= tmp
return min(2**31-1, max(-2**31, res*sign))
