题解 | #数值的整数次方#

题目难度:中等
考察内容：快速幂，递推
题目内容：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题，也不用考虑小数点后面0的位数。
题目分析
首先有负数次幂，可以进行转化，a^(-b)=1/a^b
所以只用考虑a^b即可，很明显可以递推
算法1（递推）
思路很简单，在代码中体现

class Solution {
public:
    double Power(double base, int exponent) {
        double ans=1;//记录答案
        int k=0;//如果exponent<0 记录答案应该为1/ans
        if(exponent<0)exponent=-exponent,k=1;
        //小于0，将b变为正数，记录k=1
        while(exponent--)
        {
            ans=ans*base;
            //计算答案
        }
        if(k==1)return 1.0/ans;
        return ans;
    }
};

复杂度分析：时间复杂度O(n),空间复杂度O(1)
算法2（快速幂）
对于一个数可以用二进制表示，int范围内有32位，可以利用二进制进行优化，比如我们要求2^8，我们通过当为偶数的时候，a^n=(aa)^(n/2)，当n为奇数时，a^n=a(aa)^(n/2)的形式，可以转化为4^4->8^2->64^1，就可以了，2^5的话24^2->2*16^1。

通过上面的思路，代码很容易实现了

class Solution {
public:
    double Power(double base, int exponent) {
        int f=0;
        if(exponent<0)f=1,exponent=-exponent;
        double ans=1;
        while(exponent)
        {
            if(exponent&1)ans*=base;
            base*=base;
            exponent>>=1;
        }
        if(f)ans=1/ans;
        return ans;
    }
};

复杂度分析：时间复杂度O(logn),空间复杂度O(1)