快速幂（二进制取幂）
数学与数论 · 二进制拆分 · O(log n)
把指数拆成二进制
求 aⁿ，一个一个乘要乘 n 次，太慢。快速幂的关键观察是：任何指数 n 都能写成二进制，也就是若干个 2ᵏ 之和。比如 13 = 8 + 4 + 1 = 1101₂。于是 aⁿ = ∏ a^(2ᵏ)——把对应位为 1 的那些 a^(2ᵏ) 乘起来就行。而 a^(2ᵏ) 这一串（a¹, a², a⁴, a⁸…）只要让底数反复平方就能一路算出来，每次平方一步。
反复平方 + 位选累乘
算法从低位到高位扫描 n 的二进制：维护一个底数base（初值 a，每步平方成 a², a⁴, a⁸…）和一个结果（初值 1）。看当前位：是 1 就把当前的 base 乘进结果；是 0 就只平方、不乘。扫完 log₂n 个位就得到答案，一共只做 O(log n) 次乘法。
下面固定 a=3, n=13。点「下一步」逐步看：一行幂块3¹=3, 3²=9, 3⁴=81, 3⁸=6561 逐张出现（底数平方链），每块标着它对应的二进制位——位为 1 的块选中（绿）、乘进结果，位为 0 的块跳过（灰），当前块琥珀高亮。走到底，选中的 3¹·3⁴·3⁸ = 3×81×6561 = 1594323 = 3¹³。右侧代码随每一步同步高亮。
求 313，指数 13 = 11012
结果 = 1 = 1
求 3^13：把指数 13 写成二进制 1101₂；底数从 3 起反复平方（3¹→3²→3⁴→3⁸），位为 1 就把当前平方乘进结果
1function fastPow(a: number, n: number): number {
2 let result = 1;
3 let base = a;
4 while (n > 0) { // 从低位到高位扫描 n 的二进制
5 if (n & 1) result *= base; // 当前位为 1 → 把当前平方乘入结果
6 base *= base; // 底数平方：a → a² → a⁴ → a⁸
7 n >>= 1; // 右移，看下一位
8 }
9 return result;
10}
求3^13
指数二进制1101₂
结果1
1 / 6
又快又是加密的引擎
拆分：
平方链：底数每步平方，
位选：当前位为 1 才乘进结果；共
模幂：每步再取一次模
n = Σ 2ᵏ（二进制），aⁿ = ∏ a^(2ᵏ)。平方链：底数每步平方，
a → a² → a⁴ → a⁸，一路算出各 a^(2ᵏ)。位选：当前位为 1 才乘进结果；共
O(log n) 次乘法。模幂：每步再取一次模
mod m，就是 RSA / Diffie-Hellman 的 aⁿ mod m。 快速幂真正的舞台是模幂运算aⁿ mod m：只要在每次乘法后再取一次模，数值就永远不超过 m²，于是能在 n 大到几百位时依然秒算——这正是 RSA 加解密、Diffie-Hellman 密钥交换的计算核心。同样的「二分幂」思想换成矩阵乘法，就是矩阵快速幂，能把斐波那契等线性递推加速到 O(log n)。