快速幂是高效计算a^n的算法，时间复杂度o(log n)，核心是二进制拆分指数、平方降次与条件累乘；php非递归实现需初始化结果为1，循环中依n的二进制位决定是否累乘，并每次对底数平方及右移指数，注意每步取模防溢出。
什么是快速幂算法
快速幂是一种高效计算 an 的方法，时间复杂度从朴素的 O(n) 优化到 O(log n)。核心思想是利用二进制拆分指数，结合“平方降次”和“条件累乘”：比如计算 a13，把 13 写成二进制 1101，对应 a8 × a4 × a1，只需 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() 配合实现
