题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
第一次看到这个题目的时候，首先想到的是使用库函数。
public class Solution {
public double Power(double base, int exponent) {
return Math.pow(base, exponent);
}
}
但是很明显，题目考查的是造轮子的能力而不是使用轮子的能力，那么我们接下来看看怎么自己去实现这个轮子。
首先最容易想到的肯定就是利用一个循环去实现多次乘法。
public class Solution {
public double Power(double base, int exponent) {
double res = 1;
for(int i = 0; i < exponent; i++)
res *= base;
return res;
}
}
看似很容易的题目，其实陷阱重重。
1）没有考虑指数为负数的情况。
这好办，我们记录下指数的正负，然后均取绝对值来计算，指数为负的再取倒数就好了。但是，事情有这么简单吗？
2）没有考虑底数为0的情况。
底数为0时，在指数为负最终取倒数的时候会发生分母为0的情况。
所以，修改后的代码为
public class Solution {
public static double Power(double base, int exponent) {
double p = base;
if(exponent == 0 ) return 1;
else if(exponent > 0) {
for(int i = 1; i < exponent; i++)
p *= base;
return p;
}
else{
if(base == 0) throw new RuntimeException("分母不能为0");
for(int i = 1; i < -exponent; i++)
p *= base;
return 1 / p;
}
}
}
上述代码考虑地更加完善。但是，这种最平常的思路是最优的吗？有没有更快的方法呢？
快速幂可以为我们提供更好的时间复杂度。
public class Solution {
public static double Power(double base, int n) {
int exponent;
if(n > 0)
exponent = n;
else if(n == 0)
return 1;
else {
exponent = -n;
if(base == 0)
throw new RuntimeException("分母不能为0");
}
double res = 1, current = base;
while(exponent != 0) {
if((exponent & 1) == 1)
res *= current;
current *= current;
exponent >>= 1;
}
return n >= 0 ? res : (1 / res);
}
}
快速幂的时间复杂度为O（logN）
解释一下快速幂的思想：
假设我们要求ab，b可以拆成二进制，该二进制数第i位的权为2(i-1)，例如当b==11时,b的二进制为1011
a11=a^(231+220+211+201)
则a11转变为求a(20)*a(21)*a^(23)
a^(20)=a
a^(21)=a*a
a^(22)=aaa*a
a^(23)=aaaaaaa*a
那么如何实现求上述这些指数呢？就是通过current *= current 来实现，根据指数b的二进制来看：
1011
第0位对应a^(20)，
第1位对应a^(21)，
第2位对应a^(22)，
第3位对应a^(23)
当相应二进制位数为1则与之前的所有乘积相乘，若相应二进制位数为0则不参与相乘。以此类推。
幂计算很容易将int爆掉，所以可以考虑使用long long等。
除快速幂外还有矩阵快速幂，即使用矩阵计算代替乘法计算，其余算法思想一致，不列出具体代码。
