Recursive

50 Pow(x, n)

这个题一开始我写成这样：

var myPow = function(x, n) {
  if (n < 0){
    x = 1 / x
    n = -n
  }
  if (n === 1) return x;
  return x * myPow(x, n-1)
};

看着好像没什么问题，但是当n很大的时候，比如1万多的时候，这样写就会报错：

Line 6: RangeError: Maximum call stack size exceeded

很明显，堆栈调用太深了。然后老师说要用分治来做，我写成这样就通过了：

// 64ms   84.16%   33.8mb   34.15%
var myPow = function(x, n) {
    if (n === 0) return 1
  if (n < 0){
    x = 1 / x
    n = -n
  }
  if (n === 1) return x;
  if (n % 2 === 0) {
    let p = myPow(x, n/2)
    return p * p
  }else {
    let p = myPow(x, Math.floor(n/2))
    return p * p * x
  }
};

console.log(myPow(1.00001, 123456))  // 3.43684

大概思路就是：n个相乘的x分开两半来算，因为两半的结果是一样的，因此就只需要算一半的就可以了，以此类推，一半一半的分下去。

值得一提的是，老师给出的是python代码，我也按照他那样写两个return试着提交了下，内存消耗没有变，但是速度变成了80ms，击败了17.64%的用户。orz

if (n % 2 === 0) {
  return myPow(x*x, n/2)
}else {
  return myPow(x*x, Math.floor(n/2)) * x
}

非递归的做法

老师给了一个用位运算的非递归做法，然后给出了python代码。我用js写了一下：

var myPow = function(x, n){
  if (n === 0) return 1;
  if (n < 0){
    x = 1 / x
    n = -n;
  }
  let pow = 1
  while (n>0){
    if (n & 1){
      pow *= x
    }
    x *= x
    n >>= 1
  }
  return pow
}

看起来没什么问题，但是最后卡在一个测试用例上：

myPow(2.00000, -2147483648)

期望输出是0，但是我这里会输出1。打了下日志发现，while循环走了一次就出来了。原因是，题目说：

n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]

-2147483648刚好就是下限−2^31，这里就涉及一些补码反码的知识了，看了一篇博客，感觉讲得还不错。

首先，n = -n;的时候，虽然-2147483648变成了2147483648，但是移位的时候就会发现，2147483648 >> 1之后变成了-1073741824。然后while判断为false没有没有继续执行了。

那么为什么2147483648 >> 1 === -1073741824呢？

ECMAScript 整数有两种类型，即有符号整数（允许用正数和负数）和无符号整数（只允许用正数）。在 ECMAScript 中，所有整数字面量默认都是有符号整数，这意味着什么呢？

有符号整数使用 31 位表示整数的数值，用第 32 位表示整数的符号，0 表示正数，1 表示负数。数值范围从 -2147483648 到 2147483647。

那对-2147483648取负值时，按理论应该是2147483648，但超过int能表达的最大正值，相当于2147283647+1=0111...1111+0000...0001=1000...0000=-2147483648（按补码理解）。也就是说对-2147483648取负仍然是-2147483648。

主要是因为2147483648，但超过int能表达的最大正值，用二进制表示的话就依然是1000...0000，那么移位运算的时候也会依照这个二进制数来计算，而负数的移位规则首先是保持符号不变，所以，1000...0000>>1就变成1100....0000，这个数就是-2^30=-1073741824 由此产生了bug。

那怎么办呢。我试着查了下，没什么好的结果。我就让在while里再判断一次负数好了，结果倒是通过了测试。但是和预想的不一样啊，这样写也没有更快。

完整代码：

// 72 ms 48.43% 34.3 MB 5.69%
var myPow = function(x, n){
  if (n === 0) return 1;
  if (n < 0){
    x = 1 / x
    n = -n;
  }
  let pow = 1
  while (n>0){
    if (n & 1){
      pow *= x
    }
    x *= x
    n >>= 1
    if (n < 0){
      n = -n
    }
  }
  return pow
}

ps：老师写的python的代码并不会出现这个问题，python大法好啊