快速幂

快速幂用 O(log n) 次乘法算出 a^n，比朴素的 n 次乘法快指数级。

思想

把指数 n 写成二进制：

例：13 = 1101₂ = 2³ + 2² + 2⁰

那么：

a¹³ = a⁸ · a⁴ · a¹

只需要算出 a¹, a², a⁴, a⁸（每个是前一个的平方），再按二进制位选择性相乘即可。

while (exp > 0) {
  if (exp & 1) result *= base;  // 当前位是 1：累乘
  base *= base;                  // base 平方，对应下一位
  exp >>= 1;
}

二进制位有多少（约 log₂ n 位），就执行多少轮——所以是 O(log n)。

复杂度

• 时间：O(log n) 次乘法
• 空间：O(1)

在动画里看什么

• 顶部一行是指数的二进制位（高位在左、低位在右），下方标注每一位对应的权重 2^k
• 当前底数等于 base^(2^k)，每过一位就平方一次
• result 是累加器；只有当前位为 1 时才把 result 乘上当前底数（这一步会闪烁暖红）
• 13 = 1101₂ 走完后，result = a^8 · a^4 · a^1 = a^13