题目

Implement pow(x, n).

分析

将幂转化为2的次方即可。
举例为：x^10=(x5)^2=((x2)^2*x)2=((xx)^2x)^2
需要注意几项易错点：1，n可能为负数；2，处理n=-1和n=-2147483648的情况

double myPow(double x, int n) {
    int flag=1;
    double ans=x;
    int temp[100]={0};
    int length=0;
//转化为long long 格式，防止溢出
    long long n1=n;
    if(n1<0)
    {
        n1=-n1;
        flag=-1;
    }
    if(n1==0)return 1;
    else if(n1==1)
    {   
        if(flag==-1)
            return 1/x;
        else
            return x;
    }
    else
    {
//依次计算，奇数次幂还是偶数次幂
        while(n1>1)
        {
            if(n1%2==0)
            {
                temp[length]=0;
            }
            else
            {
                temp[length]=1;
            }
            n1=n1/2;
            length++;
        }
    }
//反过来，把幂相乘得到结果
    for(int i=0;i<length;i++)
    {
        ans=ans*ans;
        if(temp[length-1-i]==1)
            ans=ans*x;
    }
//判断是正或负数次幂
    if(flag==-1)
        return 1/ans;
    else
        return ans;
}