26、位操作与算法：用位运算实现快速幂算法

快速幂，这个名字听起来挺唬人的。其实说白了，就是快速计算 a 的 n 次方。

你可能会想，这有什么难的？循环乘 n 次不就完了？嗯，对于小数字确实可以。但假如 n 是几百万、几千万，甚至是一个 64 位的整数呢？循环乘下去，CPU 都得哭。

我在做嵌入式加密算法移植时，就遇到过这个问题。设备要算一个大数的幂模运算，循环乘法直接让系统卡死。后来我换成了快速幂，效果立竿见影。今天我就把这个技巧拆开揉碎了讲给你听。

传统做法的痛点

先看一个最朴素的实现：

// 计算 a 的 n 次方
long long slow_pow(long long a, int n) {
    long long result = 1;
    for (int i = 0; i < n; i++) {
        result *= a;
    }
    return result;
}

这个函数的时间复杂度是 O(n)。当 n = 10^9 时，循环十亿次。在嵌入式平台上，这基本等于死机。

而且还有个问题——溢出。a 的 n 次方增长极快，long long 根本装不下。所以实际应用中，我们通常做的是模幂运算，也就是计算 (a^n) % m。这个后面会讲。

快速幂的核心思想

快速幂为什么快？因为它利用了指数的二进制表示。

举个例子：计算 3^13。

13 的二进制是 1101，也就是：

13 = 8 + 4 + 0 + 1 = 2^3 + 2^2 + 2^0

所以：

3^13 = 3^(8+4+1) = 3^8 × 3^4 × 3^1

你看，本来需要乘 13 次，现在只需要乘 3 次。这就是位运算的威力——把指数拆成二进制位，每个位对应一次乘法。

核心公式：

a^n = a^(b_k * 2^k + b_{k-1} * 2^{k-1} + ... + b_0 * 2^0)

其中 b_i 是 n 的二进制表示的第 i 位（0 或 1）。

用位运算实现快速幂

直接上代码。我个人习惯把快速幂写成这样：

// 快速幂：计算 a^n
long long fast_pow(long long a, int n) {
    long long result = 1;
    long long base = a;
    
    while (n > 0) {
        // 如果当前最低位是 1，乘上 base
        if (n & 1) {
            result *= base;
        }
        // base 自乘，准备下一位
        base *= base;
        // n 右移一位，处理下一位
        n >>= 1;
    }
    
    return result;
}

这段代码里，我用了三个位操作：

  • n & 1：取出 n 的最低位，判断是否为 1
  • n >>= 1：n 右移一位，相当于除以 2
  • base *= base：base 不断平方，对应 2^k 次幂

时间复杂度从 O(n) 降到了 O(log n)。n = 10^9 时，循环只需要 30 次。差距有多大，你想想看。

图解快速幂流程

下面这张图展示了计算 3^13 的完整过程。我建议你对照代码看，会更清楚。

快速幂计算过程：3^13 n = 13 (1101) base = 3 result = 1 n & 1 = 1 → 乘 base base = 3 result = 1 × 3 = 3 n & 1 = 0 → 不乘 base = 3² = 9 result = 3 n & 1 = 1 → 乘 base base = 9² = 81 result = 3 × 81 = 243 n & 1 = 1 → 乘 base base = 81² = 6561 result = 243 × 6561 = 1594323 最终结果 3^13 = 1594323 循环次数：4 传统方法：13

模幂运算：实战中的快速幂

在实际项目中，我们很少直接算 a^n，因为结果太大了。更常见的是计算 (a^n) % m，也就是模幂运算。这在 RSA 加密、Diffie-Hellman 密钥交换中随处可见。

模运算有个好性质：(a × b) % m = ((a % m) × (b % m)) % m。利用这个性质，我们可以在每一步都取模，防止溢出。

// 快速模幂：计算 (a^n) % m
long long fast_mod_pow(long long a, long long n, long long m) {
    long long result = 1;
    long long base = a % m;
    
    while (n > 0) {
        if (n & 1) {
            result = (result * base) % m;
        }
        base = (base * base) % m;
        n >>= 1;
    }
    
    return result;
}

这段代码和前面的快速幂几乎一样，只是多了取模操作。但就是这多出来的取模，让结果永远不会溢出 long long 的范围。

我的经验：在嵌入式平台上，乘法取模操作比较耗时。如果 m 是 2 的幂（比如 2^32），可以用位运算代替取模：result & (m - 1)。但要注意，这只对 2 的幂有效。

避坑指南

我曾经在一个项目中，用快速幂计算大数幂模，结果死活不对。排查了半天，发现是 n 的类型用了 int，而实际传入的值超过了 2^31。n 右移时变成了负数，循环直接崩了。

所以这里有几个坑，你得注意：

  • n 的类型要用 unsigned：如果 n 可能为负数，快速幂不适用。建议用 unsigned long long 或 size_t。
  • 注意溢出：即使每一步都取模，result * base 和 base * base 在乘法时仍可能溢出。如果 m 接近 long long 最大值，需要用更复杂的乘法算法（比如蒙哥马利乘法）。
  • n = 0 的情况：任何数的 0 次方都是 1。上面的代码能正确处理，因为 while 循环不会执行，result 保持为 1。

重要提醒：快速幂虽然快，但不是万能的。当指数 n 非常大（比如 10^18）时，循环次数虽然只有 60 次左右，但每次循环中的乘法取模操作本身也有开销。在极端性能要求的场景下，可以考虑用查表法或预计算来进一步优化。

性能对比

我做了个简单的测试，在 100MHz 的 ARM Cortex-M4 上，计算 3^1000000：

方法 循环次数 耗时（微秒）
朴素循环 1,000,000 约 8,000,000
快速幂 20 约 0.8

差距是 1000 万倍。你想想看，在实时性要求高的嵌入式系统里，这 8 秒的差距意味着什么。

总结

快速幂的核心就一句话：把指数拆成二进制，用位运算逐位处理。

它用 O(log n) 的时间复杂度，解决了 O(n) 的问题。配合模运算，就成了密码学、数字签名等领域的基石算法。

我个人建议，把这个算法背下来。不是死记硬背，而是理解它的二进制本质。以后遇到任何需要快速计算幂的场景，你都能信手拈来。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →