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

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

如果我对这个问题的理解正确，你想要的是从 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;

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