fastpower

算法
loading...

快速幂算法

快速幂算法是一种高效的算法，用于计算 ( a^b ) 的值，特别是当 ( b ) 非常大时。这个算法的基本思想是将指数 ( b ) 分解为2的幂次的和，然后通过连续平方来减少乘法的次数。

1
2
3
4
5
6
7
8
9
10
11
long long quickPow(long long a, long long b) {
    long long res = 1; // 结果初始化为1
    while (b > 0) { // 当 b 大于0时循环
        if (b & 1) { // 如果 b 的当前最低位为1，则将当前的 a 加入结果中
            res = res * a;
        }
        a = a * a; // a 自乘，即 a 的平方
        b >>= 1; // b 右移一位，即除以2
    }
    return res; // 返回结果
}

在这段代码中，我们使用了位运算来检查 ( b ) 的每一位是否为1（即 if (b & 1)）。如果为1，我们就将 ( a ) 的当前幂次乘到结果 res 中。每次循环，我们都将 ( a ) 自乘（即平方），并将 ( b ) 右移一位（即除以2）。