二分法，快速幂

题目链接-来源：力扣（LeetCode）

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

思路：

此题一上来应有暴力求解的思路，通过 pow(x, n - 1) (n > 0)或 pow(x, n + 1) (n < 0)递归或迭代地求解。
但是暴力解法会超时，我们考虑简化运算。
注意到，当n为偶数的时候，我们只需计算 pow(x, n / 2)，然后将结果平方即可。而当n为奇数时，我们依然可以 计算 pow(x, n / 2)，将结果平方后再多乘一个 x 即可。
事实上，这就是快速幂的思路，我们用 res 存储结果，在 n 为奇数（用 n & 1 判断）时，额外进行 res *= x。在 n 为偶数时，对 n 减半（用 n >> 1 操作），同时让 x 平方。即可在 log n 时间内得到结果。
细节上，在 n 为负数时，取反然后将 x 取倒数，可以简化代码。注意 n 的负数范围大于正数范围，因此用 long 型转存其绝对值。

时间复杂度：O(logn)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public double myPow(double x, int n) {
        if (Double.compare(x, 1.0) == 0 || n == 0) {
            return 1.0;
        }
        
        return powHelper(x, n);
    }
    
    private double powHelper(double x, int n) {
        if (Double.compare(x, 0.0) == 0) {
            return 0.0;
        }
        long abs = n;
        if (abs < 0) {
            abs = -abs;
            x = 1 / x;
        }
        
        if (Double.compare(x, 1.0) == 0) {
            return 1.0;
        }
        
        double res = 1.0;
        while (abs > 0) {
            if ((abs & 1) == 1) {
                res *= x;
            }
            abs >>= 1;
            x *= x;
        }
        
        return res;
    }
}