有效地计算JavaScript中整数的位数 [英] Efficiently count the number of bits in an integer in JavaScript
问题描述
假设我有一个整数I,并希望以二进制形式得到1的计数。
Let's say I have an integer I and want to get the count of 1s in its binary form.
我目前正在使用以下代码。
I am currently using the following code.
Number(i.toString(2).split("").sort().join("")).toString().length;
有更快的方法吗?我正在考虑使用按位运算符。有什么想法?
Is there a faster way to do this? I am thinking about using bitwise operators. Any thoughts?
注意: i
在32位限制范围内。
NOTE: i
is within the 32-bit limitation.
推荐答案
您可以使用 Bit Twiddling Hacks :
function bitCount (n) {
n = n - ((n >> 1) & 0x55555555)
n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
}
console.log(bitCount(0xFF)) //=> 8
请注意,上述策略仅适用于32位整数(JavaScript中按位运算符的限制)。
Note that the above strategy only works for 32-bit integers (a limitation of bitwise operators in JavaScript).
对于较大整数的更通用方法将涉及单独计算32位块(感谢 harold 的灵感来源:
A more general approach for larger integers would involve counting 32-bit chunks individually (thanks to harold for the inspiration):
function bitCount (n) {
var bits = 0
while (n !== 0) {
bits += bitCount32(n | 0)
n /= 0x100000000
}
return bits
}
function bitCount32 (n) {
n = n - ((n >> 1) & 0x55555555)
n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
}
console.log(bitCount(Math.pow(2, 53) - 1)) //=> 53
你也可以使用正则表达式:
You could also use a regular expression:
function bitCount (n) {
return n.toString(2).match(/1/g).length
}
console.log(bitCount(0xFF)) //=> 8
这篇关于有效地计算JavaScript中整数的位数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!