2

在此链接中查看设置位计数的方法，我发现了以下方法

作者说：

对 32 位整数 v 中的位数进行计数的最佳方法如下：

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

最好的位计数方法只需要 12 次操作，这与查找表方法相同，但避免了表的内存和潜在的缓存未命中。它是上述纯并行方法和使用乘法的早期方法（在使用 64 位指令计数位的部分）之间的混合，尽管它不使用 64 位指令。字节中设置的位计数是并行完成的，并且通过乘以 0x1010101 并右移 24 位来计算字节中设置的位的总和。

任何解释这种方法如何计算设置位？

4

1 回答 1

4

它之所以有效，是因为您可以通过分成两半来计算设置位的总数，计算两半中设置位的数量，然后将它们相加。也称为Divide and Conquer范式。让我们详细了解一下。。

v = v - ((v >> 1) & 0x55555555);

两位中的位数可以是0b00，0b01或0b10。让我们尝试在 2 位上解决这个问题..

 ---------------------------------------------
 |   v    |   (v >> 1) & 0b1010   |   v - x   |
 ---------------------------------------------
   0b00           0b00               0b00   
   0b01           0b00               0b01     
   0b10           0b01               0b01
   0b11           0b01               0b10

这是所需要的，最后一列显示每两位对中设置位的计数。如果这两位数字是>= 2 (0b10)然后and产生0b01，否则它产生0b00。

v = (v & 0x33333333) + ((v >> 2) & 0x33333333);

这句话应该很容易理解。在第一次操作之后，我们得到了每两位中设置位的计数，现在我们将每 4 位中的计数相加。

v & 0b11001100         //masks out even two bits
(v >> 2) & 0b11001100  // masks out odd two bits

然后我们总结上面的结果，给出 4 位中设置位的总数。最后一条语句是最棘手的。

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

让我们进一步打破它..

v + (v >> 4)

它与第二条语句类似，我们改为以 4 个为一组来计算设置位。我们知道，由于我们之前的操作，每个半字节都有设置位的计数。让我们看一个例子，假设我们有 byte 0b01000010。这意味着第一个半字节设置了 4 位，第二个半字节设置了 2 位。现在我们将这些半字节加在一起。

0b01000010 + 0b01000000

它在第一个半字节中为我们提供了一个字节中设置位的计数，0b01100010因此我们屏蔽了该数字中所有字节的最后四个字节（丢弃它们）。

0b01100010 & 0xF0 = 0b01100000

现在每个字节都有设置位的计数。我们需要把它们加在一起。诀窍是将结果乘以0b10101010具有有趣属性的结果。如果我们的数字有四个字节 ，A B C D它将产生一个包含这些字节的新数字A+B+C+D B+C+D C+D D。一个 4 字节的数字最多可以设置 32 位，可以表示为0b00100000.

我们现在需要的是第一个字节，它具有所有字节中所有设置位的总和，我们得到它 >> 24。该算法是为32 bit单词设计的，但可以很容易地针对64 bit单词进行修改。

于 2013-04-12T10:12:50.893 回答