【LeetCode】0029 两数相除

https://leetcode-cn.com/problems/divide-two-integers/

# -*- coding:utf-8 -*-

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        negative = False
        res = 0
        count = 0
        if divisor < 0 < dividend:
            negative = True
        if dividend < 0 < divisor:
            negative = True
        dividend = abs(dividend)
        divisor = abs(divisor)
        while dividend >= divisor:
            count += 1
            divisor <<= 1
        while count > 0:
            count -= 1
            divisor >>= 1
            res <<= 1
            if dividend >= divisor:
                res += 1
                dividend -= divisor
        if negative:
            res = -res
        return res if -(1 << 31) <= res <= (1 << 31)-1 else (1 << 31) - 1
if __name__ == '__main__':
    dividend = -2147483648
    divisor = 1
    # dividend = 10
    # divisor = 3
    print(Solution().divide(dividend, divisor))

思路：二进制偏移，因为不让用乘除法，所以采用类似的二进制偏移计算，左移相当于乘二，右移相当于除二。

我们举一个20/4的例子。设d=20，r=4，result（res）初始化为0。

首先我们将r左移直至大于d，于是我们有8，16，32。经过三次左移r=32>d=20。

然后我们进行除法计算。

首先：

r右移，然后判断d是否大于r，如果大于r说明res中当前位为1。

显然20>16，因此res+=1（res=1），然后d = d-r = 20-16=4。

继续下一步：

r右移=8，显然d=4<r=8，res右移但是不加一，res=10（二进制）,d

不变。

下一步：

r右移=4，显然d=4=r=4，res右移加一，res=101（二进制）,d = d – 4 = 0（如果不能整除这里也就不是0，但是一定小于4，因为如果这里大于4那么在计算之前r就大于8了，在上一步就处理掉了）。

由于我们只对r进行了三次右移，因此到这里计算结束，结果res=101=5。