Leetcode: Pow(x, n) and Summary: 负数补码总结

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     else
13     {
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那样写比较好