快速幂【c++】

幂是指乘方运算的结果。
在编写程序来实现乘方运算时，例如要求，很容易想到将b个a依次相乘。这样做需要n-1次乘法运算，这就是朴素版本的求幂算法。

朴素版本

// 朴素算法
int exponentiation(int a, int b) {
    int res = 1;
    for (; b > 0; b--) 
        res *= a;
    return res;
}

递归版本

设，且k是大于1的整数。显然运用朴素版本的算法来计算需要次乘法。但若想到的话，若计算用了次乘法的话，那计算需要的乘法次数. 当然，如果将这个策略再次运用到的计算上，那么乘法次数又可以减少了。
再比如，，只需要四次乘法就能完成运算。
减少乘法次数的要诀在于，重复利用低幂次的值来计算高次幂。基于这种思想，很容易设计出基于递归的求幂算法。

// 递归算法
int fastExponetiation1(int a, int b) {
    if (b == 0) return 1;
    if (b == 1) return a;
    int a2 = fastExponetiation1(a, b / 2);
    return a2 * a2 * fastExponetiation1(a, b % 2);
}

简单来说，每次递归，指数减半（并向下取整）。指数为0或1时，不再往下递归。显然，此算法的时间复杂度为，相比之下，朴素算法的时间复杂度为. 新算法优秀多了。

这还没完。实际上，该递归算法还存在非递归形式。

非递归版本

再看的例子。. 细心的读者已经发现，式子中依次出现了1、0、1、0四个数，而1010正是10的二进制表示。
令n = 0, 1, 2, 3···，依次遍历b的二进制表示的第n位，根据该位是0还是1来判断是否将纳入连乘之中，最终就能得到的值。同样的，还是利用低幂次的值来计算高幂次的值。代码如下：

// 非递归算法
int fastExponetiation2(int a, int b) {
    int res = 1;
    for (; b; res = (b & 1 ? res * a : res), a = a * a, b = b >> 1);
    return res;
}

在第i轮循环（i = 1, 2, 3······）中，变量a的值为（a的初始值）的次幂。
注意代码b = b >> 1等同于b = b / 2，而代码b & 1等同于b % 2. 这就和前面的递归版本的代码联系起来。

总结

递归版本和非递归版本的算法，本质上都是一样的，都是基于指数的拆分，即。递归版本应该更好理解。然而，众所周知，函数的递归深度是有限的，而且递归操作还会产生其它额外的开销。将递归的算法展开为非递归的形式，有助于提高程序的性能。因此，非递归版本的算法在效率上更胜一筹。