位运算符 C++

Question

有人能解释一下这个函数的作用吗？我理解"drop the lowest set of a bit of x"部分，也就是第5行，但是我不明白 "result ^= 1;" 这行代码的作用。当决定一个单词的奇偶性时，result不应该计算0和1吗？

short Parity_of_word(unsigned long long x) {
    short result = 0;
    while(x) {
        result ^= 1;
        x &= (x-1);
    }
    return result;
}

- galo2324

---

^= 1 只是切换最低有效位。在这里，它的作用与声明 bool result = false; 并将 result ^= 1; 替换为 result = !result; 相同。 - dxiv

实际上，它通过减法和&运算迭代遍历1位，对于海明码（popcount，1位计数）也有类似的方法。对于奇偶校验位，实际上有一种更快的方法。 ^=1是XoR 1。 - Swift - Friday Pie

@galo2324 你明白 ! 和 ^ 的作用吗？非假即真。1 xor 1 = 0。 - Swift - Friday Pie

@galo2324 它并不总是假的。随着你计数每个位，它在0、1、0、1...或false、true、false、true...之间交替。 - dxiv

@galo2324，这将是popcount，您需要一个计数器。奇偶性是1或0，您不需要计数器。但是，如果您查看维基百科，您会发现一种算法，它不使用额外的标志，并且比N操作更快，它的工作方式是，奇偶校验位将是x中最不重要的位。 - Swift - Friday Pie

Answer 1

result ^= 1;

重复更改 result 在0和1之间。因此，问题是：这会执行多少次？

x&=(x-1);

这是一种"从x中删除最后一位"的hacky方法。为了看清，可以想象x是

0101000110

移除其中一个将会使其：

0101000101

（所有结尾的0变成了1，第一个1变成了0）。一旦您将这两个值and在一起:

0101000100

Tada，1 少了一个。因此，while 循环将执行与 x 中的 1 数量相同的次数。并且它将相应地翻转 result。

- Jeffrey