最快的方法是根据位掩码从值中对所有位进行异或运算？

Question

我有一个有趣的问题,让我寻找一种更有效的做事方式.

假设我们有一个值(二进制)

(VALUE) 10110001
(MASK)  00110010
----------------
(AND)   00110000

现在,我需要能够对(AND)值中设置的值中的任何位进行异或(MASK)(始终从最低位到最高位):

(RESULT) AND1(0) xor AND4(1) xor AND5(1) = 0

现在,在纸面上,这肯定很快,因为我可以看到掩码中设置了哪些位.在我看来,在程序上我需要保持正确移位MASK直到我找到一个设置位,将其与一个单独的值进行异或,并循环直到整个字节完成.

谁能想到更快的方式？我正在寻找使用最少数量的操作和存储值来实现此目的的方法.

Answer 1

如果我理解你,你就有

result = value & mask

并且你想要将1位mask & result一起异或.一系列位的XOR与计数位数和检查该计数是偶数还是奇数相同.如果它是奇数,则异或将为1; 如果均匀,XOR将给出0.

count_bits(mask & result) % 2 != 0

mask & result可简化为简单result.你不需要mask再次使用它.的% 2 != 0可交替写为& 1.

count_bits(result) & 1

至于如何计算位数,Bit Twiddling Hacks网页提供了许多位计数算法.

计数位设置,Brian Kernighan的方式

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

Brian Kernighan的方法经历了与设置位一样多的迭代.因此,如果我们有一个只有高位设置的32位字,那么它只会循环一次.

如果您要使用该实现,则可以进一步优化它.如果你考虑一下,你不需要完整的位数.您只需跟踪他们的奇偶校验.您可以只翻转c每次迭代,而不是计算位数.

unsigned bit_parity(unsigned v) {
  unsigned c;
  for (c = 0; v; c ^= 1) {
    v &= v - 1;
  }
}

^{(感谢Slava提出的建议.)}

Answer 2

如果我正确理解了这个问题,你想要的是从MASK中设置的VALUE中获取每一位,并计算这些位的XOR.

首先,请注意,将值设为0并不会更改结果.因此,要忽略某些位,我们可以将它们视为零.

因此,对VALUE中设置的MASK中的位进行异或运算等效于对VALUE和MASK中的位进行异或运算.

现在注意,如果设置位数是偶数,则结果为0,如果是奇数,则结果为1.

这意味着我们想要计算设置位数.某些体系结构/编译器可以快速计算此值.例如,在GCC上可以获得__builtin_popcount.

所以在GCC上,可以用以下公式计算:

int set_bits = __builtin_popcount(value & mask);

return set_bits % 2;

如果您希望代码是可移植的,那么这是不可行的.但是,此答案中的注释表明某些编译器可以内联std::bitset::count以有效地获得相同的结果.