LeetCode——两数相除

淡淡的烟草味﹌ 2022-05-18 00:08 154阅读 0赞

**题目：**

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

返回被除数 `dividend` 除以除数 `divisor` 得到的商。

**示例 1:**

输入: dividend = 10, divisor = 3
    输出: 3

**示例 2:**

输入: dividend = 7, divisor = -3
    输出: -2

**说明:**

*  被除数和除数均为 32 位有符号整数。
 *  除数不为 0。
 *  假设我们的环境只能存储 32 位有符号整数，其数值范围是 \[−231,  231 − 1\]。本题中，如果除法结果溢出，则返回 231 − 1。

**思想**：

以前CPU没有乘除法运算单元的时候就是用加减法实现乘除的，所以这里也是一样用减法就OK了，但是我们一般就想到每次减除数，但是这个方案会超时，那怎么办呢，又要减法，但是减除数又超时，那只能增大减去部分的大小了，增大的话不能用乘法，就只剩下移位的，左移的话就是除数\*2，那我们减去这个除数\*2，就相当于商+1\*2，如果在一个循环里移位找到小于被除数最大的减去部分的数的话，将大大减小我们的时间。

**代码**：

class Solution:
        def divide(self, dividend, divisor):
            """
            :type dividend: int
            :type divisor: int
            :rtype: int
            """
            negative_flag = False
            if divisor <0 and dividend>0 :
                divisor*=-1
                negative_flag = True
            elif divisor >0 and dividend<0 :
                dividend*=-1
                negative_flag = True
            elif divisor <0 and dividend<0:
                divisor *=-1
                dividend*=-1
            else:
                negative_flag=False
            if divisor == dividend:
                if negative_flag == True:
                    return -1
                return 1
            #上面是一些正负号处理和其他条件处理，本人不才，做不到简洁
            shang = 0
            yu = dividend
            cnt = 1
            while(yu >= divisor):#余数小于除数的时候，说明不能继续除了
                temp = divisor#最大的减数
                cnt =1
                while temp<=yu:#寻找最大的减数
                    temp <<=1
                    cnt <<=1 #除数*2，那我们的商也要加上*2的数
                temp >>=1#因为上面循环条件是大于就跳出，所以这里要还原一下
                cnt >>=1
                shang +=cnt #加上商
                yu -=temp
            #下面是一些条件处理
            if negative_flag==True:
                if shang >2147483648:
                    return 0
                return shang*-1
            if shang>2147483647:
                return 0
            return shang
    if __name__ =="__main__":
        res = Solution()
        print(res.divide(-2147483648,-1));
        pass