位操作：如何检测一个字节中至少有5个位被设为1？

Question

什么是检查二进制数中是否设置了最小数量位的最佳方法？

例如，我需要查看此序列中是否至少设置了5个1：

101100010

我一直在研究使用位掩码等技术，但对如何完成此操作感到更加困惑而不是自信。

任何帮助都将不胜感激。

- backdesk

---

如果位(bit)有意义，我会构建一个对象，该对象接受字符串"101100010"，然后提供方法来指示有意义的状态。 - Liviu T.

顺便提一下，这被称为“汉明重量”。这可能有助于您找到一个实现。 - J. Holmes

我会留给你这个链接：http://graphics.stanford.edu/~seander/bithacks.html - Wayne

Answer 1

从http://blog.faultylabs.com/2011.php?p=jsbitfun。

/*
 popCnt(n)
 Returns the bit population count of n (that is: how many bits in n are set to 1)
 n must be an unsigned integer in the range [0..(2^32)-1]
 This lookup-table-free method is from Kernighan & Ritchie's "The C Programming Language"
 Exercise 2.9 (on page 62 of my copy). Not sure whether they (K&R) are the inventors.
*/
function popCnt(n) {
    n >>>= 0 /* force uint32 */
    for(var popcnt = 0; n; n &= n - 1) {
        popcnt++
    }
    return popcnt
}

请参见http://en.wikipedia.org/wiki/Hamming_weight了解其他算法的详细信息。

- J. Holmes

Answer 2

如果你想学习如何使用位运算，可以尝试玩玩位掩码。

如果你只需要一个非常简单的解决方案，只需将整数转换为其二进制值的字符串表示形式并计算1的数量即可：

var i = 0x1 +0x4 + 0x8 +0x80; // 10001101 in binary
var numberOf1s = i.toString(2).split('1').length-1; // 4

所以总的来说，您只需要一行代码就可以完成它：

if(<insert your var>.toString(2).split('1').length-1 >=5) {
  //At least 5 bits are set
}

- Martin Jespersen

---

@pimvdb：我同意，这样会更简单，但既然楼主要求“至少5个”，我就按照那种方式编码了。 - Martin Jespersen

Answer 3

首先使用位掩码来实现，特别是如果正在尝试学习。当将其视为一系列位时，这是最逻辑简单的方法。（有许多聪明的技巧可以完成，但首先是最重要的，对于像JS这样具有大量引擎的语言，实现可能会很聪明-不太聪明。）

要测试位b是否设置，当input&(1<<b)非0时，它被设置，当然1<<b是00000001(0x01)，00000010(0x02)，00000100(0x04)，00001000(0x08)等等，当b是0,1,2,3等等。(请注意1是00000001和<<如何将模式向左移动b位)。

因此，对于每个0 <= b < 8，请查看是否设置了该位。如果是，则将计数器加1。

现在我们知道第一个八位字节中有多少位被设置。

还要注意的是，我们关心的 b 值只有一小组有限的值。因此，我们可以消除循环并在每个循环迭代中了解每个 1 << b 。（某些浏览器（如Firefox）可以在单个表达式时非常快地处理一系列按位运算操作。）

编码愉快！

---

出于兴趣，我决定创建一个快速的性能测试案例，测试popCnt（和strCount），如其他答案所示，并且专门使用数学运算而不是过度聪明的fastCount8位计数器，以及如上所述的simpleCount8。

尽管fastCount8（和simpleCount8）都限于单个八位字节（第一个字节），但在这种特定情况下，fastCount8在某些浏览器中要快得多。 （在FF8中，它比预期的快得多，但在IE9中仅略快，在Chrome 16中则较慢。）如预期的那样，strCount比popCnt慢得多，而simpleCount8也不好多少。

这里是jsperf test和fastCount8：

function fastCount8(n) {
    // >> has higher precedence than &
    return (n >> 0 & 1)
      + (n >> 1 & 1)
      + (n >> 2 & 1)
      + (n >> 3 & 1)
      + (n >> 4 & 1)
      + (n >> 5 & 1)
      + (n >> 6 & 1)
      + (n >> 7 & 1)
}

---

更新了lookup8、lookupN（以及一些变体）、fastCount8N和fastCount8N2的性能测试用例。结果非常惊人：FF8进行了一些绝对惊人的数学优化，而其他浏览器（我测试过）甚至无法接近给定表达式的速度。此外，其他结果可能会有令人惊讶的地方，并展示了不同浏览器如何优化不同的内容...

总的来说，lookup8和lookupN2b在各个浏览器中看起来最为一致... 至少在应用给定范围的n时是这样。

- user166390

---

如果性能是您的主要关注点，并且只担心8位，那么我会选择使用查找表。 - J. Holmes

@32bitkid 已为您更新。这实际上比FF8中的fastCount8慢。（FF执行一些非常惊人的数学优化，这些结果似乎非常普遍。） - user166390

嗯，重复运行显示不同的结果，也许需要更多的测试人员 :p - user166390