在 C 语言中，快速幂是一种用于高效计算幂运算（即 ，其中 a是底数base，n 是指数power）的算法。常规的幂运算方法是通过循环将底数a连乘n次，时间复杂度为O(n)。而快速幂算法利用了指数的二进制特性，将时间复杂度优化到了O(log n)，在处理大指数时能显著提高计算效率。
原理
快速幂算法的核心思想是将指数n 表示为二进制形式，然后根据二进制位的特点来减少乘法运算的次数。例如，计算 ，因为13 的二进制表示是
，即
，那么
我们可以通过迭代的方式，从 开始，不断将指数翻倍（即
，并根据指数 n 的二进制位决定是否将当前的幂乘入结果中。
比如
翻倍其实就是平方，翻倍就是
=
*
，所以显然如果幂是奇数会多出来一个
，就需要特殊处理一下。
这里的二进制技巧是如果一个数是奇数，例如13 的二进制表示是，二进制第一位（
）权值上一定是1，因为其他二进制位上的数都代表2的幂，位运算也可以进行除2操作。
我们举的例子比较简单，实际上在计算中会多次多出这类情况（以后出现的都是翻倍后的），把多出来的单独乘到结果中即可。
代码实现：
long long fastPower(long long base, long long power) {long long result = 1;while (power > 0) {if (power % 2 == 1) {//奇数拆出result = result * base % 1000;}power = power / 2;//除以2base = (base * base) % 1000;//返回的是result，这里可以加个1的判断跳出，没差}return result;
}这个幂运算数值通常比较大，大多数快速幂都是为了获得结果的低位，所有取模运算，%1000就是保留3位。
包含位运算的代码
long long fastPower(long long base, long long power) {long long result = 1;while (power > 0) {if (power&1) {//奇数拆出result = result * base % 1000;}power>>=1;//除以2base = (base * base) % 1000;//返回的是result，这里可以加个1的判断跳出，没差}return result;
}
复杂度分析
- 时间复杂度：O(log n)，因为每次循环指数 n 都会减半。
- 空间复杂度：O(1)，只使用了常数级的额外空间。