Implement pow(x, n).

Analysis:  Time Complexity: O(LogN)

 

Iterative code: refer to https://discuss.leetcode.com/topic/40546/iterative-log-n-solution-with-clear-explanation

N = 9 = 2^3 + 2^0 = 1001 in binary. Then:

x^9 = x^(2^3) * x^(2^0)

We can see that every time we encounter a 1 in the binary representation of N, we need to multiply the answer with x^(2^i) where i is the ith bit of the exponent. Thus, we can keep a running total of repeatedly squaring x - (x, x^2, x^4, x^8, etc) and multiply it by the answer when we see a 1.

1 public class Solution { 2     public double MyPow(double x, int n) { 3         double ans = 1; 4         long absN = Math.Abs((long)n); 5         while(absN > 0) { 6             if((absN&1)==1) ans *= x; 7             absN >>= 1; 8             x *= x; 9         }10         return n < 0 ?  1/ans : ans;11     }12 }

 

Recursive code:

1 double pow(double x, int n) { 2     if (n == 0) return 1.0; 3     double half = pow(x, n/2); 4     if (n%2 == 0) 5     { 6         return half*half; 7     } 8     else if (n>0) 9     {10         return half*half*x;11     }12     else13     {14         return half/x*half;15     }16 }

 

 

 

这道题其实细细玩味起来有不少值得注意的地方：位运算的细节。

我第一遍代码里面其实有不妥的地方，比如第4行的1/helper(x, -n)，当n取Integer.MIN_VALUE时，取反结果还是自己

JAVA中整数采用符号二进制补码表示(Two's Complement)，补码对正数没什么好说的，但对负数还是要注意。

比如：

-8　　1000　　　　-4　　1100　　　　0　　0000　　　　4　　0100

-7　　1001　　　　-3　　1101　　　　1　　0001　　　　5　　0101

-6　　1010　　　　-2　　1110　　　　2　　0010　　　　6　　0110

-5　　1011　　　　-1　　1111　　　　3　　0011　　　　7　　0111

一旦某一端overflow, 就会跑到另外一端去wrap up，这就是为什么Integer.MAX_VALUE+1 会是Integer.MIN_VALUE

Integer.MIN_VALUE，即-2147483648，二进制位如下： 

1000 0000 0000 0000 0000 0000 0000 0000 

 

在计算机的运算中，“-”（前缀）运算表示各二制位取反再加1，也就是说 b = -a 在计算机内部是 b = ~a + 1 这样处理的，所以上面的位就变成了： 

 

　　 1000 0000 0000 0000 0000 0000 0000 0000 Integer.MIN_VALUE 

取反 0111 1111 1111 1111 1111 1111 1111 1111 （取反之后变成了Integer.MAX_VALUE） 

加１ 1000 0000 0000 0000 0000 0000 0000 0000 -Integer.MIN_VALUE（与原来的结果一样）

这就导致了我如下的一段code stackoverflow了

1 public class Solution { 2     public double pow(double x, int n) { 3         if (n < 0) return 1/pow(x, Math.abs(n)); 4         if (n == 0) return 1.0; 5         else { 6             double half = pow(x, n/2); 7             if (n % 2 == 0) return half * half; 8             else return half * half * x; 9         }10     }11 }

java.lang.StackOverflowError     last input: 1.00000, -2147483648, 因为-2147483648取反永远是自己，好像0取反永远是自己一样。我第一遍的code也只是侥幸结果对，其实并不好。还是像第二遍code那样写比较好