要注意正负号。

快速幂算法。
算法学习笔记(4)：快速幂 – 知乎

递归快速幂：计算a的n次方，如果n是偶数（不为0），那么就先计算a的n/2次方，然后平方；如果n是奇数，那么就先计算a的n-1次方，再乘上a；递归出口是a的0次方为1。这个算法的时间复杂度是O(logn)的。

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;
    }
}

另：大素数取模问题，对某个超大的数取模，有以下数学原理：

• 模运算的性质：(a⋅b) % m=[(a % m)⋅(b % m)] % m
• 这意味着可以在每一步乘法后取模，避免数值溢出，同时保持结果的正确性。

快速幂取模：

//递归快速幂（对大素数取模）
// 对a的n次方取mod
#define MOD 1000000007
typedef long long ll;
ll qpow(ll a, ll n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a % MOD;
    else
    {
        ll temp = qpow(a, n / 2) % MOD;
        return temp * temp % MOD;
    }
}

非递归快速幂：

非递归快速幂（迭代法）通过 二进制分解指数 来高效计算 a^n。它的核心原理是：

• 将指数 n 表示为二进制形式，逐位检查是否为 1。
• 如果某一位是 1，就将当前的 a 的幂乘到结果中。
• 每一步 a 都会平方，对应二进制位的权重。

每一次循环，a都会平方，但是只有移位的那一位是1的时候，才能算入最终结果中。

class Solution {
  public:
    double Power(double base, int exponent) {
        if(exponent == 0) return 1.0;
        if(base == 0) return 0;
        int flag = 0;
        if(exponent < 0){
            exponent = -exponent;
            base = 1 / base;
        }
        double answer = 1;
        while(exponent > 0){
            if((exponent & 1) == 1){ // 说明这一位是1 最后的结果需要乘入
                answer = answer * base;
            }
            base = base * base;
            exponent = exponent >> 1;
        }
        return answer;
    }
};