)
★ FEATURED ARTICLE 如果有人让你实现一个pow(a, n)你的第一反应是什么我猜十有八九是写个循环n 次相乘就完事了。这个答案在 n 很小的时候没毛病可一旦 n 变成 10^9 甚至 10^18普通循环的乘法次数就会直接让程序卡到怀疑人生。这时候就需要快速幂上场了。快速幂的核心思路其实不复杂说穿了就是“把指数拆成二进制用位运算来走捷径”。而这里面的关键配角就是很多人看一眼就头疼的按位与运算。它和快速幂组合在一起能把指数从几亿次乘法压缩到几十次这种性能差距用“降维打击”来形容一点都不过分。这篇文章不打算讲什么高深理论我会用最直白的语言拆解快速幂的原理重点讲透运算在里面的作用再带上递归版、迭代版代码以及我在实际刷题和项目里踩过的各种坑。不管你是刚学算法的学生还是写业务代码想优化性能的开发者这篇都值得花几分钟读完。1. 为什么你觉得“乘 n 次”已经够用了朴素算法的问题1.1 朴素循环的真实成本先看最直观的做法long long pow_naive(long long a, long long n) { long long res 1; for (long long i 0; i n; i) { res * a; } return res; }这个代码逻辑没毛病但问题就出在“没毛病”这三个字上。假设 n 10^9那这个循环就要跑 10 亿次。你可能会说10 亿次乘法对现代 CPU 来说也就一两秒的事确实纯乘法很快但如果你要在一次请求里计算多个幂或者 n 是 10^18 这种天文数字循环就直接废掉了。更要命的是很多场景下我们不只是要a^n而是要a^n mod m。比如 RSA 加密、哈希计算、随机数生成这些底层算法全都依赖大指数的模幂运算。n 动辄是几百位的二进制数循环乘法想都不要想。1.2 从二进制角度看指数拆分快速幂的核心洞察其实来自一个很朴素的想法指数可以拆成二进制。举个具体例子计算a^13。13 的二进制是1101也就是13 8 4 1所以a^13 a^(8 4 1) a^8 * a^4 * a^1看见没原来需要连乘 13 次的事情现在只要算 a^1、a^2、a^4、a^8 这四个数然后挑出对应的三项乘起来就行。a^2 可以由 a^1 平方得到a^4 可以由 a^2 平方得到a^8 可以由 a^4 平方得到。整个过程只需要 3 次平方运算加 2 次乘法。那怎么知道要挑哪几项这就需要看 13 的二进制位哪一位是 1就乘上对应的那一项。比如1101从低位到高位是第 0 位、第 2 位、第 3 位是 1所以就乘 a^1、a^4、a^8。这里的核心思想就出来了我一边把指数不断右移一边把底数不断平方遇到指数二进制最低位是 1 的时候就把当前底数乘进结果里。2. 运算在快速幂中的角色不只是“按位与”那么简单2.1 按位与的基础知识回顾先别急着写代码我们得先把这个老朋友请出来。按位与的规则就一句两个二进制位都是 1结果才是 1否则就是 0。1 1 1 1 0 0 0 1 0 0 0 0这个规则本身枯燥无味但它有一个特别实用的推论x 1 的结果就是 x 二进制最低位的值。最低位是 1奇数x 1就等于 1最低位是 0偶数x 1就等于 0。所以n 1本质上是判断 n 当前的最低位是不是 1也就是判断 n 当前是奇数还是偶数。这跟n % 2的效果完全一样但位运算是直接对二进制位操作没有除法那种“重”操作。在 C 里写n 1比写n % 2快那么一点点更重要的是语义上更容易让人联想到“二进制分解”这回事。2.2 用 n 1 判断指数当前位在快速幂的迭代版里每一轮循环都要做一件事判断当前指数的二进制最低位是否为 1。写成代码就是if (n 1) { res res * a % mod; }这个if判断的就是“当前这一轮的二进制位要不要乘进结果里”。如果最低位是 1说明这一位对应的 a^(2^i) 是最终结果需要的因子那就乘上如果最低位是 0就跳过这个因子。这里有个常见的疑问为什么不直接用n % 2 1答案是用不仅是从语义上更贴近“二进制位判断”而且编译器一般会把n % 2优化成n 1但你自己写n 1能确保不被某些奇怪的优化选项干扰也更容易让别人看出“哦这是在处理二进制位”。2.3 右移搬运n 1 与位运算优先级判断完当前位下一步就是把指数向右移位把下一位“搬到”最低位的位置上。这就是右移运算符的活。n 1; // 相当于 n n / 2但更快更符合二进制思路n 1的意思是把 n 的二进制位全部向右移动一位最高位补 0对无符号数来说。比如n 1101 n 1 后变成 0110这样循环就能依次考察原指数的每一位第一次看第 0 位第二次看第 1 位第三次看第 2 位……这里我要提醒一个巨坑位运算的优先级非常低。在 C/C 里的优先级比低比!低所以在写if (n 1 1)这种代码时实际会被解析成if (n (1 1))也就是if (n 1)虽然结果碰巧一样但这种写法非常容易埋雷。最稳妥的做法是给位运算加括号if ((n 1) 1)或者在 C 里直接省略 1因为非零即为真。3. 两种实现方式递归版与迭代版3.1 递归版快速幂的写法与调用栈理解了原理实现就水到渠成了。先来一个递归版本思路最贴近数学定义long long quick_pow_recursive(long long a, long long n, long long mod) { if (n 0) return 1 % mod; long long half quick_pow_recursive(a, n / 2, mod); long long res half * half % mod; if (n 1) { res res * a % mod; } return res; }这个递归版本的逻辑是要求a^n先算a^(n/2)然后平方。如果 n 是奇数再额外乘一个 a。例如a^13先算a^6平方得a^12因为 13 是奇数再乘 a 就是a^13。递归版本的好处是思路清晰看一眼就知道数学原理。坏处也明显每次递归都要压栈深度是 O(log n)这个深度倒是不深几十层不会栈溢出但函数调用开销毕竟存在。在竞赛里我还是更推荐迭代版。3.2 迭代版快速幂的写法与状态维护迭代版是我最常用的版本也是网上各种模板里最常见的形式long long quick_pow(long long a, long long n, long long mod) { long long res 1; while (n 0) { if (n 1) { res res * a % mod; } a a * a % mod; n 1; } return res; }每轮循环里有两件事if (n 1)判断当前二进制位是否为 1是的话就把当前底数乘进结果。a a * a % mod让底数自平方对应指数位每前进一位。n 1让指数右移一位准备看下一个二进制位。模拟一下a^13的执行过程就清楚了循环次数n 的二进制n 1 判断操作a 的值111011res 乘 aa^221100不乘a^43111res 乘 a^4a^8411res 乘 a^8a^16后面不再用50循环结束--res 依次乘上了 a^1、a^4、a^8最终就是 a^13。整个过程只有 4 轮循环而朴素算法要 13 次乘法。n 越大差距越离谱。Python 版也很简单def quick_pow(a: int, n: int, mod: int) - int: res 1 while n: if n 1: res res * a % mod a a * a % mod n 1 return res注意 Python 的整数是无限精度的所以不用像 C 那样担心中途溢出但加上取模操作仍然是好习惯。3.3 取模运算为什么必须取模以及如何在乘法中“顺便”取模很多刚接触快速幂的人会有个疑问“我代码里不写% mod最后返回结果再取模行不行”答案是在 C 里不行会溢出。比如计算2^100结果是一个 31 位的十进制整数早就超过long long的范围了。如果不中途取模前面的乘法直接溢出后面的结果全都错。中途取模的原则是每次乘法后立刻取模。因为取模运算满足(a * b) mod m ((a mod m) * (b mod m)) mod m所以每步都取模最终结果和最后取模是一模一样的但中间数字始终不会超过 m^2 的量级。我通常在mod取 10^9 7 这类常见模数时res * a的最大值也就在 10^18 量级刚好在long long的边界内但如果模数再大一点就需要考虑使用__int128或者让乘法拆开来做。提示在 C 里res * a % mod的写法很好用但要注意乘法发生溢出的情况。如果 mod 接近 10^18res * a会超过 64 位这时候要么用__int128要么用“快速乘”技巧也就是把乘法转换成加法累加再用快速幂的思路处理。4. 常见问题与排坑实录这些坑我全都踩过4.1 n0、n负数、底数为0时的处理先说 n 0。任何数的 0 次方都是 1这个好办代码里初始化res 1就覆盖了这个情况。但有一个特殊情况很多人没想过0^0。数学上这是个未定义的东西竞赛题一般不会考如果题目里真的出现了你需要看题目的约定。我处理的办法是如果底数和指数都为 0返回题目指定的值通常是 1但也可能直接报错这个看题目要求。再说负指数。快速幂这个思路本身是处理正整数的n 为负数时a^n 1 / a^(-n)也就是说要先对底数取倒数再用快速幂算正的指数部分。但在整数取模的场景下负指数要借助“模逆元”来处理。比如要算a^(-n) mod p在 p 是素数的情况下根据费马小定理a^(p-1) ≡ 1 (mod p)所以 a^(-n) ≡ a^(p-1-n) (mod p)也就是把负指数转化为 p-1-n 这个正指数再用快速幂算就行。这个点在实现时很容易漏掉。我自己最开始写模板时只处理了正指数结果在 RSA 相关的练习里遇到了负指数场景折腾了半天才醒悟过来。4.2 结果溢出与取模时机溢出这个问题我提过一嘴但值得展开细说。在 C 里即使你每次乘法后都取模如果模数本身很大比如mod 1e18那么res * a还是会爆掉long long。这种情况下我习惯写一个mul_mod函数long long mul_mod(long long a, long long b, long long mod) { long long res 0; while (b) { if (b 1) res (res a) % mod; a (a a) % mod; b 1; } return res; }这个就是“快速乘”原理和快速幂一模一样只是把乘法换成了加法。这也是位运算在数字运算里的另一种精彩应用。在 Python 里则完全不用担心这个问题Python 的大整数可以随便乘只是速度会慢一些但在竞赛里 Python 选手一般都会用内置的pow(a, n, mod)底层是 C 实现的比我们自己写的 Python 快速幂要快很多。4.3 n 1的判断写成 n % 2 1 可以吗完全可以效果一样。但有一个细微的差别在 Python 里对负数取余的结果和 C 不一样。Python 的-3 % 2结果是 1而 C 的-3 % 2结果是 -1。这会导致一个问题如果你用n % 2 1来判断负数的奇偶性在 Python 里没问题因为余数为 1但在 C 里-3 % 2 1是 false因为结果是 -1。而n 1就没有这个问题因为负数的二进制补码最低位和正数一样奇数的补码最低位一定为 1偶数为 0所以n 1对正负数判断都是对的。这也是为什么我习惯在快速幂里坚持用n 1而不是n % 2的原因之一。4.4 位运算优先级导致的小白错误这个坑我说多少遍都不嫌多。C/C 里位运算优先级是个大坑简单总结一下相关优先级从高到低算术运算符 - 移位运算符 关系运算符 ! 按位与 按位异或^ 按位或| 逻辑运算符 ||看到没的优先级竟然低于。所以如果你想写“n 的最低位是不是 1”千万别写if (n 1 1)因为先结合代码实际变成if (n (1 1))也就是if (n 1)碰巧凑对了但如果你写成if (n 1 ! 0)恭喜你!的优先级也高于实际变成if (n (1 ! 0))仍然是if (n 1)结果还是对的。然而这种“碰巧对”的代码是定时炸弹一旦哪天改动了别的条件就凉了。正确写法if ((n 1) ! 0)或者干脆if (n 1)。在 Python 里优先级类似的优先级也比低所以同样建议加括号。另外 Python 里还有个经典问题n 1只是算出右移的值并不会改变 n 自己必须写成n 1才能更新 n。我见过有人把这两行搞混结果循环跑了上万次 n 都不变直接死循环。5. 快速幂的战场从斐波那契到矩阵快速幂5.1 用快速幂求斐波那契数列很多人以为快速幂只能用来算整数幂其实它的思想可以迁移到任何满足结合律的运算上。最经典的例子就是斐波那契数列。斐波那契数列有矩阵递推关系[ F(n1) ] [ 1 1 ] ^ (n-1) [ F(2) ] [ F(n) ] [ 1 0 ] [ F(1) ]也就是说要求第 n 个斐波那契数本质上是求一个 2x2 矩阵的 n 次方。矩阵乘法也满足结合律所以完全可以把快速幂的模板套用在矩阵上只是把“乘底数”从整数相乘变成矩阵相乘。用快速幂求斐波那契数列的时间复杂度是 O(log n)这比常规的动态规划 O(n) 要快太多。当你要算第 10^18 个斐波那契数时动态规划根本跑不完而矩阵快速幂只需要大约 60 轮矩阵乘法。5.2 矩阵快速幂与 运算的配合矩阵快速幂代码里同样用到了运算struct Matrix { long long m[2][2]; }; Matrix multiply(Matrix A, Matrix B, long long mod) { Matrix C {0}; for (int i 0; i 2; i) for (int j 0; j 2; j) { for (int k 0; k 2; k) { C.m[i][j] (C.m[i][j] A.m[i][k] * B.m[k][j]) % mod; } } return C; } Matrix matrix_pow(Matrix base, long long n, long long mod) { Matrix res {1, 0, 0, 1}; // 单位矩阵 while (n) { if (n 1) { res multiply(res, base, mod); } base multiply(base, base, mod); n 1; } return res; }注意这里的res初始化为单位矩阵相当于整数快速幂里的“1”。因为任何矩阵乘单位矩阵还是它自己。n 1判断当前指数位是否为 1 的逻辑和整数版本完全一样只是base的自平方从“两个整数相乘”变成了“两个矩阵相乘”。矩阵快速幂不只是玩具。工程里很多递推式比如线性递推、马尔可夫链、转移矩阵本质都是求矩阵的幂。能用矩阵快速幂的地方运算都扮演着“检查二进制位”的角色。5.3 性能实测数据量一上来差距就明显了我自己跑过一个简单的对比计算 2^n mod 1000000007n 取 10^9。朴素循环跑了大概 1.8 秒在 O2 优化下。快速幂迭代版几乎瞬间返回循环次数只有 30 次。这个差距在小数据下根本看不出来但一旦 n 变成 10^18朴素循环连完成的可能都没有而快速幂仍然是几十轮循环就搞定。类似的思路还被用在卷积运算、大整数幂运算里面。比如某些数学库在算超大整数幂的时候也是用二进制分解指数来减少乘法次数因为大整数乘法代价高每减少一次乘法的收益都很大。6. 一些写代码的实战技巧与个人心得6.1 模板代码带上取模的通用版我最后整理一份自己常用的模板带取模支持负数指数处理通过逆元扩展可以直接抄走#include bits/stdc.h using namespace std; long long quick_pow(long long a, long long n, long long mod) { long long res 1; a % mod; while (n 0) { if (n 1) { res res * a % mod; } a a * a % mod; n 1; } return res; } // 求 a 在 mod 下的逆元mod 必须为素数 long long mod_inverse(long long a, long long mod) { return quick_pow(a, mod - 2, mod); } // 支持负数指数的快速幂mod 为素数时 long long quick_pow_any(long long a, long long n, long long mod) { if (n 0) return quick_pow(a, n, mod); long long inv mod_inverse(a, mod); return quick_pow(inv, -n, mod); }这里有一个小细节a % mod放在开头是为了防止 a 很大时第一次乘法就溢出。很多模板不写这一行我自己吃过大亏才加上。6.2 个人调试习惯与性能建议在我自己的实践里有几个习惯是踩过坑之后养成的第一写完快速幂先跑几个小用例验证边界a2, n0、a2, n1、a2, n10、a1, n1000000000分别对照手算结果。别嫌麻烦这种代码一旦出错是最难调的因为错误只在某个特定二进制位组合下才出现。第二取模时我习惯每轮都模而不是攒着最后模。这样虽然多做了几次取模运算但换来的是中间结果永远可控不会突然爆掉。性能影响微乎其微安全收益却很大。第三在 C 编译器里开了 O2 优化后n 1和n % 2生成的汇编几乎一样所以纠结用哪个意义不大真正决定性能的是循环次数是否真的到了 O(log n)。如果你发现你的快速幂跑了 O(n) 次循环肯定哪里写错了多半是n 1写成了n 1。第四Python 里不用手动写快速幂去比赛。Python 内置的pow(a, n, mod)就是快速幂的 C 实现又快又安全。手写 Python 快速幂更多是为了学习原理跑业务代码时别跟内置函数较劲。6.3 快速幂还能怎么变幂运算取模、双指数等快速幂的变形非常多我挑几个常见的说一下双指数幂计算 a^(b^c) mod m思路是先算指数部分对某个数取模再利用欧拉定理降幂。这种题目里快速幂只是其中一环还需要配合欧拉函数。浮点数幂如果底数是浮点数快速幂思路同样适用只是不再取模而且要注意精度损失。比如计算 1.0001 的 10^7 次方朴素循环的误差累积会很严重快速幂反而因为乘法次数少精度表现更好。大整数幂Python 或 Java 的 BigInteger 里进行大整数幂运算也可以用同样的二进制分解减少大整数乘法的次数运算时间能从 O(n) 降低到 O(log n)。这些变种有一个共同点核心都是“二进制分解 分治”而运算就是那个最顺手的工具。我自己的感受是一旦你把快速幂的“形”理解透看很多算法的效率优化都会有一种豁然开朗的感觉。最后再分享一个小技巧如果你在用 Python 刷题别嫌弃内置的pow但为了加深理解完全可以用手写的快速幂去测一测大指数的情况。把 n 设成 987654321分别跑内置pow和手写版本你会直观感受到二进制分解的魅力到底在哪里。我这个项目折腾完最大的收获不是记住了模板而是彻底理解了“为什么位运算在算法里无处不在”。希望这篇东西也能帮你把这块拼图补上。
阅读完成 · 觉得有帮助？
