题目：
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
思路：
Math.pow(base, exponent) ? （面试官的微笑）
考虑
- base为0，exponent<0，无效的输入
- 指数为正
- 指数为负
- 指数为0
四种情况即可
- 朴素算法
就是把a连乘b次，时间复杂度为O(n) - 快速幂算法
时间复杂度为O(logn)，原理如下：
假设我们要求a ^ b，那么其实b是可以拆成二进制的，该二进制数第i位的权为2 ^ (i-1)，例如当b==11时，a ^ 11 = a ^ (2 ^ 0+2 ^ 1 + 2 ^3 )
11的二进制是1011，11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1，因此，我们将a¹¹转化为算 a^1 * a ^ 2 * a ^ 8，看出来快的多了吧原来算11次，现在算三次。
由于是二进制，很自然地想到用位运算这个强大的工具：&和>>
&运算通常用于二进制取位操作，例如一个数 & 1 的结果就是取二进制的最末位。还可以判断奇偶x & 1==0为偶，x & 1==1为奇。 >>运算比较单纯，二进制去掉最后一位
public class Solution {
public double Power(double base, int exponent) {
double ans = 1;
int n = exponent;
if(exponent < 0){
if(base == 0)
throw new RuntimeException("分母不能为0");
n = -exponent;
}
if(exponent == 0)
return 1;
while(n != 0){
if((n & 1) == 1)
ans *= base;
base *= base;
n >>= 1;
}
return exponent > 0 ? ans : (1 / ans);
}
}
