LeetCode 50题Pow(x,n)迭代快速幂核心代码疑问解答

这段代码是**快速幂（二分幂）**的迭代实现，核心是通过二分指数将时间复杂度从O(n)降到O(logn)，这也是它能避免超时的原因。下面逐个解答你的疑问：

1. double resisual = 1;的具体作用是什么？ #

resisual（应为拼写错误，正确写法是residual）用来存储指数分解过程中无法被2整除的剩余因子。快速幂的本质是把指数拆成2的幂次之和，比如x^5 = x^(2² + 1) = (x²)² * x，这里单独的x就会被存到resisual里。初始值设为1是因为1是乘法的单位元，不会影响后续的乘积结果。

2. 循环中i = i/2的用途是什么，为何不会导致计算逻辑错误？ #

这是快速幂的核心操作：将指数二分。数学上，x^n等价于(x²)^(n/2)（n为偶数时），或者x * (x²)^((n-1)/2)（n为奇数时）。每次把指数减半，相当于把问题规模缩小一半，原本需要n次乘法的计算，现在只需要log₂n次。这个操作不会出错是因为上述等价关系严格符合幂运算规则，比如x^6 = (x²)^3、x^7 = x * (x²)^3，完全成立。

3. 代码片段if(i%2 == 1) { resisual = resisual * x; }的作用是什么？ #

当当前指数i是奇数时，说明二分后会多出来一个当前的x因子。比如计算x^5，第一次循环i=5是奇数，此时把x乘到resisual里，然后x变成x²，i变成2（5//2）；接下来i=2是偶数，直接把x变成x^4，i变成1，循环结束。最后resisual*x就是x * x^4 = x^5，这个判断用来捕获并存储奇数指数带来的额外因子，避免遗漏。

4. 为何使用x = x * x而非类似ans=ans*x的写法？ #

x = x * x是快速幂的关键，它通过不断平方底数来匹配二分后的指数。如果用ans=ans*x，那就是普通的线性乘法，时间复杂度是O(n)，对于大指数（比如10^9）肯定会超时。而平方底数的方式，每次都能把需要计算的幂次翻倍，比如从x到x²再到x^4，只需要3次操作就能得到x^8，效率提升非常明显。

5. 最后返回return resisual*x;的原因是什么？ #

循环的条件是i > 1，当i降到1时循环就停止了。此时的x对应的是最后一次二分后的底数（比如计算x^5时，循环结束后x是x^4），而resisual是之前所有奇数因子的乘积（这里是x）。把两者相乘，就得到了完整的幂次结果。如果指数是偶数，比如x^4，循环结束后resisual是1，x是x^4，相乘后就是正确结果；如果指数是1，循环根本不会执行，直接返回1*x=x，也符合预期。

内容的提问来源于stack exchange，提问作者Souvik Roy