快速幂

快速幂

这是一般求幂的算法：(a^n=a_1*a_2*...*a_n)。
我们可以发现，这个算法很慢的原因是有很多步骤重复了，例如(3^3=3*3*3)，那么我们为什么不可以让(3^3=9*3)呢，快速幂就是基于这个原理。

递归快速幂

下面我们拿6来举例：
(a^6=a^3*a^3)
(a^3=a*a^2)
(a^2=a^1*a^1)
(a^1=a*a^1)

int qpow(int a, int n) {
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a;
    else {
        int temp = qpow(a, n / 2);
        return temp * temp; // 很重要不能省略
    }
}

非递归快速幂

因为递归的方法非常占用空间，可能数字一大就爆栈了。
下面我们用非递归的方法来解决这个问题。
举个例子：
((6)_2=110=2^2+2^1=4+2)
那么(2^6=2^4*2^2)。
不难看出(a^n=a^{2^{k_{n-1}}}+a^{2^{k_{n-2}}}+...+a^{2^{k_1}})。

int qpow(int a, int n) {
    int ans = 1;
    while (n > 0) {
        if (n & 1) { // n % 2 == 1
            ans *= a;
        }
        a *= a;
        n >>= 1; // n /= 2
    }
    return ans;
}