快速了解BitVector的计算奇偶校验

Question

我在c中使用bitVectors。我的BitVectors是unsigned long long的。对于大量向量，我需要知道奇偶校验，即1的位数是偶数还是奇数。

确切的值并不重要，只是奇偶校验。我想知道是否有什么东西比计算和检查的数量更快。我试图想到一些东西，但找不到任何东西。

如何将此工作的简短示例：

void checkIntersection(unsigned long long int setA, unsigned long long int setB){
    if(isEven(setA & setB)){
        //do something
    }
}

.

Answer 1

分配和征服技术：

uint64_t a = value;
a ^= (a >> 32);            // Fold the 32 MSB over the 32 LSB
a ^= (a >> 16);            // reducing the problem by 50%
a ^= (a >> 8);             // <-- this can be a good break even point
..
return lookup_table[a & 0xff];  // 16 or 256 entries are typically good
..

.

折叠程序可以应用直到结束：

a ^= (a >> 1);
return a & 1;

.

在IA中，可以在减少到8位后直接检索奇偶校验标志。

a ^= (a >> 4);使另一个好点停止分割，因为某些处理器架构可以提供嵌入到XXM（或霓虹灯）寄存器中的并行查找表生成码码。或者只是256-条目LUT的潜在高速缓存未命中可以简单地超重一个额外的计算任务。它自然最佳地测量给定架构中的最佳尺寸是最佳的。

这个最后一个表实际上包括16位，可以用序列仿真：

return ((TRUTH_TABLE_FOR_PARITY) >> (a & 15)) & 1;

.

在上面的魔法常量的位 n 编码奇偶校验（n）的布尔值。

Answer 2

您可以在阵列中重新编译一个字节：

的所有可能组合的奇偶校验

bool pre[256] = { 0, 1, 1, 0, 1, ....}

.

当您需要找出刚执行的较大数组的奇偶校验时：

bool parity (long long unsigned x)
{   
    bool parity = 0;
    while(x)
    {   
        parity ^= pre[x&0xff];
        x>>=8;
    }
    return parity;
}

.

免责声明：我没有测试代码，这只是一个想法。

Answer 3

很容易。像

这样的东西

unsigned population(unsigned long long x) {
  x = ((x >> 1) & 0x5555555555555555) + (x & 0x5555555555555555);
  x = ((x >> 2) & 0x3333333333333333) + (x & 0x3333333333333333);
  x = ((x >> 4) & 0x0f0f0f0f0f0f0f0f) + (x & 0x0f0f0f0f0f0f0f0f);
  x = (x >> 8) + x;  // Don't need to mask, because 64 < 0xff
  x = (x >> 16) + x;
  x = (x >> 32) + x;
  return x & 0xff;
}

.

应该工作。此外，一些CPU有人口计数指令（我不认为X86确实，介意）。

如果你喜欢这种东西，你应该看看黑客的愉悦 by henry s. warren，Jr。