提示用于查找表中设置位计数算法(Hint for lookup table set bit coun

我在看的设置位计数问题（给出一个二进制数，如何有效地计算有多少位设置）解决方案。

在这里， http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive ，我已经找到了一些方法。

怎么样的查表法？我不明白的二进制表示法/数的特性，使其工作。

static const unsigned char BitsSetTable256[256] = 
{
#   define B2(n) n,     n+1,     n+1,     n+2
#   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
   B6(0), B6(1), B6(1), B6(2)
};

unsigned int v; // count the number of bits set in 32-bit value v
unsigned int c; // c is the total bits set in v

// Option 1:
c = BitsSetTable256[v & 0xff] + 
   BitsSetTable256[(v >> 8) & 0xff] + 
   BitsSetTable256[(v >> 16) & 0xff] + 
   BitsSetTable256[v >> 24]; 

// Option 2:
unsigned char * p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] + 
    BitsSetTable256[p[1]] + 
    BitsSetTable256[p[2]] + 
    BitsSetTable256[p[3]];


// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++)
{
   BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}

特别是，我不明白BitsSetTable256定义在第一。为什么定义这些量B2，B4，...？在我看来，他们不是事后使用。

你可以暗示的二进制表示进一步的文档？

谢谢！

该定义是形成由图案表。他们是递归的宏，B6使用B4和B4使用B2。 B6（0）将获得分成：

B4(0), B4(1), B4(1), B4(2)

B4（0）将获得分成：

0, 1, 1, 2

该序列的第几号将是：

// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11
   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3

正如你所看到的，这些都是表中的每个指标设置的位数。

该算法的其余部分是你打破成8位块，总结每个大块集的比特数，这就是这些线约（您使用选项1或选项2以自己的喜好，而不是两个）：

// Option 1:
c = BitsSetTable256[v & 0xff] + 
    BitsSetTable256[(v >> 8) & 0xff] + 
    BitsSetTable256[(v >> 16) & 0xff] + 
    BitsSetTable256[v >> 24]; 

// Option 2:
unsigned char * p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] + 
    BitsSetTable256[p[1]] + 
    BitsSetTable256[p[2]] + 
    BitsSetTable256[p[3]];

底部的代码：

// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++)
{
   BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}

正在生成BitsSetTable256不同的方式。它生成的表在运行时，而不是在编译时（即宏定义做什么。

PS。如果您的目标足够新（SSE4）86可以使用POPCNT指令。