朴素算法

在要求算出一个数字的n次幂时，最容易想到的便是朴素的循环累乘：

int normalPower(int base, int exponent) {
    while (exponent > 0) {
        base *= base;
        --exponent;
    }
    return base;
}

很明显，这种方法的时间复杂度为O(N);

快速幂算法

根据二进制的性质以及编程语言中方便的与运算符&和移位运算符>>，有人提出了快速幂的算法，其时间复杂度为O(logN)。对这两个操作符不明白的同学可以先看文末的简述。
1.快速幂思想
例如计算a^b这样一个数，我们指数b以转换二进制的形式进行分解，将其写成二进制中每一位乘上该位的权重(从右往左，第i位的权为2^i-1)。
例如：a¹³ = a^{2^0+2^2+2^3} = a^{2^0}a^{2^2}a^{2^3}
2.快速幂实现
在这里我们先给出快速幂实现的代码，方便后续进行对照讲解

int fastPower(int base, int exponent) {
    int sum = 1;
    while (exponent != 0) {
        if ((exponent & 1) != 0) {
            sum *= base;
        }
        exponent = expnonent >> 1;  // 对指数进行移位
        base *= base;               // 让base的次幂以2的倍数增长
    }
    return sum;
}

需要额外注意的是，&操作符的运算符低于>之类的比较运算符，也低于==和!=运算符。
3.快速幂讲解
首先可以看到，循环的终止条件为指数e为0，且每次循环e都会右移一位，而自然数N的二进制长度为log₂N，因此这个循环至多遍历log₂N次。即它的时间复杂度为O(logN)。
我们在每次指数右移的同时，让底数base=base*base。这样一来，第一次循环结束后base的大小变为原来的2=2¹次方倍，第二次后变为原来的2¹*2¹=2²次方倍...最终，我们在第n次循环中sum所乘的base总是base^{2^(n-1)}。保证了算法的正确性。而每次base^{2^(n-1)}，总能在下一次的循环中利用到base^{2^n}的计算中，减少了程序的时间消耗与空间消耗。
假设我们输入了fastPower(bbasese, 13)这样一个函数，那么按照上面的定义，13应该是被理解为二进制串1101，在每次开始都进行和1相与，为1时才进行sum和bbasese的相乘，联系上一段话，我们不难推断出我们能够按照base¹³ = base^{2^0+2^2+2^3} = base^{2^0}base^{2^2}base^{2^3}的顺序计算。

快速幂预备知识
1.二进制
相信大家都知道二进制的原理，这里我们主要用到十进制与二进制相互转换的原理。
举个例子，6的二进制是110，那么6便可以标示成2²+2¹。
2.与运算符&
这是一个二元运算符，返回左右两数以二进制形式相与后的结果。例如x & 1 == 1则表示x为奇数，x & 1 == 0则为偶数。
3.移位运算符>>
顾名思义，这是令一个数的二进制形式移位的操作符。该操作符指向右边，因此是右移，例如1011>>1 = 101。相似的，还有左移用的操作符<<，不过这里用不上。