# 问题 原题链接：[https://leetcode.com/problems/powx-n/](https://leetcode.com/problems/powx-n/) Implement pow(x, n), which calculates x raised to the power n (xn). Example 1: ``` Input: 2.00000, 10 Output: 1024.00000 ``` Example 2: ``` Input: 2.10000, 3 Output: 9.26100 ``` Example 3: ``` Input: 2.00000, -2 Output: 0.25000 Explanation: 2^-2 = 1/2^2 = 1/4 = 0.25 ``` Note: - -100.0 < x < 100.0 - n is a 32-bit signed integer, within the range [−231, 231 − 1] # 分析过程 - 输入：底数 x 和幂次 n - 输出：幂次计算的结果 - 思路：题意其实是快速进行幂次计算，方法是进行二分幂次。题目允许负数次幂，因此如果是负数次幂，可以提前把底数倒过来，然后就和计算正数次幂一样了。 - 递归方法：递归求出`x^(n / 2)`的结果，最后根据奇数次幂和欧数次幂计算最后一步即可。 - 循环方法：以二进制的视角看指数，值是 1 的位代表最终结果会含有对应次幂的因数，具体思路看注释。 # 解决方法 递归方法： ```cpp class Solution { public: double myPow(double x, long n) { // 递归结束条件 if (n == 0) { return 1; } else if (n == 1) { return x; } // 如果是负数次幂，先把x倒数 if (n < 0) { n = -n; x = 1 / x; } // 递归取得x的n/2次幂的结果 double res = myPow(x, n / 2); // 根据幂次是否是偶数得到结果 if (n % 2 == 1) { return res * res * x; } else { return res * res; } } }; ``` 循环方法： ```cpp class Solution { public: double myPow(double x, long n) { double s = 1; // 如果是负数次幂，先把x倒数 if (n < 0) { n = -n; x = 1 / x; } while (n > 0) { // 按二进制看n // 例如：n = 1011b // 第四位是1，代表结果里有个因数是x^3，如果是0，表示不含有。 // 所以最后结果就是 x^3 * x^1 * x^0 if (n & 1) { s *= x; } x *= x; n >>= 1; } return s; } }; ```