xoring 如何计算位奇偶性？

Question

/*
 * bitParity - returns 1 if x contains an odd number of 0's
 *   Examples: bitParity(5) = 0, bitParity(7) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 4
 */
int bitParity(int x) { //XORing two numbers returns a number with same bit parity. 
                       //Keep shifting half of our number until reduced to 1 bit simple case
  x = ( x >> 16 ) ^ x;
  x = ( x >> 8 ) ^ x;
  x = ( x >> 4 ) ^ x;
  x = ( x >> 2 ) ^ x;
  x = ( x >> 1) ^ x;

  return (x & 1);
}

嗨，我试图解决这个问题，但失败了。

所以我在 google 上搜索了答案。

google 上可用的大多数解决方案彼此不同，

但是在这个位奇偶性问题中，答案都是一样的（使用异或）

我知道询问这个或那个代码是如何工作的是错误的，

所以我想知道机制或想法。

如果你能给我一些想法，那将非常有帮助。

几天都无法解决这个问题，需要一些帮助

int bitParity(int x) {
  int x1 = ( x >> 28 ) ^ x;
  int x2 = ( x >> 24 ) ^ x1;
  int x3 = ( x >> 20 ) ^ x2;
  int x4 = ( x >> 16 ) ^ x3;
  int x5 = ( x >> 12 ) ^ x4;
  int x6 = ( x >> 8 ) ^ x5;
  int x7 = ( x >> 4 ) ^ x6;
  int x8 = ( x >> 2 ) ^ x7;
  int x9 = ( x >> 1 ) ^ x8;
  return (x9 & 1);
}

以上代码无效

Answer 1

使用调试器，您可以逐行跟踪语句流：

x = ( x >> 16 ) ^ x;

计算高（最高）16 位和低（最低）16 位的按位 xor。仅结果的低 16 位被进一步考虑。整数的上半部分被 down/right 移动 16 位。

  x = ( x >> 8 ) ^ x;

计算前一个结果的高 8 位和低 8 位的按位 xor。

  x = ( x >> 4 ) ^ x;
  x = ( x >> 2 ) ^ x;
  x = ( x >> 1) ^ x

原来的32位是collapsed/folded到16、8、4、2、1位来收集不相等的位位置。最终，剩余的单个位指示原始 32 位整数中是否存在奇数个设置位。

如果对一个整数的两半进行异或运算，则具有相同值的位位置将产生 0 位，而具有相反值的位位置将产生 1 位。因此，得到的 1 位表示原始整数中的位位置对，它们是不相等的。这样的一对 "odd pairs" 抵消了。

x & 1

屏蔽 x 的最低有效位，奇数 x 为 1，偶数 x.

为 0

xoring 如何计算位奇偶性？

how xoring calculates bitsparity?

bit-manipulation

bit-shift