来自 leetcode 的一个题目，题目大概意思是给定两个数计算其商，要求不能用乘法、除法和 mod 运算符来做计算。

该题目在leetcode 打的标签是 Medium（中等难度），而接受率仅有16.6%，题目并不难，但接受率挺低的。

一、暴力法
读完这个题目，最直接的想法就是来个暴力运算了：被除数大于除数时候，不断用被除数减去除数，一直到它小于除数为止，所减的次数，就是商了。

但该算法致命的缺点：慢，当被除数远远大于除数时候，就不得不做大量的循环操作了（比如 123456789 / 2 ，得循环 61728394 次），时间复杂度是O(n)。我试过提交这样的算法，提交运行结果是超时，估计16.6%的接受率之外的提交，包含有很多这种算法了。

二、迭代法
这里定义被除数为 a，除数为 b，为了简化问题，这里假定a 和b 均为非负数（如果存在负数，根据情况取反为正数，算出结果后再做符号变换就可）。a 和 b 的关系不外乎就三种了：a 小于 b；a 在 b 和 2b 之间；a 大于 2b。

对这三种情况分别分析 a / b 的结果：
2.1） a < b 时候，商和余数 分别为：0，a
2.2） b <= a < 2b 时候，商和余数 分别为：1，a – b
2.3） a > 2b 时候，可以考虑先算 a / （2b），假设 计算 a / （2b） 得商 x，余数 y。这里再看 y 的情况，y 和 b 关系 可分为下面两种情况：
2.3.1）如果 y < b, 那么得到，a / b 的商和余数分别为 2x，y 了
2.3.2）如果 y >= b (y是不可能是大于等于 2*b 的)，则有 a / b 商和余数 分别为 2x+1, (y-b)了。

总结下 a > 2b 情况，算 a / b 可以先算 a / 2b，令 c = 2b， 也就是算 a / c，而算 a / c 和 算 a / b 没有啥差别的，也是同样的过程，如果a 还大于2c，则先算 a / 2c，令 d = 2c，也就是算 a / d， 继续如果 a 还大于 2d，令 e = 2d ……如此迭代下去。

就算被除数远大于除数，按这个思路，除数两倍两倍的放大，使得运算量会快速减少，从而加快了运算，其时间复杂度为O(logn)。

三、代码实现
Solution.divide 只是做一些边缘条件的判断的，主要实现在 Solution._divide 函数内。 为便于读解，代码去除了原题要求的“-2^31 <= dividend, divisor <= 2^31 – 1” 的约束，题目要求不能用乘法，但没有说不能用左移（<<），就算不能用 左移也没有关系，用 + 来代替代码的<<1 即可。同时，代码的 -n 不是 -1 * n，应该读解为 0 – n：

class Solution:
    '''
    def _divide(self, dividend: int, divisor: int):
        result = 0
        while dividend > divisor:
            dividend -= divisor
            result += 1

        return result, dividend
    '''

    def _divide(self, dividend: int, divisor: int) -> (int,int):
        if dividend < divisor:
            # 被除数小于除数，直接返回就可
            return 0, dividend

        doubleDivisor = divisor << 1
        if divisor <= dividend and dividend < doubleDivisor:
            return 1, dividend - divisor

        result, mod = self._divide(dividend, doubleDivisor)
        result = result << 1

        if mod >= divisor:
            mod -= divisor
            result += 1

        return result, mod

    def divide(self, dividend: int, divisor: int) -> int:
        if divisor == 0:
            return 0

        positive = True
        if dividend < 0:
            dividend = -dividend
            positive = not positive

        if divisor < 0:
            divisor = -divisor
            positive = not positive

        result, mod = self._divide(dividend, divisor)

        if not positive:
            result = -result

        return result

四、最后
提交的结果“Your runtime beats 97.89 % of python3”，看来这样的方法还是不错的。

另外如果计算 x^n，规定不能用库函数，也是可以用类似的算法思想来实现。

（全文完）

（欢迎转载本站文章，但请注明作者和出处 云域 – Yuccn ）