题目内容

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

示例

示例 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

提示

1、-100.0 < x < 100.0
2、-2^31 <= n <= 2^31-1
3、-10^4 <= x^n <= 10^4

题解

本题考查快速幂算法或者叫反复平方法。基本思想如下：

求出x^n的n的二进制表示，用2的幂乘来表示n，最后求出。这样做，我们可以将本来要让x乘n次的情况，降低在30次左右(因为可以预处理x^(2^0)、···、x^(2^30))。这里，给出一个例子，方便大家理解。

假设要求x^7，7的二进制表示为0111，则就是求x^(2^0+2^1+2^2)，然后把式子拆开的话就知道应该乘预处理的哪些项了。

这里，我们在实现的时候，需要注意一下，可以根据幂的二进制表示的1或0的情况，在预处理的时候，把结果同步处理。

若幂为负数，则res = 1/res。

具体，请看代码。

代码

class Solution {
public:
    double myPow(double x, int n) {
        //快速幂，反复平方法
        typedef long long LL;
        bool is_minus = n < 0;
        double res = 1;
        for(LL k = abs(LL(n)); k; k >>= 1){
            if(k & 1) res *= x;//枚举2进制的位，判断是1还是0，如果是1则乘起来，不是1则跳过。
            x *= x;
        }

        if(is_minus) res = 1/res;//判断是否是负数
        return res;
    }
};