知道位矢量计算奇偶校验的快速方法

我正在使用位矢量C.我的位矢量是unsigned long long's。对于大量的向量，我需要知道奇偶校验位，即1的位数是偶数还是奇数。知道位矢量计算奇偶校验的快速方法

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

的我多么希望这个工作很短的例子：

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

来源

2014-02-27 nvcleemp

搜索“bit twiddling hacks”.... –

随着分而治之技术：

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（或NEON）寄存器中的并行查找表uint8_t LUT[16]。或者简单地说，256条LUT的潜在缓存未命中可以简单地超过一轮额外的计算任务。测量给定体系结构中哪种LUT尺寸是最优的自然是最好的选择。

这最后表实际上只有16位组成，且可以与序列来模拟：上述

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

其中位n中的魔术恒定的编码奇偶校验（N）的布尔值。

来源

2014-02-27 08:26:39

很容易。像

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的确如此）。

如果你喜欢这种东西，你应该亨利·沃伦检查出书黑客的喜悦，小

来源

2014-02-27 08:20:17 alastair

OP特别想要比计算位数更快的东西。 –

公平点。我想我误解了这个问题。 – alastair

你可以在一个阵列预先计算在一个比特的所有可能的组合校验字节：

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-27 08:25:41 titus

知道位矢量计算奇偶校验的快速方法

回答

相关问题