LeetCode50，一题学会快速幂

题意

这道题的题意只有一句话，就是给定两个数x和n，要求。

从题意来看，这道题平平无奇，基本上没有什么特别的。但是我们继续看它的note就会发现问题，其中x是浮点数，它的范围是-100到100。而n的范围则是32位int的范围，到这里就有问题了。

因为如果n很大，我们用循环去计算的话一定会超时。我们之前讨论过这个问题，即使是运算最快的C++，一秒钟内的运算次数也只有10的8次方左右。而32位的int高达10的9次方，如果是Python的话这个运算会更慢，所以我们用循环肯定是无法得出结果的。

快速幂

这道题目把复杂度限制死了，我们从暴力方法入手是想不出结果的，必须要引入新的算法。而针对本题的算法就是快速幂。

快速幂算法本质上也是二进制算法的变形，需要基于我们对二进制的充分理解，某种程度上来说它和多重背包问题当中的二进制拆分的解法比较近似。都需要对整数进行拆分，不过不同的是在背包问题当中拆分的结果进行的累加运算，而这里则是累乘。

如果你没有看过多重背包问题，也没有关系，我会从头开始将它讲清楚。

快速幂的算法好理解，但是看懂了很容易忘，尤其是初学的时候。学的时候理解了，过两天就忘了，或者代码写不出来了，这很正常。所以我们先从根本问题出发，从根源上理解它，而不只是运作原理。

第一个问题：我们使用快速幂的原因是什么？

这个问题很好回答，当然是因为快啊，不然的话我们用循环计算幂不行么。但是为什么快速幂就快呢？为什么它比循环快呢？

这个问题哪怕我们没有学过快速幂的算法，也是可以回答的，它的答案也很简单，因为我们把一个原本不太好求的量转化成了一个很容易求解的量，从而降低了复杂度。说起来是废话的东西，但其实是很多算法的本质。算法也不是天上掉下来的，想出算法的人也不是凭空拍脑袋就出来的，最核心都是有一个原理可寻的。很多算法的核心原理，其实就是用转化和代替的方法求本来不是特别方便求的值。这个方法不仅在数学上常用，在算法上也是一样。

我们理解了这个核心之后，剩下的就简单了，我们知道不好求，因为我们现在没什么好的办法，那什么量是容易求的量呢？又该怎么转化呢？顺着这个思路，我们眼前的世界清楚了很多。

原本我们求解的方法就是通过循环，每次循环都乘上一个x，循环n次之后得到结果。我们观察一下这个过程，会发现我们在循环的时候，每一次循环，其实都代表了x的指数增加了1。也就是说它是线性增长的，当然就慢了。那什么增长比较快呢？指数增长比较快，比如我们一直翻倍翻倍，就很快。有一个关于指数增长的著名故事，说是从前有一个人发明了国际象棋。当地的国王非常喜欢下棋，于是他就把这个发明者召到了面前来说，你这个发明很好，我愿意奖赏你，你说吧，你想要什么，只要我能给的都行。

这个人说，陛下我想要的很简单，只要一些米。我希望第一个格子里放1颗米，第二个格子里放2颗，第3个格子里放4颗。每一个格子里放的都是前面的2倍，请陛下把这些米赏赐给国家里的穷人吧。

国王很震惊，觉得这个人是不是缺心眼，这么好的机会怎么只要了这么点赏赐。但是我们都知道，国际象棋一共有八八六十四格，我们按照这样放满，需要颗米。这显然是一个天文数字，别说一个国家了，就是全世界的米加起来也没这么多。故事里没提这个人最后的结局，很有可能因为戏弄国王被砍死了。但不管结局如何，至少说明了一个问题，指数增长和我们的直觉不符，它的变化极快。

所以我们希望要是我们的指数也可以这样成倍地增长而不是每次只增加1就好了，那么我们怎么让指数成倍增长呢？这个就很简单了，平方就好了。

我们把x平方就得到了，我们再把它平方就得到了，我们每次平方完，指数都翻了一倍，就好像刚才故事里的棋盘一样。所以我们只需要很少的次数就可以让指数变得很大。

我们解决了指数增长速度的问题，但是又遇到了新的问题，我们这样增长是很快，但是它翻倍再翻倍不一定就能得到n呀？

这个问题也简单，直接得到不可能就想办法凑呗。举个例子，比如我们的n=15，我们先找到小于15的最大的2的幂，发现是8。所以我们先得到了，我们把它放在一边之后还剩下了7，我们再来凑7，又找到了4，于是再放到一边，还剩下3，我们再来凑3……如此循环往复直到凑齐了n为止，n是一定可以这样凑到的，因为这本质上就是一个转化成二进制的过程。

我把整个过程画成了一张图，我们来看下图：

我们先算出所有2的幂，然后在算出所有x的2的幂次方。再把n拆成二进制，把二进制当中对应位置是1的值乘起来，就得到了结果。

有些同学可能不太熟悉二进制和位运算，我会提供两个版本的代码，帮助大家理解。我们先来看简单一些的代码：

class Solution:
    def myPow(self, x: float, n: int) -> float:
        base = []
        # 标记n是否为负数
        flag = n < 0
        # 把n置为正数
        n = abs(n)
        base.append(x)
        # 我们算出所有的x^2^i
        for i in range(32):
            base.append(base[-1] * base[-1])
            
        ret = 1.0
        # 遍历32个二进制位
        # 如果i位为1，那么答案乘上base[i]
        for i in range(32):
            if ((1 << i) & n) > 0:
                ret *= base[i]
        # 如果n为负数返回1/ret
        return 1/ret if flag else ret

在上面这段代码当中我们是先算出了每一个，然后我们再根据n转化成二进制的结果将它们乘在了一起。当然，我们熟练了之后是可以不这么费劲的，我们可以把这两步合并在一起，我们再来看一段代码：

class Solution:
    def myPow(self, x: float, n: int) -> float:
        base = []
        flag = n < 0
        n = abs(n)
        
        base = x    
        ret = 1.0
        # 我们在遍历二进制位的时候顺便求出x^2^i
        for i in range(32):
            if ((1 << i) & n) > 0:
                ret *= base
            # x^2^i = x^2^(i-1) * x^2^(i-1)
            base *= base
        
        return 1/ret if flag else ret

总结

到这里关于快速幂的讲解就结束了，我个人感觉应该还是比较清楚的，算法的核心根基还是二进制，如果对二进制的概念掌握了，快速幂算法就是小意思了。

可能你会觉得奇怪，为什么非要用二进制而不是三进制、四进制呢，不是更快吗？原因有两个，一个是计算机底层基于二进制，我们暂时没有找到一个很好的材料可以实现三进制，因为二进制很简单，逻辑门开和关，带来高低电平表示状态就好了，但是三个状态用什么材料来实现呢？第二个原因是没有必要，多进制的确会更快，但是很有限，所以没有这个必要。

说来也不怕笑话，我在刚开始入门的时候，一直是用上的上面那种比较蠢的方法。而且放眼题解，至今没有找到一个人用这种蠢办法写快速幂的。但是代码蠢没有关系，能够运行，能够AC，能够理解才是关键。一开始写蠢点的代码没有关系，只要保持进步，以后自然会越来越好的。