[Leetcode] Pow(x, n)

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 };