基于位掩码从值中异或所有位的最快方法？

Question

我遇到了一个有趣的问题，我正在寻找一种更有效的做事方式。

假设我们有一个值（二进制）

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

现在，我需要能够对在 (MASK) 值中设置的 (AND) 值的任何位进行异或（总是从最低位到最高位）：

(RESULT) AND<sub>1</sub>(0) xor AND<sub>4</sub>(1) xor AND<sub>5</sub>(1) = 0

现在，从理论上讲，这肯定很快，因为我可以看到掩码中设置了哪些位。在我看来，以编程方式我需要继续右移 MASK 直到找到一个设置位，将它与一个单独的值进行异或，然后循环直到整个字节完成。

谁能想到更快的方法？我正在寻找用最少的操作和存储的值来做到这一点的方法。

Answer 1

利用与 0 的 XOR 不会改变任何东西，可以应用掩码然后无条件地将所有位异或在一起，这可以通过并行前缀方式完成。所以像这样（未测试）：

x = m & v;
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
result = x & 1

您可以根据需要使用更多（或更少）步骤，这是针对 32 位的。

Answer 2

如果我没理解错的话，你有

result = value & mask

并且您想将 mask & result 的 1 位异或在一起。一系列位的异或与计算位数并检查该计数是偶数还是奇数相同。如果是奇数，则异或为 1；如果偶数，XOR 将给出 0.

count_bits(mask & result) % 2 != 0

mask & result可以简化为result。您不需要再次使用 mask 与它。 % 2 != 0 也可以写成 & 1.

count_bits(result) & 1

至于如何计算位，Bit Twiddling Hacks web page gives a number of bit counting algorithms。

Counting bits set, Brian Kernighan's way
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's method goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop.

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

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

^{（感谢Slava的建议。）}

Answer 3

如果我对这个问题的理解正确，你想要的是从 MASK 中设置的 VALUE 中获取每一位，并计算这些位的异或。

首先，请注意，将值与 0 进行异或运算不会改变结果。因此，要忽略一些位，我们可以将它们视为零。

因此，对 VALUE 中设置的位与 MASK 中的位进行异或运算等同于对 VALUE 和 MASK 中的位进行异或运算。

现在请注意，如果设置的位数为偶数，则结果为0，如果为奇数，则为1。

这意味着我们要计算设置位的数量。一些 architectures/compilers 有办法快速计算这个值。例如，在 GCC 上，这可以通过 __builtin_popcount.

获得

所以在 GCC 上，这可以用以下方法计算：

int set_bits = __builtin_popcount(value & mask);

return set_bits % 2;

如果你希望代码是可移植的，那么这是行不通的。但是，this answer 中的注释建议某些编译器可以内联 std::bitset::count 以有效地获得相同的结果。

Answer 4

如果在代码主体中使用 v &= v - 1，需要注意的一个重要问题是它会在进行计数时将 v 的值更改为 0。使用其他方法，该值将更改为 1 的数量。虽然计数逻辑通常包装为一个函数，这不再是一个问题，但如果您需要在代码主体中呈现计数逻辑，则必须保留 v 的副本，如果该值是又需要了。

除了介绍的其他两种方法外，以下是另一种最喜欢的位旋转技巧，它通常比循环方法对更大的数字有更好的性能：

/* get the population 1's in the binary representation of a number */
unsigned getn1s (unsigned int v)
{
    v = v - ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    v = (v + (v >> 4)) & 0x0F0F0F0F;
    v = v + (v << 8);
    v = v + (v << 16);
    return v >> 24;
}

基于位掩码从值中异或所有位的最快方法？

Fastest Way to XOR all bits from value based on bitmask?

c++

c

bit-manipulation

xor

Counting bits set, Brian Kernighan's way