LCR 001 两数相除
一.题目：
. - 力扣（LeetCode）
二.原始解法-超时：
class Solution:
def divide(self, a: int, b: int) -> int:
# 1）分析：
# 除法计算，不能使用除法符号，可以理解为实现除法
# 除法原理是减法次数，a/b可以理解为a-b重复多次至结果小于0，假设此时余数为c
# 由于注意事项第一点已说明直接截取余数部分保留整数，返回重复次数即可，如果a，b正负不同，返回负数，否则返回正数
# 如果返回结果不在[−231, 231−1]范围，则返回231 − 1
# 2）判断输入有效性
if b == 0:
return
## 这里有一个易忘记知识点：python内置函数-幂计算x的n次方为x ** n
if a < -2 ** 31 or a > 2 ** 31 - 1 or b < -2 ** 31 or b > 2 ** 31 - 1:
return
if a == 0:
return 0
# 3）判断返回符号：
if a > 0 and b < 0 or a < 0 and b > 0:
symbol = -1
else:
symbol = 1
# 4) 使用while循环计算，按绝对值计算除法
## 这里有一个易忘知识点：python内置函数-绝对值为abs(-x)=x
current_a = abs(a)
abs_b = abs(b)
result = 0
while current_a - abs_b >= 0:
current_a = current_a - abs_b # 被除数刷新为差
result += 1
# 5）赋值符号
result = -result if symbol == -1 else result
# 6）判断结果溢出
if result < -2 ** 31 or result > 2 ** 31 - 1:
return 2 ** 31 - 1
else:
return result
三.正确解法及好的讲解、力扣解法参考：
好的讲解：《剑指 Offer》专项突破版 - 面试题 1 : 整数除法_输入2个int型整数,它们进行除法计算并返回商-CSDN博客
Python实现易于理解版本： . - 力扣（LeetCode）
四.对这个标准解法自己的消化分析：
首先被除数和除数的边界在 [−2 31 , 2 31 −1]范围中，题目描述中提到溢出情况，就是指商的数值超出了这个范围，那么什么情况下商会超出这个范围呢？可以把这个范围画到数轴上看一下，如下图：
上面这个图红色箭头表示超出范围的数值部分，推出了两种可能的不等式组，即
当商x<=0时，|x|>-a 或者 当商x>=0时，|x|>b。这两个不等式如果至少要成立一个，就得满足|x|大于-a和b的最小值，如果连这个条件都不满足，那么这个不等式组是不成立的。即|x|>min( 2 31 ， 2 31 −1 )，也就是|x|> 2 31 −1，那么为什么要用|x|而不是直接用x判断呢，因为除法的符号是根据除数和被除数是否符号一致判断的，为了使分析简单，可以先忽略符号。那么知道了溢出时候商x的最小值，看下当被除数和除数满足这个范围 [−2 31 , 2 31 −1] 时，是否会出现一个商处于这个溢出范围，也就是商的绝对值比 2 31 −1大，即|x|> 2 31 −1；
因为这是整数除法，所以商的绝对值一定小于被除数，又得到一个不等式：|a|/|b|=x且a、b皆为整数则|x|<|a|，再结合上面的结论，可以推出|x|的取值范围： 2 31 −1 < |x|<|a|，那么是否存在这种情况呢？只要判断是否存在 2 31 −1< |a|，有的，当|a|= 2 31 时，此时如果|b|=1，那么|x| = 2 31 了。
那么就是a = 2 31 时，b=1或-1；或a=- 2 31 时，b=1或-1，但是因为a的范围在 [−2 31 , 2 31 −1]之间，所以只有一种可能， a=- 2 31 ，b=-1结果是此时商会溢出，需要特殊处理。那么就在初始化的时候拦截这种输入，直接处理特殊场景即可，边界问题分析完了，现在看非特殊场景下求商绝对值的算法（刚才说了，商的符号先放到一边不考虑）
上面我的原始解法是最直观的根据除法的原理是减法来计算的，但是超时了，因为极端情况下当被除数为 2 31 −1，除数为1时，需要减 2 31 −1次，计算次数太多了。那么有没有简单办法呢？可以考虑刚才说的这种极端情况，如果每次减的不是除数，而是除数的N倍，然后商再加上这个N倍，就相当于减少了计算次数，其实就是利用除数膨胀N倍的时候，商会缩小N倍，这个N最好是2的n次方，这样计算次数就更少了。也就是说，用a和b的 2 31 倍数比较，如果a比这个小，就减少倍数为2的30次，这样一直减少到a比b扩大2的某次方要大，说明a-b一定大于2的某次方，那么a除以b的2的某次方的商一定大于1，也就是a除以b一定大于商乘以2的某次放，举个例子：17/1=17，如果用原始减法算，需要计算17次，如果用17-1*2的4次方，发现此时差大于0，那么17/1的商一定大于2的4次方，因为17就是比1大那么多倍，即商=16，然后计算17-1*2的4次方=1，此时差=除数，商再加1直到差<除数。即上面力扣解法中的这部分核心代码：
temp是2的n次方的n，从31次方开始倒推，只要a比b*2的n次方大，a就减去当前被扩大了的除数（其实还是用了除法的原理是减法，只是除数膨胀了），quo是商，当除数膨胀了的时候，商也要膨胀，因为计算次数被减少了，膨胀的数值就是b扩大的倍数
同时这道题扩大n倍由于题目要求不能使用乘法，只能使用位移，Python中的左移<<就是扩大2的n次方，又因为要判断a，b的输入值处理溢出，需要了解python中2的n次方运算符是**
五.实现如下：
class Solution:
def divide(self, a: int, b: int) -> int:
# 处理a，b是否在题目范围，及除数是否为0非法，退出计算
if a < -2**31 or a > 2**31 +1 or b < -2**31 or b > 2**31 +1 or b == 0:
return
# 处理会导致商溢出的情况 a=-2**31，b=1或-1，直接按题目要求返回溢出默认值
if a == -2**31 and b == -1:
return 2**31 - 1
# 处理被除数为0，直接返回0
if a == 0:
return 0
# 处理非特殊情况，先简化除法为绝对值，flag为商的符号，然后a，b取绝对值
flag = True if (a > 0 and b > 0) or (a < 0 and b <0) else False
a,b = abs(a),abs(b)
# temp为2的n次幂的n，即除数左移位数，初始化为题目最大值31，quo为商，当temp为最大值时，商初始化为最小值0
temp,quo = 31,0
# 开始用除法原理减法+除数倍数膨胀计算
while temp >= 0:
if a >= b << temp:#此时可以处理商和被除数了
a -= b << temp
quo += 1 << temp
temp -= 1
# 计算完成，给商赋符号
if not flag:
quo = -quo
return quo
