剑指offer--12. 数值的整数次方

题目：
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

思路：
Math.pow(base, exponent) ? （面试官的微笑）

考虑

1. base为0，exponent<0，无效的输入
2. 指数为正
3. 指数为负
4. 指数为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);
  }
}