c - bitParity - 在整数中查找奇数位

Question

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

例如:bitParity(5) = 0, bitParity(7) = 1
然而，这很困难，因为我只能在这个问题上使用位运算符(! ˜ & ˆ | + << >> 是唯一合法的)。这意味着，没有循环，if-then ，或任何类似的东西。可以使用常量。

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

任何人都可以提供一些建议吗？谢谢。

Answer 1

对于 32 位数字:

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

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

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