题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0

牛客网题目链接

求解思路1

常规解法，需要注意几个点即可：

• 底数为0，不管多少次方都为0（一般底数不为0）
• 指数为0，结果为1
• 指数为负数，结果为正数次幂的倒数

class Solution {
public:double Power(double base, int exponent) {double res=base;if(exponent){if(exponent>0){for(int i=1;i<exponent;i++)res*=base;return res;}else{for(int i=1;i<-exponent;i++)res*=base;return 1.0/res;}}else if(base==0){return 0;}else{return 1.0;}}
};

运行时间：2ms占用内存：376k

求解思路2

据说啊，有这么一个公式：

我们回过头来看看思路1中的解法，如果我们要计算a的32次方的话就要计算32次

而有了上面的公式，我们要计算a的32次方，可以这么算：

先算$a^2$ -> 再算$a^4=a^{(2)\times 2}$ -> 再算$a^8=a^{(4)\times 2}$ -> 再算$a^{16}=a^{(8)\times 2}$，最后算$a^{32}=a^{(16)\times 2}$

哇，amazing！

算一个数的32次方我们只需要计算5次就可以了！！！

由于我们计算的次方比较低，因此可以采用递归的方法来计算，代码如下：

class Solution {
public:double Power(double base, int exponent) {if(exponent>0)return calculate(base,exponent);elsereturn 1.0/calculate(base,-exponent);}double calculate(double base,int exponent){if(exponent==0)return 1.0;if(exponent==1)return base;double res=calculate(base,exponent>>1);res*=res;if(exponent&0x1)res*=base;return res;}
};

运行时间：3ms占用内存：376k