力扣（29）

水深无声 2022-09-11 12:30 164阅读 0赞

# 题目描述 #

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

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

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3
    输出: 3
    解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:

输入: dividend = 7, divisor = -3
    输出: -2
    解释: 7/-3 = truncate(-2.33333..) = -2

提示：

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

# 解题 #

## 1. 减法代替除法 ##

乘法是加法的简单运算，乘法的问题可以用加法解决，那么除法的问题是否可以用减法解决

令a = 22,b = 3
    a/b = 7···1
    22-3 = 19
    19-3 = 16
    16-3 = 13
    13-3 = 10
    10-3 = 7
    7-3 = 4
    4-3 = 1

代码①实现：

def divide(a,b):
        i = 0
        while(a>=b):
            a = a - b
            i = i + 1
         return i  # i为商，a为余数

但是这个代码的前提是a,b都为正数，如果不为正数，则不成立。

所以可以考虑把a和b的符号提取出来，最后加到结果上去。

代码②实现：

def divide(a,b):
        i = 0
        sign = -1 if (a>0)^(b>0) else 1
        a,b = abs(a),abs(b)
        while(a>=b):
            a = a - b
            i = i + 1
         return i if sign ==1 else -i  # i为商，a为余数

这个代码已经可以在测试中成功了，可以进行初步提交

### 2. 考虑一下越界问题 ###

提示中还有一行内容：

环境中只能存储32为有符号整数，如果溢出会怎么样？

现实中的数学不用去考虑这个东西，但在计算机中我们应该去考虑。

代码③实现：

#32 位最大值：2^31 - 1 = 2147483647
    #32 位最小值：-2^31 = -2147483648
    def divide(a,b):
    	INT_MIN, INT_MAX = -2**31, 2**31 - 1
        if a == INT_MIN and b == -1:
            return INT_MAX
        i = 0
        sign = -1 if (a>0)^(b>0) else 1
        a,b = abs(a),abs(b)
        while(a>=b):
            a = a - b
            i = i + 1
         return i if sign ==1 else -i  # i为商，a为余数

### 3 . 降低时间复杂度（这部分开始就是参考别人的了，我的脑容量不足以支持我想到） ###

令a = 22,b = 3,k = 1			    		
    22 - (3 + 3)     	k = k + k = 2   	
    22 - (6 + 6) = 10   k = k + k = 4   	
    22 - (12 + 12) < 0  k = k + k = 8

代码④实现：

def divide(a,b):
    	INT_MIN, INT_MAX = -2**31, 2**31 - 1
        if a == INT_MIN and b == -1:
            return INT_MAX
        i = 0
        sign = -1 if (a>0)^(b>0) else 1
        a,b = abs(a),abs(b)
        
        while(a>=b):
        	value,k = b,1
            while(a>=value+value):
            	k += k
                value += value
            i,a = i+k,a-value
            
         return i if sign ==1 else -i  # i为商，a为余数

### 4. 位运算优化 ###

令a = 22,b = 3,k = 1			    		22 - (3<<0)
    22 - (3 + 3)     	k = k + k = 2   	22 - (3<<1)
    22 - (6 + 6) = 10   k = k + k = 4   	22 - (3<<2)
    22 - (12 + 12) < 0  k = k + k = 8   	22 - (3<<3)

代码⑤实现：

def divide(a,b):
    	INT_MIN, INT_MAX = -2**31, 2**31 - 1
        if a == INT_MIN and b == -1:
            return INT_MAX
        ans = 0
        sign = -1 if (a>0)^(b>0) else 1
        a,b = abs(a),abs(b)
        
        for i in range(31,-1,-1):
            if(a>>i) - b >=0:
                a = a -(b<<i)
                ans += 1 <<i
            
         return ans if sign ==1 else -ans  # ans为商

来源：力扣（LeetCode）  
[链接][Link 1]：https://leetcode-cn.com/problems/divide-two-integers  
[参考题解][Link 2]：https://leetcode-cn.com/problems/divide-two-integers/solution/jian-dan-yi-dong-javac-pythonjs-liang-sh-ptbw/

[Link 1]: https://leetcode-cn.com/problems/divide-two-integers
[Link 2]: https://leetcode-cn.com/problems/divide-two-integers/solution/jian-dan-yi-dong-javac-pythonjs-liang-sh-ptbw/