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;
}

Answer 2

这可以通过循环正确解决.但是这是一种没有它的方法.

x = (x & 0x0000FFFF) ^ (x >> 16)
x = (x & 0x000000FF) ^ (x >> 8)
x = (x & 0x0000000F) ^ (x >> 4)
x = (x & 0x00000003) ^ (x >> 2)
x = (x & 0x00000001) ^ (x >> 1)

编辑:我不需要&.更好的版本:

x ^= x >> 16
x ^= x >> 8
x ^= x >> 4
x ^= x >> 2
x ^= x >> 1
x &= 1;