在 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:

You can use a strategy from this collection of 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屋！