0050. Pow(x, n)

题目信息

题号:
  1. Pow(x, n)

难度:

Medium

主题:

数学、递归、二进制、快速幂

原题:

LeetCode 0050

重点:

从逐次相乘推导到指数折半,并安全处理负指数与 INT_MIN

题目重述

给定浮点数 x 和 32 位有符号整数 n,计算并返回 x 的 n 次幂。

不能依赖把答案预先存入表中。零指数满足 x^0 = 1;负指数满足 x^n = (1 / x)^(-n)。题目保证不会要求计算无定义的零的非正整数次幂,并保证结果位于题目规定的 浮点范围内。

n 的范围为 [-2^31, 2^31 - 1],因此处理负指数时必须考虑最小 32 位整数无法在 int 中直接取相反数。

自建示例

输入:x = 2.0, n = 13
输出:8192.0

13 = 8 + 4 + 1
2^13 = 2^8 × 2^4 × 2

负指数示例:

输入:x = 4.0, n = -3
输出:0.015625

4^-3 = (1/4)^3 = 1/64

边界示例:

输入:x = 1.0, n = -2147483648
输出:1.0

-n 无法由 32 位 int 表示;必须先把 n 提升到更宽的整数类型。

C++ 实现

class Solution {
private:
    double repeatedMultiplication(double base, long long exponent) {
        double result = 1.0;
        for (long long count = 0; count < exponent; ++count) {
            result *= base;
        }
        return result;
    }

    double recursiveFastPower(double base, long long exponent) {
        if (exponent == 0) return 1.0;

        double half = recursiveFastPower(base, exponent / 2);
        double squared = half * half;
        if (exponent % 2 == 0) return squared;
        return squared * base;
    }

    double iterativeFastPower(double base, long long exponent) {
        double result = 1.0;

        while (exponent > 0) {
            if (exponent % 2 == 1) {
                result *= base;
            }
            base *= base;
            exponent /= 2;
        }
        return result;
    }

public:
    double myPow(double x, int n) {
        long long exponent = n;
        if (exponent < 0) {
            x = 1.0 / x;
            exponent = -exponent;
        }
        return iterativeFastPower(x, exponent);
    }
};

题解

重复乘法基线

当指数为非负整数时,乘方定义可以直接写成:

x^n = 1 × x × x × ... × x
              共 n 个 x

repeatedMultiplication 完全按照定义执行,因此不会遗漏任何乘因子。它需要 n 次乘法;32 位正指数最多接近 2.1 × 10^9,线性次数无法接受。

需要利用的结构不是底数,而是指数可以不断折半。

指数折半

设非负指数为 n。若 n = 2k:

x^n = x^(2k) = (x^k)^2

若 n = 2k + 1:

x^n = x^(2k+1) = (x^k)^2 × x

每次只需求一次 x^k,再平方得到偶数部分。若把 power(x, n / 2) 调用两次,两棵递归子树会重复计算, 调用数仍会退化到线性级。recursiveFastPower 先保存 half,其递推关系因此为:

T(n) = T(n / 2) + O(1)

指数每层减半,递归深度和乘法次数都降为 O(log n)。零指数返回 1;随后根据奇偶性返回 half² 或 half² × base,与上面的代数分解完全一致。

二进制迭代

不断判断奇偶并除以 2,等价于从低位到高位读取指数的二进制表示。以 13 为例:

13 = 1101₂ = 2³ + 2² + 2⁰
x^13 = x^8 × x^4 × x

循环中的 base 依次代表:

x, x², x⁴, x⁸, ...

当前最低位为 1 时,把对应幂乘入 result;最低位为 0 时跳过。每轮把 base 平方,并把指数除以 2,从而转向下一位。

快速幂不变量

负指数归一化之后,设初始目标为:

originalBase^originalExponent

迭代过程始终保持:

result × base^exponent
= originalBase^originalExponent

初始 result = 1,等式成立。

若 exponent = 2k,更新 base = base²、exponent = k 后:

result × (base²)^k
= result × base^(2k)

若 exponent = 2k + 1,先执行 result *= base,再平方底数并折半指数:

result' × (base²)^k
= result × base × base^(2k)
= result × base^(2k+1)

两种更新都保持目标值不变。循环结束时 exponent = 0,不变量变为:

result × base^0 = result

因此 result 就是原目标幂。每轮删除一个二进制位,所以迭代次数与指数位数同阶。

负指数归一化

对 n < 0:

x^n = (1 / x)^(-n)

先把底数改为 1 / x,再把指数改为非负值,递归和迭代核心就无需处理符号。

32 位有符号整数范围不对称:

最小值:-2147483648
最大值: 2147483647

当 n = INT_MIN 时,数学上的 -n 超出 int 上界。代码先执行:

long long exponent = n;

数值提升到更宽类型后,再执行 exponent = -exponent 才不会溢出。这一步必须发生在取相反数之前。

状态演化

对 2^13:

exponent

base

最低位

result 更新后

13

2

1

2

6

4

0

2

3

16

1

32

1

256

1

8192

0

65536

结束

8192

每一行都满足 result × base^exponent = 2^13。

边界处理

n = 0

循环不执行,返回初始值 1。

n = 1

唯一二进制位为 1,底数恰好乘入一次。

x = 0 且 n > 0

快速幂自然得到 0。

x = 1 或 x = -1

平方和指数奇偶会自然得到正确结果,不需要特殊分支。

n = INT_MIN

通过 long long 安全保存其绝对值。

代码演进

repeatedMultiplication 直接执行乘方定义,时间随指数绝对值线性增长。

recursiveFastPower 利用奇偶分解把指数每次减半,并且只计算一次半幂。

iterativeFastPower 进一步把递归过程改写为二进制扫描,以 result × base^exponent 为不变量,只保存常量个状态。 公开入口先归一化负指数,再调用该方法。

复杂度分析

设 N = |n|。

重复乘法执行 N 次乘法,时间为 O(N),额外空间为 O(1)。

递归快速幂每层把指数减半,时间为 O(log N),递归栈为 O(log N)。

迭代快速幂每轮删除一个二进制位,时间为 O(log N),额外空间为 O(1)。当 n = 0 时,时间为 O(1)。