最快的方法是根据位掩码从值中对所有位进行异或运算？(Fastest Way to XOR all bits from value based on bitmask?)

最快的方法是根据位掩码从值中对所有位进行异或运算？(Fastest Way to XOR all bits from value based on bitmask?)

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

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

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

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

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

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

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

I've got an interesting problem that has me looking for a more efficient way of doing things.

Let's say we have a value (in binary)

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

Now, I need to be able to XOR any bits from the (AND) value that are set in the (MASK) value (always lowest to highest bit):

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

Now, on paper, this is certainly quick since I can see which bits are set in the mask. It seems to me that programmatically I would need to keep right shifting the MASK until I found a set bit, XOR it with a separate value, and loop until the entire byte is complete.

Can anyone think of a faster way? I'm looking for the way to do this with the least number of operations and stored values.

最满意答案

如果我正确理解了这个问题，你想要的是从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来有效地获得相同的结果。

If I understood this question correctly, what you want is to get every bit from VALUE that is set in the MASK, and compute the XOR of those bits.

First of all, note that XOR'ing a value with 0 will not change the result. So, to ignore some bits, we can treat them as zeros.

So, XORing the bits set in VALUE that are in MASK is equivalent to XORing the bits in VALUE&MASK.

Now note that the result is 0 if the number of set bits is even, 1 if it is odd.

That means we want to count the number of set bits. Some architectures/compilers have ways to quickly compute this value. For instance, on GCC this can be obtained with __builtin_popcount.

So on GCC, this can be computed with:

int set_bits = __builtin_popcount(value & mask); return set_bits % 2;

If you want the code to be portable, then this won't do. However, a comment in this answer suggests that some compilers can inline std::bitset::count to efficiently obtain the same result.