优质博文：IT-BLOG-CN

题目

实现pow(x, n) ，即计算x的整数n次幂函数（即，xn ）。

示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：
输入：x = 2.10000, n = 3
输出：9.26100

示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

-100.0 < x < 100.0
-231 <= n <= 231-1
n是一个整数
要么x 不为零，要么n > 0。
-104 <= xn <= 104

代码

本题的方法被称为「快速幂算法」，有递归和迭代两个版本。这篇题解会从递归版本的开始讲起，再逐步引出迭代的版本。

当指数 n 为负数时，我们可以计算 x⁻ⁿ再取倒数得到结果，因此我们只需要考虑 n 为自然数的情况。

方法一：快速幂 + 递归
「快速幂算法」的本质是分治算法。举个例子，如果我们要计算 x⁶⁴，我们可以按照：x→x² →x⁴ →x⁸ →x¹⁶ →x³² →x⁶⁴的顺序，从 x 开始，每次直接把上一次的结果进行平方，计算 6 次就可以得到 x⁶⁴的值，而不需要对 x 乘 63 次 x。

再举一个例子，如果我们要计算 x⁷⁷ ，我们可以按照：x→x² →x⁴ →x⁹ →x¹⁹ →x³⁸ →x⁷⁷的顺序，在 x→x²，x² →x⁴ ，x¹⁹ →x³⁸这些步骤中，我们直接把上一次的结果进行平方，而在 x⁴ →x⁹ ，x⁹ →x¹⁹ ，x³⁸ →x⁷⁷这些步骤中，我们把上一次的结果进行平方后，还要额外乘一个 x。

直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 x。但如果我们从右往左看，分治的思想就十分明显了：

当我们要计算 xⁿ时，我们可以先递归地计算出 y=x^⌊n/2⌋，其中 ⌊a⌋ 表示对 a 进行下取整；

根据递归计算的结果，如果 n 为偶数，那么 xⁿ =y²；如果 n 为奇数，那么 xⁿ =y² ×x；

递归的边界为 n=0，任意数的 0 次方均为 1。

由于每次递归都会使得指数减少一半，因此递归的层数为 O(logn)，算法可以在很快的时间内得到结果。

class Solution {public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}public double quickMul(double x, long N) {if (N == 0) {return 1.0;}double y = quickMul(x, N / 2);return N % 2 == 0 ? y * y : y * y * x;}
}

时间复杂度： O(logn)，即为递归的层数。
空间复杂度： O(logn)，即为递归的层数。这是由于递归的函数调用会使用栈空间。

方法二：快速幂 + 迭代
由于递归需要使用额外的栈空间，我们试着将递归转写为迭代。在方法一中，我们也提到过，从左到右进行推导是不容易的，因为我们不知道是否需要额外乘 x。但我们不妨找一找规律，看看哪些地方额外乘了 x，并且它们对答案产生了什么影响。

我们还是以 x⁷⁷ 作为例子：

x→x² →x⁴ → + x⁹ → + x¹⁹ →x³⁸ → + x ⁷⁷并且把需要额外乘 x 的步骤打上了 + 标记。可以发现：

x³⁸ → + x⁷⁷中额外乘的 x 在 x⁷⁷中贡献了 x；

x⁹→+x ¹⁹中额外乘的 x 在之后被平方了 2 次，因此在 x⁷⁷中贡献了 x²² =x⁴；

x⁴→ + x⁹中额外乘的 x 在之后被平方了 3 次，因此在 x⁷⁷中贡献了 x²³=x⁸；

最初的 x 在之后被平方了 6 次，因此在 x⁷⁷ 中贡献了 x²⁶=x⁶⁴。我们把这些贡献相乘，x×x⁴×x⁸×x⁶⁴恰好等于 x⁷⁷。而这些贡献的指数部分又是什么呢？它们都是 2 的幂次，这是因为每个额外乘的 x 在之后都会被平方若干次。而这些指数 1，4，8 和 64，恰好就对应了 77 的二进制表示 (1001101)₂ 中的每个 1！

因此我们借助整数的二进制拆分，就可以得到迭代计算的方法，一般地，如果整数 n 的二进制拆分为

n=2ⁱ⁰+2ⁱ¹+⋯+2^ik

那么xⁿ=x²ⁱ⁰×x²ⁱ¹×⋯×x^2ik这样以来，我们从 x 开始不断地进行平方，得到 x²,x⁴ ,x⁸ ,x¹⁶,⋯，如果 n 的第 k 个（从右往左，从 0 开始计数）二进制位为 1，那么我们就将对应的贡献 x^2k计入答案。

下面的代码给出了详细的注释。

class Solution {public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}public double quickMul(double x, long N) {double ans = 1.0;// 贡献的初始值为 xdouble x_contribute = x;// 在对 N 进行二进制拆分的同时计算答案while (N > 0) {if (N % 2 == 1) {// 如果 N 二进制表示的最低位为 1，那么需要计入贡献ans *= x_contribute;}// 将贡献不断地平方x_contribute *= x_contribute;// 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可N /= 2;}return ans;}
}

时间复杂度： O(logn)，即为对 n 进行二进制拆分的时间复杂度。
空间复杂度： O(1)。