当前位置：首页 > article >正文

C语言————快速幂

article 2025/2/12 23:38:21

在 C 语言中，快速幂是一种用于高效计算幂运算（即 $a^{n}$ ，其中 a是底数base，n 是指数power）的算法。常规的幂运算方法是通过循环将底数a连乘n次，时间复杂度为O(n)。而快速幂算法利用了指数的二进制特性，将时间复杂度优化到了O(log n)，在处理大指数时能显著提高计算效率。

原理

快速幂算法的核心思想是将指数n 表示为二进制形式，然后根据二进制位的特点来减少乘法运算的次数。例如，计算 $a^{13}$ ，因为13 的二进制表示是 $1101_2$ ，即 $13 = 2^3 + 2^2 + 2^0$ ，那么 $a^{13} = a^{2^3 + 2^2 + 2^0} = a^{2^3} \times a^{2^2} \times a^{2^0}$

我们可以通过迭代的方式，从 $a^1$ 开始，不断将指数翻倍（即 $(a^2, a^4, a^8, \cdots$ ，并根据指数 n 的二进制位决定是否将当前的幂乘入结果中。

比如 $a^9=a^4*a^4*a^1=a^2*a^2*a^2*a^2*a^1=a^1*a^1*a^1*a^1*a^1*a^1*a^1*a^1*a^1$

翻倍其实就是平方， $a^1$ 翻倍就是 $a^2$ = $a^1$ * $a^1$ ，所以显然如果幂是奇数会多出来一个 $a^1$ ，就需要特殊处理一下。

这里的二进制技巧是如果一个数是奇数，例如13 的二进制表示是 $1101_2$ ，二进制第一位（ $2^0$ ）权值上一定是1，因为其他二进制位上的数都代表2的幂，位运算也可以进行除2操作。

我们举的例子比较简单，实际上在计算中会多次多出 $a^1$ 这类情况（以后出现的都是翻倍后的），把多出来的单独乘到结果中即可。

代码实现：

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;//除以2
        base = (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;//除以2
        base = (base * base) % 1000;//返回的是result，这里可以加个1的判断跳出，没差
    }
    return result;
}