数值的整数次方

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

分析

利用快速幂解题。

例子：3^6 = 33333*3 = (3^2)^(6/2) = 9^3 = 9 * (9^2)^(2/2)

每次二分，底数平方，指数除以2，如果指数是奇数，就需要多乘一次底数。

如果指数是负数，可将 x^n 转化成 (1/x)^(-n)，注意 n=−2147483648 时 -n=2147483648，int的范围是[−2147483648,2147483647]，所以存这个变量要用long类型。

时间复杂度O(\(log_2N\)) 空间复杂度O(1)

class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        long m = n;
        if (m < 0) {
            x = 1/x;
            m = -m;
        }

        while (m>0) {
            if ((m&1)==1) res *= x;
            x *= x;
            m = m>>1;
        }
        return res;
    }
}