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

问题:

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

约束: x <= 2^800

SB青年版

不用说,递归肯定是最sb的版本:

1
2
3
4
5
6
7
8
9
10
function power2sb(x,n) {
n = n || 0;
if(x === 1) {
return n;
}
if( x < 1) {
return false;
}
return power2sb(x / 2, n + 1);
}

结果测试:

1
2
3
4
5
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青年版

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

1
2
3
4
5
6
7
8
9
10
11
function power2lb(x) {
var n = 0;
while( x >= 1){
if(x === 1){
return n;
}
x = x / 2;
n++;
}
return false;
}

结果测试:

1
2
3
4
5
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

普通青年版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
}

文艺青年版

位运算,无循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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,结果一样
*/
}

结果测试:

1
2
3
4
5
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

字符串直接匹配解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
统计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能够支持大数的计算。

最终满分通过答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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

便于鸣谢,捐赠请留下网名~