PHP 实现快速幂算法面试题

快速幂是高效计算a^n的算法，时间复杂度o(log n)，核心是二进制拆分指数、平方降次与条件累乘；php非递归实现需初始化结果为1，循环中依n的二进制位决定是否累乘，并每次对底数平方及右移指数，注意每步取模防溢出。

什么是快速幂算法

快速幂是一种高效计算 aⁿ 的方法，时间复杂度从朴素的 O(n) 优化到 O(log n)。核心思想是利用二进制拆分指数，结合“平方降次”和“条件累乘”：比如计算 a¹³，把 13 写成二进制 1101，对应 a⁸ × a⁴ × a¹，只需 3 次乘法（而非 12 次）。

PHP 实现非递归版本（推荐面试写法）

非递归更直观、无栈溢出风险，也体现对位运算的理解：

• 初始化结果为 1，底数为 a，指数为 n
• 循环处理 n > 0：若当前 n 是奇数（n & 1），将当前底数乘入结果；然后底数自乘（base = base * base），n 右移一位（n >>= 1）
• 注意取模：题目常要求结果对 10⁹+7 等大质数取模，每次乘法后都应 % MOD 防止溢出

带取模的完整 PHP 示例

// 示例：计算 (a ^ b) % mod

function quickPow($a, $b, $mod) {
  $res = 1;
  $base = $a % $mod;
  while ($b > 0) {
    if ($b & 1) {
      $res = ($res * $base) % $mod;
    }
    $base = ($base * $base) % $mod;
    $b >>= 1;
  }
  return $res;
}

立即学习“PHP免费学习笔记（深入）”；

面试时容易被追问的点

• 负指数怎么处理？：若题目允许，可先转为正指数再求逆元（需模为质数，用费马小定理）
• 底数为 0 或 1 怎么办？：0⁰ 通常按题意定义（常见为 1）；0ⁿ（n>0）直接返回 0；1ⁿ 恒为 1
• 为什么用位运算比 $b /= 2 更好？：$b >>= 1 是整数右移，避免浮点误差；$b & 1 比 $b % 2 == 1 更快且语义清晰
• 能否处理大整数？：PHP 的 int 有上限，如需超大数，可用 gmp_powm() 或 bcmod() 配合实现