剑指offer_12:数值的整数次方

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 1:
输入: 2.00000, 10
输出: 1024.00000

示例 2:
输入: 2.10000, 3
输出: 9.26100

示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

1、暴力解法，超时

x为0，n小于0时应该要抛出异常的，0没法做分母

class Solution {
    public double myPow(double x, int n) {
        if(x==0){
            return 0;
        }
        double res=1;
        if(n==0){
            return 1;
        }else if(n>0){
            while(n!=0){
                res*=x;
                n--;
            }
            return res;
        }else{
            while(n!=0){
                res*=x;
                n++;
            }
            return 1/res;
        }
    }
}

2、快速幂(递归)

详细的快速幂算法：https://blog.csdn.net/qq_19782019/article/details/85621386

正常我们计算指数就是一个一个的乘起来，比如2^{5就是2x2x2x2x2，2}n进行了n-1次乘法。

这个过程是可以优化的，使用二分的思路，比如2^5可以先算2x2得到4，再算4x4x2，就变成3次乘法。

快速幂就是将每一步的指数分成两半，用对应的底数做平方运算，即a^n=a(n/2)*a^(n/2)。

奇偶不一样：

n为奇数时：a^n=a(n-1)*a

n为偶数时：a^n=a(n/2)*a^(n/2)

这样时间复杂度就从O(n)降到了O(logn)

//易错样例：
//0.00001
//2147483647
//超时问题

//易错样例：
//1.00000
//-2147483648

class Solution {
    public double myPow(double x, int n) {
        if(n==0){
            return 1;
        }else if(n>0){
            if(n%2==0){
                return myPow(x*x,n/2);
            }else{
                return x*myPow(x*x,n/2);
            }
        }else{
            //return myPow(1/x,-n);
            //负数取反溢出
            return 1/x*myPow(1/x,-n-1);
        }
    }
}

3、快速幂(非递归)

class Solution {
    public double myPow(double x, int n) {
        double res=1;
        for(int i=n;i!=0;i/=2){
            if(i%2==0){
                x*=x;
            }else{
                res*=x;
                x*=x;
            }
        }
        if(n<0){
            return 1/res;
        }else{
            return res;
        }
    }
}

4、快速幂位运算

class Solution {
    public double myPow(double x, int n) {
        double res=1;
        long a=n;
        if(a<0){
            x=1/x;
            a=-a;
        }
        while(a!=0){
            if((a&1)!=0){
                res*=x;
            }
            x*=x;
            a>>=1;
        }
        return res;
    }
}