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