C:计算正位的偷偷摸摸的方法？

Question

所以我想看看是否有一些偷偷摸摸的位操作系列可以让我计算 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？

Answer 1

计算比特的最快方法is by using "magic numbers" :

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(link 到 ideone)。

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