[LeetCode] Pow(x,n)

Implement pow(x, n).

思路：像string to integer一样。考虑的细节较多。

　　　1.测试用例要考虑基数和指数都为正数、负数和零的情况。

　　　2.注意0的0次方在数学上没有意义。

　　　3.考虑底数为0且指数为负数的处理方法。可以有返回值、全局变量和异常。这里使用全局变量区别这种情况。

　　　4.用位运算代替乘除和求余优化效率：移位代替除法（n>>1 == n /2);用位与代替求余判定奇偶（if (n& 0x1 == 1) == if(n % 2 == 1))

　　　5.对于n取值INT_MIN = -2147483648时，-n依然是INT_MIN，并不是INT_MAX=2147483647，这时需要格外小心。

　　　时间复杂度O(lgN),空间复杂度O(1)

 1 bool g_invalid_input = false;
 2 double mypow(double x, int n) {
 3     if (fabs(x - 0.0) < 1e-9) {
 4         g_invalid_input = true;
 5         return 0.0;
 6     }
 7 
 8     if (n == 0) return 1;
 9     if (n < 0) {
10         if (n == INT_MIN)
11             return 1.0 / (mypow(x, INT_MAX) * x);
12         else
13             return 1.0 / (mypow(x, -n));
14     }
15 
16     double result = mypow(x, n >> 1);
17     if (n & 0x1 == 1)
18         return result * result * x;
19     else
20         return result * result;
21 }

这是一种STL的写法，这种方法避免了递归调用的栈溢出。来自http://blog.csdn.net/fengbingyang/article/details/12236121

class Solution {  
public:  
    double pow(double x, int n) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        if(n<0)  
        {  
            if(n==INT_MIN)  
                return 1.0 / (pow(x,INT_MAX)*x);  
            else  
                return 1.0 / pow(x,-n);  
        }  
        if(n==0)  
            return 1.0;  
        double ans = 1.0 ;  
        for(;n>0; x *= x, n>>=1)  
        {  
            if(n&1>0)  
                ans *= x;  
        }  
        return ans;  
    }  
};

还有一位大牛的方法，来自http://blog.csdn.net/sunbaigui/article/details/8981241

class Solution {  
//divide-and-conquer  
//classic  
public:  
    double pow(double x, int n) {  
        if (n == 0) return 1.0;  
        // Compute x^{n/2} and store the result into a temporary  
        // variable to avoid unnecessary computing  
        double half = pow(x, n / 2);  
        if (n % 2 == 0)  
            return half * half;  
        else if (n > 0)  
            return half * half * x;  
        else  
            return half * half / x;  
    }  
};

相关题目：《剑指offer》面试题11