快速幂cpp代码

基础问题：求数字 $a$ 的 $n$ 次方。
最基本的想法，就是一次一次相乘，时间复杂度为 $O(n)$。
代码如下：

using ll = long long;
ll pow(ll a, ll n)
{
    ll ret = 1;
    for (ll i = 0; i < n; i++) {
        ret *= a;
    }
    return ret;
}

稍微思考一下便可得知，计算一个数的$n$次方并不需要相乘 $n$ 次。我们如果知道 $a$ 的 $n/2$ 次方，便可以用两个 $a^{n/2}$ 相乘，获得 $a^n$。顺着这个思想往下想，可以考虑把 $n$ 拆成二进制的形式，这样只要把对应的二进制位数得到的幂相乘起来就可以得出答案了。举例：当 $n$ 为 7 时，我们要 $6^7$。$7$ 按照二进制可以拆成 $00000111$。那我们只要知道 $6^1$，$6^2$ 和 $6^4$，再把他们相乘就可以了。
代码如下：

ll qpow(ll a, ll n)
{
    if (n == 0) {
        return 1;
    } else if (n % 2 == 1) {
        return qpow(a, n - 1) * a;
    } else {
        ll ret = qpow(a, n / 2);
        return ret * ret;
    }
}

ll qpow2(ll a, ll n)
{
    ll ret = 1;
    while (n) {
        if (n & 1) {
            ret *= a;
        }
        a *= a;
        n >>= 1;
    }
    return ret;
}

一为递归的方式，二为迭代的方式。考虑到调用栈切换，方式二会快一些。这种把幂拆成二进制的方法，就被称为快速幂。
完整代码如下：

#include <iostream>
#include <time.h>
using namespace std;
using ll = long long;
ll pow(ll a, ll n)
{
    ll ret = 1;
    for (ll i = 0; i < n; i++) {
        ret *= a;
    }
    return ret;
}

ll qpow(ll a, ll n)
{
    if (n == 0) {
        return 1;
    } else if (n % 2 == 1) {
        return qpow(a, n - 1) * a;
    } else {
        ll ret = qpow(a, n / 2);
        return ret * ret;
    }
}

ll qpow2(ll a, ll n)
{
    ll ret = 1;
    while (n) {
        if (n & 1) {
            ret *= a;
        }
        a *= a;
        n >>= 1;
    }
    return ret;
}
int main()
{
    ll a = 7, n = 16;
    clock_t startTime, endTime;
    startTime = clock(); // cpu clock time
    cout << pow(a, n) << endl;
    endTime = clock();
    cout << (endTime - startTime) << endl;

    startTime = clock(); // cpu clock time
    cout << qpow(a, n) << endl;
    endTime = clock();
    cout << (endTime - startTime) << endl;

    startTime = clock(); // cpu clock time
    cout << qpow2(a, n) << endl;
    endTime = clock();
    cout << (endTime - startTime) << endl;
}

可以看到后面两种cpu周期普遍低于前一种。