数值的整数次方

题目描述

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

第一次看到这个题目的时候，首先想到的是使用库函数。

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

但是很明显，题目考查的是造轮子的能力而不是使用轮子的能力，那么我们接下来看看怎么自己去实现这个轮子。
首先最容易想到的肯定就是利用一个循环去实现多次乘法。

public class Solution {
    public double Power(double base, int exponent) {
        double res = 1;
        for(int i = 0; i < exponent; i++) 
            res *= base;
        return res;
  }
}

看似很容易的题目，其实陷阱重重。
1）没有考虑指数为负数的情况。
这好办，我们记录下指数的正负，然后均取绝对值来计算，指数为负的再取倒数就好了。但是，事情有这么简单吗？
2）没有考虑底数为0的情况。
底数为0时，在指数为负最终取倒数的时候会发生分母为0的情况。
所以，修改后的代码为

public class Solution {
    public static double Power(double base, int exponent) {
        double p = base;
         
        if(exponent == 0 ) return 1;
        else if(exponent > 0) {
            for(int i = 1; i < exponent; i++)
                p *= base;
              return p;
        }
         
        else{
            if(base == 0) throw new RuntimeException("分母不能为0");
            for(int i = 1; i < -exponent; i++)
                p *= base;
            return 1 / p;
        }
  }
}

上述代码考虑地更加完善。但是，这种最平常的思路是最优的吗？有没有更快的方法呢？
快速幂可以为我们提供更好的时间复杂度。

public class Solution {
    public static double Power(double base, int n) {
        int exponent;
        if(n > 0)
            exponent = n;
        else if(n == 0)
            return 1;
        else {
            exponent = -n;
            if(base == 0)
                throw new RuntimeException("分母不能为0");
        }
        double res = 1, current = base;
        while(exponent != 0) {
            if((exponent & 1) == 1)
                res *= current;
            current *= current;
            exponent >>= 1;
        }
        return n >= 0 ? res : (1 / res);
    }
}

快速幂的时间复杂度为O（logN）
解释一下快速幂的思想：
假设我们要求a^{b，b可以拆成二进制，该二进制数第i位的权为2}(i-1)，例如当b==11时,b的二进制为1011

a11=a^(231+220+211+201)
则a11转变为求a^(20)*a(21)*a^(23)

a^(20)=a

a^(21)=a*a

a^(22)=aaa*a

a^(23)=aaaaaaa*a

那么如何实现求上述这些指数呢？就是通过current *= current 来实现，根据指数b的二进制来看：

1011

第0位对应a^(20)，

第1位对应a^(21)，

第2位对应a^(22)，

第3位对应a^(23)

当相应二进制位数为1则与之前的所有乘积相乘，若相应二进制位数为0则不参与相乘。以此类推。

幂计算很容易将int爆掉，所以可以考虑使用long long等。

除快速幂外还有矩阵快速幂，即使用矩阵计算代替乘法计算，其余算法思想一致，不列出具体代码。