LeetCode29 Medium 除法与二进制优化

链接

Divide Two Integers

难度

Medium

描述

给定两个整数，被除数和除数，要求在不使用除号的情况下计算出两数的商

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

样例 1:

Input: dividend = 10, divisor = 3
Output: 3

样例 2:

Input: dividend = 7, divisor = -3
Output: -2

注意:

• 除数和被除数都在32位int的范围内

• 除数不为0

• 对于超界的情况返回$2^{31}-1$

• Both dividend and divisor will be 32-bit signed integers.

• The divisor will never be 0.

• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [− $2^{31}$ , $2^{31}$ − 1]. For the purpose of this problem, assume that your function returns $2^{31}$ − 1 when the division result overflows.

题解

老规矩，我们依然从最简单的情况开始入手。我们都知道，在计算机内部，是二进制的，而二进制是只能进行加减的。所以没错，所有的乘法和除法的操作其实最终都会转换为加减法来进行。对于这道题而言也是一样的，既然禁止我们使用除法，那么我们可以用减法来代替。

暴力

最简单的策略就是我们可以用一个循环去不停地减，然后用一个累加器计算到底执行了多少次减法，当不够减的时候则停止。整个流程非常简单，但是我们还需要考虑一下正负号的问题，按照排列组合来看，被除数和除数一共有4中正负号的情况。但我们并不需要考虑那么多，这四种情况可以简单地归并成是否同号两种，然后进一步分析又会发现是否同号的计算过程并没有差别，唯一会影响的只有最后结果的正负号。

还有一点比较令人在意的是提示当中说的可能会超界的情况，我们来分析一下，其实会超界的可能性只有一个。那就是 $-2^{31}$ 除以-1的情况，会得到 $2^{31}$ ，而32位int的正数范围最大是 $2^{31}-1$ ，所以我们需要在意这个问题。不过好在对于Python而言，int是没有范围的，所以可以忽略这个问题，只需要最后特判一下结果，但是对于C++和Java等语言而言，需要特判一下这个case。

我们来总结一下上面的过程，我们可以先将除数和被除数全部转化为正数，然后用一个标记flag来记录它们是否同号。再计算完结果之后，需要判断一下结果的范围是否越界，如果越界返回 $2^{31}-1$ 。

代码如下：

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 判断是否同号
        flag = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)
        ret = 0
        # 全部赋值为正
        dividend, divisor = abs(dividend), abs(divisor)

        start = 0
        # 模拟除法
        while start + divisor <= dividend:
            start += divisor
            ret += 1

        # 防止越界，注意只有正数才有可能越界
        return min(ret, (1 << 31) - 1) if flag else -ret

这个代码当然是没有问题的，但是如果你真的这么提交，那么一定会超时。原因也很简单，当除数非常小，比如是1的时候，那么我们的循环次数就是被除数的大小。当我们给定一个很大的被除数的时候，会超时就是显然的了。

二进制优化

接下来讲的这个算法很重要，是快速幂等许多算法的基础，由于本题当中不是进行的幂运算，所以不能称作是快速幂算法，一时间也没有什么好的名字，由于本质上是通过二进制的运算来优化，所以就称为二进制优化吧。

在讲解算法之前，我们先来分析一下bad case出现的原因。之所以会超时，是因为有可能被除数非常小，比如是1，这个时候我们一位一位地减就非常耗时。那么很自然地可以想到，我们可不可以每次不是减去一个1，而是若干个1，最后把这些减去的数量加起来，是不是会比每次减去一个要更快一些呢？但是还有细节我们不清楚，我们怎么来确定这个每次应该减去的数量呢？如果确定了之后发现不够减，又应该怎么办呢？

要回答上面这个问题，需要对二进制有比较深入的理解。我们先把刚才的问题放一放，来看一看二进制对于除法的解释。举个简单的例子，比如15 / 3 = 5。我们知道15等于5个3相乘，那么我们把它们都写成二进制。15的二进制是1111，3的二进制是0011，5的二进制是0101，我们重点来看这个5的二进制。

5的二进制写成0101，展开的话会得到是 $2^2 + 2^0 = 4 + 1$ ，也就是说我们可以把15看成 $(2^2+2^0)*3$ ，这个式子写成是 $(0*2^3+1*2^2+0*2^1+1*2^0)*3=15$ 。也就是说我们可以把被除数看成是若干个2的幂乘上除数的和，这就把一个除法问题转化成了加法问题。同样我们把求解商转化成了求解商的二进制表达，二进制表达有了，最后的商无非是再进行一个求和累加即可。

最后，我们来分析一下，为什么能够优化。因为题目当中已经限定了，除数和被除数都在32位的int范围。也就是说最多只有32个二进制位，那么我们的循环次数最多也就是32次。通过二进制优化，我们把原本一个 $O(n)$ 的问题，降级成了 $O(\log n)$ ，这两者之间差了不止一个数量级，当然要快得多。

我们把上面这个思路写成代码，就可以得到答案：

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 前面处理和之前一样
        flag = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)
        ret = 0
        dividend, divisor = abs(dividend), abs(divisor)

        # 预处理二进制数组
        binary = [0 for _ in range(33)]
        # 第0位即2的零次方乘上除数，所以就是除数本身
        binary[0] = divisor
        for i in range(1, 33):
            # 后面每一位是前面一位的两倍，因为二进制
            # << 是位运算左移操作，等价于*2，但是速度更快
            binary[i] = binary[i-1] << 1

        for i in range(32, -1, -1):
            if binary[i] <= dividend:
                dividend -= binary[i]
                # 答案加上2^i
                ret += (1 << i)
        return min(ret, (1 << 31) - 1) if flag else -ret

这段代码不长，也没有用到什么特别牛哄哄的算法，无非是对二进制的一些运用。但是对于对二进制不够熟悉的初学者而言，想完全搞明白可能有些费劲，这也是很正常的。希望大家能够沉下心来好好理解，如果实在看不懂也没关系，在以后快速幂等算法当中，还会和它见面的。

今天的文章到这里就结束了，如果喜欢本文的话，请来一波素质三连，给我一点支持吧（关注、在看、点赞）。