【算法教程】【C/C++】基础数学：快速幂——程序设计思路与代码实现

前言

        通常情况下，我们在使用程序进行幂运算时，会利用循环乘法或pow( , )解决。但对于数据非常大的情况，这样做非常影响效率，很容易导致超时。因此，快速幂应运而生。

程序设计思路

        快速幂基于二进制进行。通常情况下，我们会将其封装为一个函数binpow( , )。下面举个例子说明其原理：

        我们要计算3¹³，常规做法是：用for循环使一个变量从1开始每次乘3，这里数据小，没有问题，但如果是3^100000000呢（不考虑数据溢出）？这样算肯定不对。

        快速幂就很好的解决了这个问题，我们可以将3¹³分解为：

3¹³ = 3⁸ * 3⁴ * 3¹

        这样一来，我们只需要计算3²ⁿ即可，即每次进行平方运算。节省了大量时间。

代码实现

int quick(int a,int b){//计算a^b
    int res = 1;//从1乘起
    while(b>0){
        if(b&1) res=res*a;//当a（二进制）的这一位是1时，乘a
        a=a*a;//计算a^2
        b>>=1;//答案的一位（二进制）解决
    }
    return res;
}

结语

        快速幂在很大程度上提升了效率，使得程序速度更快。我是faryou，再见！