0

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

确切的值并不重要，只是奇偶校验。我想知道是否有比计算数量和检查更快的方法。我试着想些什么，但什么也找不到。

我希望它如何工作的一个简短示例：

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

3 回答 3

3

使用分而治之的技术：

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 中，Parity 标志可以在减少到 8 位后直接检索。

a ^= (a >> 4);uint8_t LUT[16]停止除法的另一个好处是，因为某些处理器架构可以提供嵌入到 XXM（或 NEON）寄存器中的并行查找表。或者只是 256 项 LUT 的潜在缓存未命中可以简单地超过一轮额外的计算任务。在给定的架构中，最好测量哪种 LUT 大小是最佳的。

最后一个表实际上仅包含 16 位，可以使用以下序列进行模拟：

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

其中上述魔法常数的位N编码Parity(N)的布尔值。

于 2014-02-27T08:26:39.420 回答
1

您可以在一个数组中预先计算一个字节中所有可能的位组合的奇偶校验：

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;
}

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

于 2014-02-27T08:25:41.217 回答
0

相当容易。就像是

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 有，介意）。

如果你喜欢这种东西，你应该看看Henry S. Warren, Jr.的书Hacker's Delight 。

于 2014-02-27T08:20:17.153 回答