快速幂是一种高效的计算幂的方法,其基本思想是将幂的指数表示为二进制形式,
然后利用二进制数的每一位来确定是否需要进行平方和乘法操作。这种方法比直接
进行连乘要高效得多,特别是在处理大指数时。
快速幂的算法步骤如下:
1. 将指数 n 转换为二进制形式。
2. 初始化结果为 1,底数为 base。
3. 从右往左扫描指数的每一位:
o 如果当前位为 1,则将结果乘以底数的当前值。
o 底数进行平方操作。
o 移动到下一位。
下面是一个使用 C 语言实现的快速幂算法示例:
c 复制代码
#include <stdio.h>
// 快速幂函数
long long fast_power(long long base, int n) {
long long result = 1;
while (n > 0) {
// 如果 n 的当前位是 1,则将结果乘以 base 的当前值
if (n & 1) {
result *= base;
}
// base 进行平方操作
base *= base;
// n 右移一位,相当于除以 2
n >>= 1;
}
return result;
}
int main() {
long long base = 2;
int n = 10;
printf("The result of %lld^%d is: %lld\n", base, n, fast_power(base,
n));
return 0;
}