剑指 Offer 16. 数值的整数次方

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

示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000

思路参考题解：https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-shi-ti-16-shu-zhi-de-zheng-shu-ci-fang-kuai-s/

思路是使用快速幂。简单来说就是将指数改写为二进制。然后通过循环复制x *= x，在指数二进制为1的位置，将结果乘上x即res *= x。详细的描述可以看参考题解。

对于指数为负数的处理，如果指数为负数，x = 1 / x并将指数再设置为正数即可。比如2−12^{-1}可以转化为(12)1(\frac12)^1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public double myPow(double x, int n) {
        if (x == 0 || x == 1) return x;
        long nn = n;
        if (n < 0) {
            x = 1 / x;
            nn = -nn;
        }
        double res = 1.0;
        while (nn > 0) {
            if ((nn & 1) == 1) {
                res *= x;
            }
            x *= x;
            nn >>= 1;
        }
        return res;
    }
}