[leetcode-50-Pow(x, n)]

Implement pow(x, n).

开始的时候思路很朴素，隐约觉得不太对劲。。果然，超时了。

double myPow(double x, int n)
    {
        if (x == 0.0) return 0;
        if (n == 1) return x;

        double result = 1.0;
        for (int i = 0; i < abs(n);i++)
        {
            result *= x;
        }
        if (n>0)return result;
        return 1.0/result;
    }

然后，再仔细琢磨，发现可以缩短时间，缩短到 O(lgn)的复杂度。

比如8个2相乘的话，可以表示为4的平方，4又可以表示为2的平方，只需三次即可算出。

double myPow2(double x, int n)
    {
        if (x == 0.0) return 0;
        if (n == 1) return x;

        double result = 1.0;
        unsigned long long p = n;
        if (n < 0) { p = -n; x = 1 / x; }
        while (p)
        {
            if (p & 1) result *= x;//奇数的情况
            x *= x;
            p >>= 1;
        }
     
        return result;    
    }

参考：

https://discuss.leetcode.com/topic/17832/non-recursive-c-log-n-solution/2