[Leetcode][python]Divide Two Integers

浅浅的花香味﹌ 2022-05-28 02:38 161阅读 0赞

## 题目大意 ##

除法运算，但是不能用编程语言提供的乘法、除法和取模运算，即只能用加法和减法实现。

## 解题思路 ##

[https://blog.csdn.net/qian2729/article/details/50528758][https_blog.csdn.net_qian2729_article_details_50528758]

## 代码 ##

class Solution(object):
        def divide(self, dividend, divisor):
            """
            :type dividend: int
            :type divisor: int
            :rtype: int
            """
            MAX_INT = 2147483647
            sign = 1 if (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0) else -1
            quotient = 0
            dividend = abs(dividend)  # 被除数
            divisor = abs(divisor)  # 除数
            while dividend >= divisor:
                k = 0
                tmp = divisor
                # 减去1，2，4，8逐渐加速，直到被除数小于除数，然后出内部while，k置为0，再重新加速。最终等到直接小于被除数
                while dividend >= tmp:
                    dividend -= tmp
                    quotient += 1 << k
                    tmp <<= 1
                    k += 1
            quotient  = sign * quotient
            if quotient > MAX_INT:
                quotient = MAX_INT
            return quotient

### 补充思路 ###

[https://blog.csdn.net/zdavb/article/details/47108505][https_blog.csdn.net_zdavb_article_details_47108505]

**计算机计算除法**

计算机计算除法的过程与人类计算的过程很类似，只是选择范围变成了0或1.  
还以51/3为例说明（51：110011；3:11）

从第一位开始为1，小于11，结果位置0；余数为1  
从第二位开始，余数\*2+1=11，等于11，结果位置1，余数为0；  
从第三、四位开始，余数\*2+0=0<011,结果位置0，余数为0  
从第5位开始，余数\*2+1=1<11，结果置0，余数为1  
从第6位开始，余数\*2+1=11=11，结果置1，余数为0.

此时将结果位相连，恰好是10001（17）

## 总结 ##

[https_blog.csdn.net_qian2729_article_details_50528758]: https://blog.csdn.net/qian2729/article/details/50528758
[https_blog.csdn.net_zdavb_article_details_47108505]: https://blog.csdn.net/zdavb/article/details/47108505