Pow(x, n)

直接乘的话会超时O(n)。利用二分法降为O(lgn)。
 1 public class Solution {
 2     public double pow(double x, int n) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         if(n == 0)
 6             return 1;
 7         if(n == 1)
 8             return x;
 9             
10         boolean negative = false;
11         if(n < 0)
12             negative = true;
13         n = Math.abs(n);
14         double result = 0;
15         result = pow(x, n>>1);
16         result *= result;
17         if((n&1) > 0)
18             result *= x;
19         return negative?1/result:result;
20         
21     }
22 }