Implement pow(x, n).

注意n等于INT_MIN的时候，直接让n = -n会整形溢出.

 

二分法：

1 class Solution { 2 public: 3     double pow(double x, int n) { 4         if (n == 0) return 1; 5         if (n < 0) return 1 / (pow(x, -(n + 1)) * x); 6         double e = pow(x, n / 2); 7         if (n % 2 == 0) { 8             return e * e;; 9         } else {10             return x * e * e;11         }12     }13 };

 

快速幂乘法：

1 class Solution { 2 public: 3     double myPow(double x, int n) { 4         if (n < 0) return 1 / (pow(x, -(n + 1)) * x); 5         double res = 1; 6         while (n > 0) { 7             if (n & 1) res *= x; 8             x *= x; 9             n >>= 1;10         }11         return res;12     }13 };