企业官网建设流程全解析

如果有人让你实现一个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; }

每轮循环里有两件事：

1. if (n & 1)判断当前二进制位是否为 1，是的话就把当前底数乘进结果。
2. a = a * a % mod让底数自平方，对应指数位每前进一位。
3. n >>= 1让指数右移一位，准备看下一个二进制位。

模拟一下a^13的执行过程就清楚了：

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^18，res * a会超过 64 位，这时候要么用__int128，要么用“快速乘”技巧，也就是把乘法转换成加法累加，再用快速幂的思路处理。

4. 常见问题与排坑实录：这些坑我全都踩过

4.1 n=0、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(n+1) ] [ 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 1000000007，n 取 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 个人调试习惯与性能建议

在我自己的实践里，有几个习惯是踩过坑之后养成的：

第一，写完快速幂先跑几个小用例验证边界，a=2, n=0、a=2, n=1、a=2, n=10、a=1, n=1000000000，分别对照手算结果。别嫌麻烦，这种代码一旦出错，是最难调的，因为错误只在某个特定二进制位组合下才出现。

第二，取模时我习惯每轮都模，而不是攒着最后模。这样虽然多做了几次取模运算，但换来的是中间结果永远可控，不会突然爆掉。性能影响微乎其微，安全收益却很大。

第三，在 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和手写版本，你会直观感受到二进制分解的魅力到底在哪里。我这个项目折腾完，最大的收获不是记住了模板，而是彻底理解了“为什么位运算在算法里无处不在”。希望这篇东西也能帮你把这块拼图补上。