数值的整数次方

1.题目
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。（保证base和exponent不同时为0 —）
如，输入2，3；返回8.00000

2.思路
方法一：直接调用Math类的pow方法

public class Solution {
    public double Power(double base, int exponent) {
        return Math.pow(base,exponent);
  }
}

方法二：上述方法就显得本题毫无意义，可直接实现pow()方法
时间复杂度：O(n)

public class Solution {
    public double Power(double base, int exponent) {
        if(base==0&&exponent>0){//0的正数次方为0
            return 0;
        }
        if(exponent==0){//任何数的0次方都为1
            return 1;
        }
        if(base==0&&exponent<0){//1/0是无穷大
            throw new RuntimeException();
        }
        double res=1;
        if(exponent<0){//幂小于0的情况
            exponent=-exponent;
            base=1/base;
        }
        for(int i=0;i<exponent;i++){//幂大于0的情况
            res*=base;
        }
        return res;
  }
}

方法三：利用递归实现
递归快速幂法 时间复杂度o(logn) 空间复杂度o(logn)
n为偶数时：b^n = (b^(n/2))^2
n为奇数时：b^n = (b^(n/2))^2*b

public class Solution {
    public double Power(double base, int exponent) {
        if(base==0&&exponent>0) return 0;
        if(exponent==0) return 1;
        if(base==0&&exponent<0) throw new RuntimeException();
        if(base==1) return 1;
        double res=1.0;
        int n=Math.abs(exponent);
        res=Power(base,n>>1);//右移一位除2，左移一位乘2
        res*=res;
        if((n&1)==1) res*=base;//奇数与1相与为1，偶数与1相与为0
        if(exponent<0) res=1/res;
        return res;
  }
}

方法四：优化，从数值运算简化，并考虑Java 中 int32 变量区间 n∈[−2147483648,2147483647]，因此当 n=−2147483648时执行 n=−n 会因越界而赋值出错。解决方法是先将n存入 long 变量b，后面用b操作即可。

public class Solution {
    public double Power(double base, int exponent) {
        if(base==0.0f) return 0.0; //0的任意次方为0
        long b=exponent;  //防止取反越界
        if(b<0){  //全部转为正数
            b=-b;
            base=1/base;
        }
        double res=1.0;
        while(b>0){
            if((b&1)==1) res*=base;  //此位为1，则累计
            base*=base;//累计底数
            b>>=1;//移位
        }
        return res;
  }
}