【每日一题】剑指 Offer 16. 数值的整数次方

实现函数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 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。

直接考虑

首先想到的是循环遍历。但是不出所料，超出时长。。

class Solution {
    public double myPow(double x, int n) {
        double sum=1;
        if(n>=0){
             for(int i=0;i<n;i++){
                sum=sum*x;
            }
        }
        else{
            for(int i=0;i>n;i--){
                sum=sum/x;
            }  
        }
        return sum;
    }
}

快速幂运算

求 x^n 最简单的方法是通过循环将 n 个 x 乘起来，依次求 x^1, x^2, …, x^{n-1} ，时间复杂度为 O(n)。
快速幂法 可将时间复杂度降低至 O(log_2 n) ，以下从 “二分法” 和 “二进制” 两个角度解析快速幂法。

大神的数学推导，学不来。

算法流程：

1. 当 x = 0 时：直接返回 0（避免后续 x = 1 / xx=1/x 操作报错）。
2. 初始化 res = 1 ；
3. 当n<0 时：把问题转化至 n≥0 的范围内，即执行 x = 1/x=1/x ，n = - n ；
4. 循环计算：当 n=0 时跳出；
	4.1. 当n&1=1 时：
	4.2. 将当前 x 乘入 res（即res∗=x ）；
	4.3. 执行 x = x^2(即 x∗=x ）；
	4.4. 执行 n 右移一位（即 n >>= 1）。
5. 返回 res 。

Java 代码中 int32 变量 n∈[−2147483648,2147483647] ，因此当 n = -2147483648时执行 n = -n会因越界而赋值出错。解决方法是先将 n 存入 long 变量 b ，后面用 b操作即可。

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

复杂度分析：
时间复杂度 O(log2 n)二分的时间复杂度为对数级别。
空间复杂度 O(1 )： res, b 等变量占用常数大小额外空间。