class Solution {
   // T(n) = T(n/2) + O(1) = O(logn)
    public double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n == -1) return 1 / x;
        double half = myPow(x, n >> 1);
        half *= half;
        // 是否为奇数
        return ((n & 1) == 1) ? (half * x) : half;
    }
}