# 0050. Pow(x, n)
### 题目地址（50. Pow(x, n)）
### 题目描述
```
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
```
### 前置知识
* 递归
* 位运算
### 公司
* 阿里
* 腾讯
* 百度
* 字节
### 解法零 - 遍历法
#### 思路
这道题是让我们实现数学函数`幂`，因此直接调用系统内置函数是不被允许的。
符合直觉的做法是`将x乘以n次`，这种做法的时间复杂度是$O(N)$。
经实际测试，这种做法果然超时了。测试用例通过 291/304，在 `0.00001\n2147483647`这个测试用例挂掉了。如果是面试，这个解法可以作为一种兜底解法。
#### 代码
语言支持: Python3
Python3 Code:
```python
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1
if n < 0:
return 1 / self.myPow(x, -n)
res = 1
for _ in range(n):
res *= x
return res
```
### 解法一 - 普通递归（超时法）
#### 思路
首先我们要知道：
* 如果想要求 x ^ 4，那么我们可以这样求： (x^2)^2
* 如果是奇数，会有一点不同。 比如 x ^ 5 就等价于 x \* (x^2)^2。
> 当然 x ^ 5 可以等价于 (x ^ 2) ^ 2.5, 但是这不相当于直接调用了幂函数了么。对于整数，我们可以很方便的模拟，但是小数就不方便了。
我们的思路就是：
* 将 n 地板除 2，我们不妨设结果为 a
* 那么 myPow(x, n) 就等价于 `myPow(x, a) * myPow(x, n - a)`
很可惜这种算法也会超时，原因在于重复计算会比较多，你可以试一下缓存一下计算看能不能通过。
> 如果你搞不清楚有哪些重复计算，建议画图理解一下。
#### 代码
语言支持: Python3
Python3 Code:
```python
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1
if n == 1:
return x
if n < 0:
return 1 / self.myPow(x, -n)
return self.myPow(x, n // 2) * self.myPow(x, n - n // 2)
```
### 解法二 - 优化递归
#### 思路
上面的解法每次直接 myPow 都会调用两次自己。
我们不从缓存计算角度，而是从减少这种调用的角度来优化。
考虑 myPow 只调用一次自身可以么？ 没错，是可以的。
具体来说就是：
* 如果 n 是偶数，我们将 n 折半，底数变为 x^2
* 如果 n 是奇数， 我们将 n 减去 1 ，底数不变，得到的结果再乘上底数 x
这样终于可以 AC。
#### 代码
语言支持: Python3, CPP
Python3 Code:
```python
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1
if n == 1:
return x
if n < 0:
return 1 / self.myPow(x, -n)
return self.myPow(x * x, n // 2) if n % 2 == 0 else x * self.myPow(x, n - 1)
```
CPP Code:
```cpp
class Solution {
double myPow(double x, long n) {
if (n < 0) return 1 / myPow(x, -n);
if (n == 0) return 1;
if (n == 1) return x;
if (n == 2) return x * x;
return myPow(myPow(x, n / 2), 2) * (n % 2 ? x : 1);
}
public:
double myPow(double x, int n) {
return myPow(x, (long)n);
}
};
```
**复杂度分析**
* 时间复杂度：$O(logN)$
* 空间复杂度：$O(logN)$
### 解法三 - 位运算
#### 思路
我们来从位（bit）的角度来看一下这道题。如果你经常看我的题解和文章的话，可能知道我之前写过几次相关的“从位的角度思考分治法”，比如 LeetCode [458.可怜的小猪](https://leetcode-cn.com/problems/poor-pigs/description/)。
以 x 的 10 次方举例。10 的 2 进制是 1010，然后用 2 进制转 10 进制的方法把它展成 2 的幂次的和。
因此我们的算法就是：
* 不断的求解 x 的 2^0 次方，x 的 2^1 次方，x 的 2^2 次方等等。
* 将 n 转化为二进制表示
* 将 n 的二进制表示中`1的位置`pick 出来。比如 n 的第 i 位为 1，那么就将 x^i pick 出来。
* 将 pick 出来的结果相乘
这里有两个问题：
第一个问题是`似乎我们需要存储 x^i 以便后续相乘的时候用到`。实际上，我们并不需要这么做。我们可以采取一次遍历的方式来完成，具体看代码。
第二个问题是，如果我们从低位到高位计算的时候，我们如何判断最高位置是否为 1？我们需要一个 bitmask 来完成，这种算法我们甚至需要借助一个额外的变量。 然而我们可以 hack 一下，直接从高位到低位进行计算，这个时候我们只需要判断最后一位是否为 1 就可以了，这个就简单了，我们直接和 1 进行一次`与运算`即可。
如果上面这段话你觉得比较绕，也可以不用看了，直接看代码或许更快理解。
#### 代码
语言支持: Python3
Python3 Code:
```python
class Solution:
def myPow(self, x: float, n: int) -> float:
if n < 0:
return 1 / self.myPow(x, -n)
res = 1
while n:
if n & 1 == 1:
res *= x
x *= x
n >>= 1
return res
```
**复杂度分析**
* 时间复杂度：$O(logN)$
* 空间复杂度：$O(1)$
### 关键点解析
* 超时分析
* hashtable
* 数学分析
* 位运算
* 二进制转十进制
### 相关题目
* [458.可怜的小猪](https://leetcode-cn.com/problems/poor-pigs/description/)
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/50.pow-x-n.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.