bitParity - 查找整数中的奇数位

我必须创建一个函数bitParity(int x)接受一个整数并返回1如果有奇数个0的位形式为x, and 0否则。

Ex: bitParity(5) = 0, bitParity(7) = 1

然而，这很困难，因为我只能使用位运算符来解决这个问题（! ˜ & ˆ | + << >>是唯一合法的）。这意味着，没有循环，if-then，或类似的东西。可以使用常量。

到目前为止，我所拥有的不起作用，但我认为我应该移动整数的位16, 8, and 4次和XOR剩余的整数。

有人可以提供一些建议吗？谢谢。

对于 32 位数字：

function bitParity(int x) {
   x ^= x >> 16;
   x ^= x >> 8;
   x ^= x >> 4;
   x &= 0xf;
   return (0x6996 >> x) & 1;
}

Note*0x6996 表示数字 1、2、4、7、8、11、13 和 14 的位向量。可以用奇数位表示的所有 4 位值。在 0x6996 中，如果某个位在向量中的位置对应于 (1、2、4、7、8、11、13 或 14)，则该位被设置。

这就是为什么 (0x6996 >> x) & 1 有意义，在移位 x 后，如果 x 等于位向量中的任何值，则该表达式只会返回 1，这意味着奇数位被放。