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。
0 条评论