声明：若无特殊说明，本文的 $a^b$ 表示 $a$ 的 $b$ 次方

幂函数的朴素实现

如果我们想要实现幂函数 pow(x,n) 最自然的想法就是设置一个循环，记录 x 累乘 n 次的结果。这种思路的代码实现过于简单，所以不予展示。

但是这样，我们的时间复杂度是 O(n)，n 比较大的时候，我们也需要承担比较大的代价。

有没有更快的算法呢？

乘法快速幂

我们可以这样计算 $3^7$，因为 $3^7=3^4 \times 3^3$，$3^3=3^2 \times 3^1$，$3^2=3^1 \times 3^1$。

所以 $3^7=3^4 \times 3^2 \times 3^1$。

我们每次都只需要折半计算幂，然后通过幂运算的性质来得到结果，比如 $3^7=3^4 \times 3^3$，就不需要经过计算 $3^6$ 的环节。

每次都折半进行计算，这不就是对 $y$ 进行二进制分解的过程吗？

简单地说，$(7)_{10}=(1011)_2$，也就是说，$7=2^2+2^1+2^0$。

根据幂运算的性质就可以得到：

$$x^7=x^{(2^2+2^1+2^0)}=x^{(2^2)} \times x^{(2^1)} \times x^{(2^0)}$$

所以我们只需要计算 $x^1$、$x^2$、$x^4$。

这很简单，$x$ 的初始值就是 $x^1$。

要想实现 $x^2$，我们让 $x$ 再乘上自身即可，$x^4$ 同理。

这样，我们的代码实现就比较简单了。

我们先对 $y$ 进行二进制分解，分解完，我们只看有 1 的部分。

还是拿 7 举例子，二进制下的 7 是 $1011$。

• 看第 0 位，是 1，所以答案需要乘上 $x^{(2^0)}$
• 看第 1 位，是 1，所以答案需要乘上 $x^{(2^1)}$
• 看第 2 位，是 0，所以答案不需要更改
• 看第 3 位，是 1，所以答案需要乘上 $x^{(2^3)}$

下面是代码实现，C++ 由于没有使用到其常用特性，所以参考 C 语言版本。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
// 这里用int只是为了演示算法，具体数据类型依据具体数据量 
int myPower(int x, int y){
    int ret = 1;
    while(y != 0){
        if((y & 1) != 0){
            ret *= x;
        }
        x *= x;
        y >>= 1;
    }
    return ret;
}
int main(){
    srand(time(NULL));
    for(int x = 1; x <= 10; ++x){
        int y = rand() % 6 + 2;
        printf("%d的%d次方是%d,标准库函数核对结果:%d\n", 
                x, y, myPower(x, y), (int)pow(x, y));
    }
    return 0;
}

import random
import math

def myPower(x, y):
    ret = 1
    while y != 0:
        if (y & 1) != 0:
            ret *= x
        x *= x
        y >>= 1
    return ret

for x in range(1, 11):
    y = random.randint(2, 7)
    print(f"{x}的{y}次方是{myPower(x, y)},标准库函数核对结果:{int(math.pow(x, y))}")