数值的整数次方

题目描述：

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

解析一：

初看，就是求一个 double类型的数值的n次方，用代码来写就是n次数值相乘。
但是，这道题的关键就是对边界值的充分考虑。下面来依次解答：

• base==0.0
  从数学规定上可知，底数不能为0，故此时抛出异常
• 指数（exponent）是0
  非零的任意数的0次方结果都是1
• 指数（exponent）是负数
  “负指数幂”：a的-r次幂(r为任何正数)定义为a的r次幂的倒数。

代码一：

根据如上思路，分情况可写作代码如下：

public class Solution {
    public double Power(double base, int exponent) {
        double res =1.0; //double类型数据的初始化
        if(base == 0.0){
            //底数不能为0
            return 0.0;
        }else if(exponent ==0){
            //非零底数的0次幂，结果为1
            return 1.0;
        }else if(exponent<0){
            //负指数幂
            int exp = -exponent;
            for(int i =0;i<exp;i++){
                res *= base;
            }
            return 1/res;
        }else{
            //正指数幂
            for(int j=0;j<exponent;j++){
                res *= base;
            }
            return res;
        }
  }
}

这种写法要把各种情况都考虑清楚，逻辑清晰，考虑全面才行。
这种算法的时间复杂度为O(N)。

---

解析二：

可以找出可以优化的算法，因为是求base的exponent次幂，可以用递归
当exponent为偶数时：base^n = base^(n/2) * base^(n/2)
当exponent为奇数是：base^n = base^(n/2) * base^(n/2) *base
这样就可以递归地求出base^(n/2) 的大小，最后需要判断exponent的奇偶再进行最后一步运算即可。

代码二：

这种方法，也要认真考虑底数为0，指数为0，指数为负数的各种情况。

public class Solution {
    public double Power(double base, int exponent) {
        double res = 1.0;
        if(base==0.0){
            return 0.0;
        }else if(exponent==0){
            return 1.0;
        }
        int n = exponent>0?exponent:(-exponent);
        res  =  Power(base,n/2);  //递归调用
        res *= res;
        if(n%2==1)
            res *= base;
        res = (exponent>0) ? res : 1/res;
        return res;
  }
}

用了递归的方法，时间复杂度优化为O(logN)。

之前看到有其他人的解法，可以用正整数的右移一位来实现除以2的效果，即n>>1。