50.pow(x,n)

50. Pow(x, n)

难度中等333

实现 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

思路描述：因为不用考虑大数问题，所以只需要循环地去计算就可以了，但是单纯的循环去算，比如：

for(int i = 1; i < n; i ++)
x *= x;
是会超时的。

所以我们可以考虑比如我们计算 x^8，就是 x^2 * x^2 * x^2 * x^2，当我们计算出来 x^2 之后就可以只进行三次乘法就可以了，相对于之前的 7 次乘法，时间大大减少了。

也就是 x^n 可以分解成若干个 x^i 的乘积

我们这里使用快速幂进行求解。我们看一下 n 的二进制形式一定是若干个 1 和 0 构成

所以我们可以看出来，每次乘的值都是前一个值的2倍，当 n 对应位为0时跳过

负数幂和正数幂相同，因为除以一个数就相当于乘这个数的倒数。

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0 || x==1.0){
            return 1.0;
        }
        long long num =n;
        if(num<0){
            num=-num;
            x= 1/x;
        }
        double ret = 1;
        while(num){
            if(num&1) ret*=x;
            x*=x;
            num>>=1;
        }
        return ret;
    }
};

ll quick_pow(ll a, ll b, ll mod) {
    ll ans = 1;
    while (b)
    {
        if (b & 1) ans = (ans*a) % mod;
        a = (a*a) % mod;
        b >>= 1;
    }
    return ans;
}
b是可以为double的,

class Solution {
public:
    double  quick_pow(double a, long long  b) {
        double ans = 1;
        while (b)
        {
            if (b & 1) ans = (ans*a) ;
            a = (a*a) ;
            b >>= 1;
        }
        return ans;
    }
    double myPow(double x, int n) {
        if(n==0 || x==1.0){
            return 1.0;
        }
        long long num =n;
        if(num<0){
            num=-num;
            x= 1/x;
        }
        return quick_pow(x,num);
    }
};