leetcode-29：两个数相除

题目描述：给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

1. 被除数和除数均为 32 位有符号整数。
2. 除数不为 0。
3. 假设我们的环境只能存储 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))