50. Pow(x, n)

O(logn)
循环版本

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        res = 1
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>= 1
        return res

class Solution {
public:
    double myPow(double x, int n) {
        long t = labs(n); // 注意n溢出！！
        x = n < 0 ? 1 / x : x;
        double res = 1.0;
        while (t > 0) {
            if (t & 1) {
                res *= x;
            }
            x *= x;
            t >>= 1;
        }
        return res;
    }
};

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

        double res = 1;
        while (n != 0) {
            if (n & 1) {
                res *= x;
            }
            x *= x;
            n /= 2; // 这里一定不要用 n >>= 1因为n可能为INT_MIN
        }
        return res;
    }
};

1.00000
-2147483648
这个测试用例很重要！因为-INT_MIN还是INT_MIN！！所以必须要把n < 0的分支分离出来，否则会造成死循环

class Solution {
public:
    double myPow(double x, int n) {
        return n < 0 ? power(1 / x, labs(n)) : power(x, n);
    }

    double power(double x, long n) {
        if (n == 0) return 1;
        return n & 1 ? x * power(x * x, n / 2) : power(x * x, n / 2);
    }
};

class Solution {
public:
    double myPow(double x, int n) {
        double res = 1.0;
        n < 0 ? power(1 / x, labs(n), res) : power(x, n, res);
        return res;
    }

    void power(double x, long n, double &res) {
        if (n == 0) return;
        if (n & 1) {
            res *= x;
        }
        power(x * x, n / 2, res);
    }
};