JS 判断一个数是否为 2 的 N 次幂

问题：

判断一个数(x)是否为 2 的 N 次幂，如果是，返回是 2^n 中的 n，如果不是返回 false

约束： x <= 2^800

SB 青年版

不用说，递归肯定是最 sb 的版本：

function power2sb(x, n) {
  n = n || 0;
  if (x === 1) {
    return n;
  }
  if (x < 1) {
    return false;
  }
  return power2sb(x / 2, n + 1);
}

结果测试：

console.log(power2sb(4)); // 2
console.log(power2sb(5)); // false
console.log(power2sb(65536)); // 16
console.log(power2sb(Math.pow(2, 52) + 1)); // false
console.log(power2sb(Math.pow(2, 53) + 1)); // false 实际结果：53

LowB 青年版

低级循环版，与上一个版本半斤八两。

function power2lb(x) {
  var n = 0;
  while (x >= 1) {
    if (x === 1) {
      return n;
    }
    x = x / 2;
    n++;
  }
  return false;
}

结果测试：

console.log(power2lb(4)); // 2
console.log(power2lb(5)); // false
console.log(power2lb(65536)); // 16
console.log(power2lb(Math.pow(2, 52) + 1)); // false
console.log(power2lb(Math.pow(2, 53) + 1)); // false 实际结果：53

普通青年版

function power2nm(x) {
  // 奇数肯定不是2的N次幂
  if (x % 2 === 1) {
    return false;
  }
  // 总结规律
  // 2^2=4
  // 2^3=8
  // 2^4=16
  // 2^5=32
  // 2^6=64
  // 2^7=128
  // 2^8=256
  // 2^9=512
  // 所以，个位不可能为 0
  if (x % 10 === 0) {
    return false;
  }
  var n = 0;
  while (x >= 1) {
    if (x === 1) {
      return n;
    }
    x = x / 2;
    n++;
  }
  return false;
}

文艺青年版

位运算，无循环。

function power2fs(x) {
  // 一句话版本
  return (x & (x - 1)) === 0 ? (x - 1).toString(2).length : false;
  /*
    解释：
    1. (x & ( x - 1)) === 0
    先来寻找一下规律：
    2^2=4 对应二进制为
    100
    2^3=8
    1000
    2^4=16
    10000

    所以，
    2^N=1+N个0
    2^N-1=N个1

     100
    & 11
    ----
     000
    4 & 3 = 0

     1000
    & 111
    -----
     0000
    8 & 7 = 0

    2. (x-1).toString(2).length
    (8-1).toString(2) // 111, length: 3
    (16-1).toString(2) // 1111, length: 4
    或者还可以写成 x.toString(2).length - 1，结果一样
   */
}

结果测试：

console.log(power2fs(4)); // 2
console.log(power2fs(5)); // false
console.log(power2fs(65536)); // 16
console.log(power2fs(Math.pow(2, 52) + 1)); // false
console.log(power2fs(Math.pow(2, 53) + 1)); // false 实际结果：53

分割线

上面 4 个版本都有一个共同的缺点，那就是只能计算到 2^52 次方。

JavaScript 中双精度类型最大 53 位，即 2^53-1 = 9007199254740991。

NB 青年版

> 2016年7月6日更新


这题的原题来自： <https://www.hackerrank.com/challenges/two-two>


### 字符串直接匹配解题思路

```
统计2幂个数/字符串/ /统计2幂个数/字符串
1	1			0	01
1	2			0	02
1	4			0	04
1	8			0	08
2	16			0	016
2	32			0	032
2	64			0	064
4	128			0	0128
2	256			0	0256
3	512			0	0512
4	1024		0	01024
4	2048		0	02048
2	4096		0	04096
4	8192		0	08192
4	16384		0	016384
4	32768		0	032768
1	65536		0	065536
4	131072		0	0131072
6	262144		0	0262144
6	524288		0	0524288
4	1048576		0	01048576
4	2097152		0	02097152
5	4194304		0	4194304
```

通过该方式，先通过计算，得出一张类似上述的对照表。
通过查表法去快速推算结果。虽然这样能够通过系统评分的判断，但是实际上效率非常低下，这张对照表的产生花费大量的计算。

### 大数计算

先把思路做一下调整，之前在做这个题的时候，总是在做字符串的遍历，查询，效率非常低下。
而实际上2^0到2^800一共只有801个组合，只需要将这801个出现的次数匹配出来，就是结果。

这里用到了一个库：

https://github.com/peterolson/BigInteger.js

让JavaScript能够支持大数的计算。

最终满分通过答案：

```js
var bigInt;//引入代码省略

function processData(input) {
  var data = input.split("\n");
  for( var i=0; i < data[0]; i++) {
    compute(data[i+1]);
  }
}

function compute(word) {
  var count = 0;
  var base = new bigInt(2);

  for( var i=0; i <= 800; i++ ) {
    var s = base.pow(i).toString(10);
    var idx = 0, nextIdx = 0;
    do {
      idx = word.indexOf(s, nextIdx);
      if( idx != -1) {
        count++;
      }
      nextIdx = idx +1;
    } while( idx != -1);
  }

  console.log(count);
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});
```

![150](http://w3log.qiniudn.com/blog/two-two.png)