实现 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.0n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。题目链接：中文题目；英文题目
对于这道题我们首先会想到直接累乘来得到最后结果，比如2 ^ 4 = 2 * 2 * 2 * 2 = 8，但是如果幂非常的大，那么这个方法一般都是会超时的。所以我们可以考虑把幂部分进行拆分来达到简化计算的目的。
这里我们使用2为底数来简化原函数的幂部分，比如，5^10的幂可以拆解成：
10 = 2 ^ 1 + 2 ^ 3
那么具体我们怎么拆解呢？一种方法是连续减去最大的幂指数：10 - 8(2 ^ 3) = 2 - 2(2 ^ 1) = 0；另一种方法是反过来连续除以2，当商为奇数时，记录一个答案值：
后面的代码使用了方法二。迭代时如果先将幂变成正数，需要注意转换成long型，否则INT_MIN转换时会越界。另外，也可以使用递归的进行计算。递归结束边界和迭代是一样的，当幂函数为0结束递归返回1.0。
2.2.1 迭代实现
class Solution { public: double myPow(double x, int n) { long power = n < 0 ? -(static_cast<long>(n)) : n; // static_cast<long> - corner case: 1.00000 ^ -2147483648 // int power = n; // 用这个while的循环条件需改成：while (power) double ans = 1, product = x; // 5 ^ 2 ^ 0 while (power > 0) { // power & 1 == 1 ? ans *= product : ans; // 检查当前幂是否为奇数 power /= 2; product *= product; // 以5 ^ 10为例，这里连续产生：5 ^ 2 ^ 1, 5 ^ 2 ^ 2, 5 ^ 2 ^ 3, 5 ^ 2 ^ 4 ...... } return n < 0 ? 1 / ans : ans; } };2.2.2 递归实现
class Solution { public: double myPow(double x, int n) { if (!n) return 1.0; long power = n / 2; if (n < 0) { power = -power; x = 1 / x; } double res = myPow(x, power); if (n & 1 == 1) { return res * res * x; } return res * res; } };