快速幂算法（二进制分解） - 编程数学

快速幂算法：用“翻倍法”让大数幂计算快到飞起

同学们，你们有没有遇到过这样的问题：老师让你计算 2 的 100 次方，你亮出计算器，结果它显示“溢出”或者直接罢工。自己手算？2×2=4，再×2=8……一直乘100次，不仅手酸，还容易算错。有没有一种方法，能让我们用很少的乘法次数就得到答案？当然有！这就是我们今天要学的 快速幂算法（也叫“二进制快速幂”或“平方倍增法”）。

快速幂专门用来计算 a 的 n 次方（a^n），它的神奇之处在于：原本需要 n 次乘法，现在只用大约 log₂(n) 次乘法。比如 n=100，原本要乘100次，快速幂只需要7次循环（每次循环里做一次乘法和一次平方），总共14次乘法。当 n 很大时，这个差别就像骑自行车和坐火箭一样明显。计算机科学、密码学、图形学里到处都有它的身影。

? 生活中的类比：用“翻倍”策略买巧克力

假设你想买20块巧克力，但商店的规则很古怪：你每次只能买“你目前拥有的巧克力数量”那么多块。一开始你手里有0块，所以第一次你只能买1块。现在你有1块了，第二次你可以买1块（总共2块）。第三次你已经有2块了，所以可以买2块（总共4块）。第四次买4块（总共8块），第五次买8块（总共16块），第六次买16块（总共32块）——够了！只用了6次就买到了超过20块。如果你想正好买到20块，可以在这个过程里“选择性”购买：比如第一次买1块（有1），第二次买1块（有2），第三次不买（保留2），第四次买2块（有4），第五次不买（保留4），第六次买4块（有8），第七次不买（保留8），第八次买8块（有16），第九次买4块——啊，不，这样太麻烦了。其实用二进制选择会更简单，快速幂就是这个思路：把指数拆成二进制，然后通过“翻倍”得到所有需要的幂次，最后把选中的乘起来。

? 数学原理：二进制分解

快速幂的核心思想是：任何一个正整数 n 都可以表示为若干个2的整数次幂之和（就是二进制展开）。比如：

13 的二进制是 1101，也就是 13 = 8 + 4 + 1 = 2³ + 2² + 2⁰。
那么 a¹³ = a⁸⁺⁴⁺¹ = a⁸ × a⁴ × a¹。

我们只需要依次计算出 a¹, a², a⁴, a⁸, a¹⁶ … 这些“2 的幂次”的值，然后根据指数 n 的二进制位，把对应的那些乘起来就行了。怎么快速得到这些值呢？很简单：每个下一个值就是上一个值的平方：

a¹ 就是 a
a² = a¹ × a¹
a⁴ = a² × a²
a⁸ = a⁴ × a⁴
……

这样只需要 log₂(n) 次平方运算就能得到所有需要的幂次。然后遍历 n 的二进制位，如果当前位是 1，就把对应的幂次乘到结果里。

⚙️ 算法步骤（一步一步来）

我们以计算 2¹³ 为例，手动走一遍算法：

初始化：结果 res = 1，底数 base = 2，指数 n = 13（二进制 1101）。
循环（当 n > 0）：
- 检查 n 的最低位（n & 1）：最低位是1 → 把当前 base 乘到 res 里。此时 base = 2，所以 res = 1 × 2 = 2。
- 然后 base 平方：base = 2 × 2 = 4。
- n 右移一位：n = 13 >> 1 = 6（二进制 110）。
第二次循环（n=6，二进制110）：
- 最低位是0 → 不乘。
- base 平方：base = 4 × 4 = 16。
- n 右移：n = 6 >> 1 = 3（二进制 11）。
第三次循环（n=3，二进制11）：
- 最低位是1 → res = 2 × 16 = 32。
- base 平方：base = 16 × 16 = 256。
- n 右移：n = 3 >> 1 = 1（二进制 1）。
第四次循环（n=1，二进制1）：
- 最低位是1 → res = 32 × 256 = 8192。
- base 平方：base = 256 × 256 = 65536（其实用不到了）。
- n 右移：n = 1 >> 1 = 0，循环结束。
返回 res = 8192。验证：2¹³ = 8192，正确！

注意：我们只用了4次循环（13的二进制位数是4），而普通连乘需要13次。如果指数是100，二进制是1100100（7位），循环7次就够了。

? 新手容易犯的错误

忘记处理 n = 0 的情况：任何数的 0 次方等于 1。算法里 while (n > 0) 会直接跳过，返回初始的 res = 1，正确。但如果你把 res 初始化为 0 就错了。
用 int 导致溢出：2¹³ 是8192，没问题，但 2¹⁰⁰ 已经是个巨大的数。C++ 里建议用 long long，甚至用 unsigned long long 或高精度。Python 没有这个问题（任意精度）。如果你需要结果对某个数取模（避免溢出），可以用快速幂取模（下面会提到）。
死循环：如果忘记 n >>= 1，循环会无限进行下去。还有，如果 n 是负数（比如 -1），while(n > 0) 不会执行，但如果你想处理负数指数，就得先取倒数再算，不过一般我们只教非负指数。
位运算优先级：在 C++ 中，n & 1 的优先级低于 ==，所以写 if (n & 1 == 1) 会先计算 1 == 1 得到 1，再 n & 1，结果不对。正确写法是 if (n & 1) 或加括号 if ((n & 1) == 1)。

? 完整可运行代码示例（含模运算）

很多场景下我们只需要结果模一个大数（比如在竞赛或密码学中，结果可能太大），这时可以一边乘一边取模。下面给出带取模的版本，以及一个纯粹求幂的版本。代码中变量名简短并带有中文注释。

C++ 版本（带取模）

#include <iostream>
using namespace std;

// 快速幂取模：计算 (a^n) % mod
long long fastPowMod(long long a, long long n, long long mod) {
    long long res = 1;            // 结果，初始为1（任何数的0次方=1）
    long long base = a % mod;     // 底数先模一次，防止后续乘法溢出
    while (n > 0) {
        if (n & 1LL) {           // 判断 n 的当前最低位是否为1
            res = (res * base) % mod;   // 乘上当前 base 并取模
        }
        base = (base * base) % mod;     // base 平方后取模
        n >>= 1;                // n 右移一位，相当于去掉最低位
    }
    return res;
}

int main() {
    long long a = 2, n = 13, mod = 1000000007;
    long long ans = fastPowMod(a, n, mod);
    cout << a << "^" << n << " mod " << mod << " = " << ans << endl;
    // 正常 2^13 = 8192，mod 后就是 8192
    // 如果 n 很大，比如 2^100 mod 1000000007，也能快速算出
    return 0;
}

Python 版本（带取模）

def fast_pow_mod(a: int, n: int, mod: int) -> int:
    """
    快速幂取模：计算 (a^n) % mod
    :param a: 底数
    :param n: 指数（非负）
    :param mod: 模数
    :return: 结果
    """
    res = 1                     # 结果初始化为1
    base = a % mod              # 底数先取模
    while n > 0:
        if n & 1:               # 如果当前最低位是1
            res = (res * base) % mod
        base = (base * base) % mod  # 底数平方并取模
        n >>= 1                 # 右移一位
    return res

# 测试
if __name__ == "__main__":
    a, n, mod = 2, 13, 1000000007
    ans = fast_pow_mod(a, n, mod)
    print(f"{a}^{n} mod {mod} = {ans}")

你可能会想：为什么非要取模？因为计算机里整数有上限，一旦超出就会溢出（比如 long long 最大约 9.22×10¹⁸，而 2¹⁰⁰ ≈ 1.27×10³⁰，远大于这个数）。取模之后结果始终在 0 到 mod-1 之间，安全又好用。

? 练习一下

用手算或代码计算 3¹⁰（用快速幂方法），验证结果是否为 59049。
不用快速幂，写一个普通循环乘法版本，比较当 n = 1000000 时的运行时间（提示：普通循环会慢到让你怀疑人生，建议别真跑那么大，用 1000 或 10000 试试）。
挑战：计算 2⁵⁰⁰ 的最后三位数字（提示：用快速幂取模，mod=1000）。

? 延伸学习：矩阵快速幂

快速幂不仅能用在数字上，还能用在矩阵上！比如我们要计算一个矩阵 A 的 n 次方，可以用完全一样的思路：把“乘法”换成“矩阵乘法”，“平方”换成“矩阵的平方”，结果初始化为单位矩阵。矩阵快速幂在计算斐波那契数列的第 n 项、求解线性递推等问题中超级有用。我们会在后续的“矩阵快速幂”知识点中详细学习。

另外，快速幂也是 RSA 加密算法 的基石之一，RSA 里需要计算超大整数的幂并取模，没有快速幂的话几乎不可能实现。

? 总结

快速幂通过二进制分解指数，利用底数平方，把时间复杂度从 O(n) 降到 O(log n)。
核心代码就是 while(n){ if(n&1) res*=base; base*=base; n>>=1; }。
记得处理好 n=0 和溢出，需要时加上取模运算。
这个思想在很多领域通用，从解数学题到写游戏、搞加密都用得上。

学好快速幂，你就在编程路上多了一把锋利的“小刀”——哪怕遇到再大的指数，也能轻松切割！

例题精讲