提示为查找表设置位计数算法 [英] Hint for lookup table set bit count algorithm

问题描述

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

I am looking at solution for the set bit count problem (given a binary number, how to efficiently count how many bits are set).

下面， http://graphics.stanford.edu/~seander/bithacks。 HTML＃CountBitsSetNaive ，我已经找到了一些方法。

Here, http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive, I have found some methods.

有关查表法是什么？我不明白的二进制重新presentation /多项特性，使其工作。

What about the lookup table method? I dont understand what properties of binary representation / number make it work.

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，...？在我看来，他们是不是以后使用。

In particular, I dont understand the BitsSetTable256 definition at first. Why define these quantities B2, B4,... ? it seems to me that they are not used afterwards.

你能暗示二进制重新presentation进一步DOC？

Could you hint at further doc on binary representation?

谢谢！

推荐答案

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

The definitions are to form the table by patterns. They are recursive macros, B6 uses B4 and B4 uses B2. B6(0) will get broken into:

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

B4（0），将获得分成：

B4(0) will get broken into:

0, 1, 1, 2

序列的第几号将是：

The first few numbers of the sequence will be:

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

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

As you can see, these are the number of bits set for each index in the table.

该算法的其余部分是你正在打破数为8位数据块，总结在每个块设置的位数，这就是这些线约（您使用选项1或选项2你的喜好，不能同时）：

The rest of the algorithm is that you are breaking the number into 8-bit chunks and summing the number of bits set in each chunk, that's what these lines are about (you use either option 1 or option 2 at your liking, not both):

// 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]];

在code底部：

The code at the bottom:

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

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

Is a different way of generating the BitsSetTable256. It generates the table at runtime instead of at compile-time (which is what the macro definition does.

P.S。如果你的目标足够新（SSE4）86可以使用POPCNT指令。

P.S. If you're targeting recent enough (SSE4) x86 you can use POPCNT instruction.

这篇关于提示为查找表设置位计数算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！