8

所以我想看看是否有一些偷偷摸摸的位操作系列可以让我计算 uint32 中有多少位是 1（或者更确切地说是 count mod 2）。

“明显”的方式是这样的：

uint32 count_1_bits_mod_2(uint32 word) {
    uint32 i, sum_mod_2;
    for(i = 0; i < 32; i++)
        sum_mod_2 ^= word;
        word >>= 1;

是否有一些“偷偷摸摸”的方法可以在不使用循环的情况下获得正确的 sum_mod_2 ？

4

7 回答 7

7

计算位数最快的方法是使用“幻数”：

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

这将打印 9（指向ideone 的链接）。

对于 32 位数字，这需要 12 次操作——与基于查找的方法所需的数字相同，但您不需要查找表。

于 2012-08-21T12:32:58.830 回答
5

“最佳”方式可能取决于您的代码运行的 CPU 架构。例如，以 Nehalem/Barcelona 开头的 Intel/AMD CPU 支持“popcnt”指令，该指令计算整数寄存器中 1 的位数，因此只需两条指令（popcnt 和按位与 1）即可计算该值你追求。

如果您碰巧使用的是相当新的 GCC 版本（或具有类似支持的其他编译器），您可以使用其 __builtin_popcount() 函数来计算人口计数，使用“-mpopcount”或“-msse4.2”编译指定的标志使用 popcnt 指令。有关更多信息，请参阅此链接。例如：

uint32_t parity = __builtin_popcount(x) & 1;
于 2012-08-21T13:20:41.257 回答
5

最快最快的是使用 CPU popcnt 指令，紧随其后的是 SSSE3 代码。最快的便携是bitslice方法，其次是查找表：http ://www.dalkescientific.com/writings/diary/archive/2011/11/02/faster_popcount_update.html

与所有事情一样，您应该对负载进行基准测试。如果太慢，则进行优化。

对于 AMD Phenom II X2 550，使用 gcc 4.7.1（使用g++ -O3 popcnt.cpp -o popcnt -mpopcnt -msse2）：

Bitslice(7) 1462142 我们；cnt = 32500610
Bitslice(24) 1221985 我们；cnt = 32500610
劳拉杜 2347749 我们；cnt = 32500610
SSE2 8 位 790898 us；cnt = 32500610
SSE2 16 位 825568 我们；cnt = 32500610
SSE2 32 位 864665 我们；cnt = 32500610
16 位 LUT 1236739 我们；cnt = 32500610
8 位 LUT 1951629 我们；cnt = 32500610
gcc popcount 803173 我们；cnt = 32500610
gcc popcountll 7678479 我们；cnt = 32500610
FreeBSD 版本 1 2802681 我们；cnt = 32500610
FreeBSD 版本 2 2167031 我们；cnt = 32500610
维基百科#2 4927947 我们；cnt = 32500610
维基百科#3 4212143 我们；cnt = 32500610
HAKMEM 169/X11 3559245 我们；cnt = 32500610
天真 16182699 我们；cnt = 32500610
Wegner/Kernigan 12115119 我们；cnt = 32500610
安德森 61045764 我们；cnt = 32500610
8x 移位并添加 6712049 us；cnt = 32500610
32x班次加6662200 us；cnt = 32500610

对于带有 gcc 4.7.1 的 Intel Core2 Duo E8400（g++ -O3 popcnt.cpp -o popcnt -mssse3此-mpopcntCPU 不支持）

Bitslice(7) 1353007 我们；cnt = 32500610
Bitslice(24) 953044 我们；cnt = 32500610
劳拉杜 534697 我们；cnt = 32500610
SSE2 8 位 458277 我们；cnt = 32500610
SSE2 16 位 555278 我们；cnt = 32500610
SSE2 32 位 634897 我们；cnt = 32500610
SSSE3 414542 我们；cnt = 32500610
16 位 LUT 1208412 我们；cnt = 32500610
8 位 LUT 1400175 我们；cnt = 32500610
gcc popcount 5428396 我们；cnt = 32500610
gcc popcountll 2743358 我们；cnt = 32500610
FreeBSD 版本 1 3025944 我们；cnt = 32500610
FreeBSD 版本 2 2313264 我们；cnt = 32500610
维基百科#2 1570519 我们；cnt = 32500610
维基百科#3 1051828 我们；cnt = 32500610
HAKMEM 169/X11 3982779 我们；cnt = 32500610
天真 20951420 我们；cnt = 32500610
Wegner/Kernigan 13665630 我们；cnt = 32500610
安德森 6771549 我们；cnt = 32500610
8x 移位加 14917323 us；cnt = 32500610
32x 移位加 14494482 us；cnt = 32500610

Bitslice 方法是一种并行机制，一次计算多个（7 或 24 个）机器字，因此它对通用函数具有边际可用性。在http://dalkescientific.com/writings/diary/popcnt.cpp之后：

static inline int popcount_fbsd2(unsigned *buf, int n)
{
  int cnt=0;
  do {
    unsigned v = *buf++;
    v -= ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    v = (v + (v >> 4)) & 0x0F0F0F0F;
    v = (v * 0x01010101) >> 24;
    cnt += v;
  } while(--n);
  return cnt;
}

static inline int merging2(const unsigned *data) 
{
        unsigned count1,count2,half1,half2;
        count1=data[0];
        count2=data[1];
        half1=data[2]&0x55555555;
        half2=(data[2]>>1)&0x55555555;
        count1 = count1 - ((count1 >> 1) & 0x55555555);
        count2 = count2 - ((count2 >> 1) & 0x55555555);
        count1+=half1;
        count2+=half2;
        count1 = (count1 & 0x33333333) + ((count1 >> 2) & 0x33333333);
        count2 = (count2 & 0x33333333) + ((count2 >> 2) & 0x33333333);
        count1+=count2;
        count1 = (count1&0x0F0F0F0F)+ ((count1 >> 4) & 0x0F0F0F0F);
        count1 = count1  + (count1 >> 8);
        count1 = count1 + (count1 >> 16);

        return count1 & 0x000000FF;
}

static inline int merging3(const unsigned *data) 
{
        unsigned count1,count2,half1,half2,acc=0;
        int i;

        for(i=0;i<24;i+=3)
        {
                count1=data[i];
                count2=data[i+1];
                //w = data[i+2];
                half1=data[i+2]&0x55555555;
                half2=(data[i+2]>>1)&0x55555555;
                count1 = count1 - ((count1 >> 1) & 0x55555555);
                count2 = count2 - ((count2 >> 1) & 0x55555555);
                count1+=half1;
                count2+=half2;
                count1 = (count1 & 0x33333333) + ((count1 >> 2) & 0x33333333);
                count1 += (count2 & 0x33333333) + ((count2 >> 2) & 0x33333333);
                acc += (count1 & 0x0F0F0F0F)+ ((count1>>4) &0x0F0F0F0F);
        }
        acc = (acc & 0x00FF00FF)+ ((acc>>8)&0x00FF00FF);
        acc = acc + (acc >> 16);
        return acc & 0x00000FFFF;
}

/* count 24 words at a time, then 3 at a time, then 1 at a time */
static inline int popcount_24words(unsigned *buf, int n) {
  int cnt=0, i;

  for (i=0; i<n-n%24; i+=24) {
    cnt += merging3(buf+i);
  }
  for (;i<n-n%3; i+=3) {
    cnt += merging2(buf+i);
  }
  cnt += popcount_fbsd2(buf+i, n-i);
  return cnt;
}
于 2012-08-21T13:26:00.437 回答
2 
count = 0;
while (word != 0) {
  word = word & (word-1);
  count++;
}

该声明

word = word & (word-1);

清除字中的最低 1 位。最终，您会用完 1 位。

于 2012-08-21T12:34:39.600 回答
1

我认为这很容易理解，而且效率很高。

x = some number;
x ^= (x >> 1); // parity of every bit pair now in bits 0, 2, 4, ...
x ^= (x >> 2); // parity of every 4 bits now in bits 0, 4, 8, ...
x ^= (x >> 4); // ...etc
x ^= (x >> 8);
x ^= (x >> 16); // parity of all 32 bits now in bit 0
parity = x & 1;
于 2012-08-21T13:40:53.737 回答
0

预先计算所有结果并进行简单的数组查找。对于简单的“偶数或奇数”布尔结果，您可以创建一个位数组。

于 2012-08-21T12:32:43.510 回答
0 
           cnt = 0;
           while (word != 0) {
           word = word & (word-1);
           cnt++;

这可以删除 1 位以获取更多详细信息，请访问http://pgrtutorials.blogspot.in/p/bit-manipulation.html

于 2012-08-21T14:42:39.750 回答