关于快速幂即快速算某个数的多少次幂，我第一次接触时，特别懵比，Leetcode中有一道这样的题，当时用了暴力法，没有通过，超出时间限制。 暴力法： 采用循环乘n个x

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        output = x
        if n>0:
            for i in range(n-1):
                output = output*x
        elif n == 0:
            output= 1
        else:
            for i in range(-n-1):
                output = output*x
            output = 1/output
        return output

下面从二进制角度出发，给出快速幂的一种解法：

二进制角度：

如求 x n x^n xn， 对于任何十进制正整数 n ，其二进制为 1 ∗ b 1 + 2 ∗ b 2 + 4 ∗ b 3 + . . . + 2 m − 1 ∗ b m 1*b_1+2*b_2+4*b_3+...+2^{m-1}*b_m 1∗b1+2∗b2+4∗b3+...+2m−1∗bm ， 故： x n = x 1 ∗ b 1 + 2 ∗ b 2 + 4 ∗ b 3 + . . . + 2 m − 1 ∗ b m x^n=x^{1*b_1+2*b_2+4*b_3+...+2^{m-1}*b_m} xn=x1∗b1+2∗b2+4∗b3+...+2m−1∗bm = x 1 ∗ b 1 ∗ x 2 ∗ b 2 ∗ x 4 ∗ b 3 ∗ . . . x 2 m − 1 ∗ b m =x^{1*b_1}*x^{2*b_2}*x^{4*b_3}*...x^{2^{m-1}*b_m} =x1∗b1∗x2∗b2∗x4∗b3∗...x2m−1∗bm

如当n=3时，二进制为：11 x 3 = x 1 ∗ 1 + 2 ∗ 1 x^3=x^{1*1+2*1} x3=x1∗1+2∗1 = x 1 ∗ 1 ∗ x 2 ∗ 1 =x^{1*1}*x^{2*1} =x1∗1∗x2∗1

如当n=8时，二进制为：1000 x 8 = x 1 ∗ 0 + 2 ∗ 0 + 4 ∗ 0 + 8 ∗ 1 x^8=x^{1*0+2*0+4*0+8*1} x8=x1∗0+2∗0+4∗0+8∗1 = x 1 ∗ 0 ∗ x 2 ∗ 0 ∗ x 4 ∗ 0 ∗ x 8 ∗ 0 =x^{1*0}*x^{2*0}*x^{4*0}*x^{8*0} =x1∗0∗x2∗0∗x4∗0∗x8∗0

因此一个想法是循环赋值操作 x = x 2 x = x^2 x=x2即可 x n = x n / 2 × x n / 2 = ( x 2 ) n / 2 x^n=x^{n/2} ×x^{n/2} =(x^2 ) ^{n/2} xn=xn/2×xn/2=(x2)n/2， 如下代码：while循环中，res在二进制位数值为1时执行 r e s ∗ x res*x res∗x操作，每次 x 执行平方操作，n除以2

class Solution:
    def myPow(self, x, n):
        if x == 0.0: return 0.0
        res = 1
        if n < 0: x, n = 1 / x, -n
        while n:
            if n & 1: res *= x
            x *= x
            n >>= 1
        return res

n&1 （与操作）： 判断 n 二进制最右一位是否为 1，为1则乘以x ； n>>1 （移位操作）： n 右移一位（可理解为删除最后一位），即n//2 n//2 需要分为奇偶两种情况： 下面以n=9（1001）为例：

其中 x ∗ x 8 x*x^8 x∗x8中第一个x对应的是1001中低位上的1， x 8 x^8 x8对应的是高位上的1 以n=8（1000）为例：

复杂度分析： 时间复杂度 O(logn) ： 二分的时间复杂度为对数级别。 空间复杂度 O(1) ： res, bb 等变量占用常数大小额外空间

递归

当我们要计算 x n x^n xn时，我们可以先递归地计算出 y = x n / / 2 y=x^{n//2} y=xn//2 根据递归计算的结果：

如果 n 为偶数，那么 x n = y 2 x^n = y^2 xn=y2； 如果 n 为奇数，那么 x n = y 2 ∗ x x^n = y^2 * x xn=y2∗x

递归的边界为 n = 0，任意数的 0 次方均为 1。

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickMul(N):
            if N == 0:
                return 1.0
            y = quickMul(N // 2)
            return y * y if N % 2 == 0 else y * y * x
        
        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)