2

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

例如：bitParity(5) = 0, bitParity(7) = 1 合法操作：！~ & ^ | + << >>

我的朋友与我分享了他的代码，但是当我从头开始计算时，它似乎与他得到的相反，有人可以稍微解释一下这段代码，以便我了解它是如何运作的吗？

int bitParity(int x) {
x = ( x >> 16 ) ^ x;
x = ( x >> 8 ) ^ x;
x = ( x >> 4 ) ^ x;
x = ( x >> 2 ) ^ x;
x = ( x >> 1 ) ^ x;

    return (x & 1);
}
4

1 回答 1

0

这个函数基本上是xoring 输入数字的所有位并将其放在 LSB，因此1如果有奇数个1s，则给出。

这个怎么运作：

  • 接受输入8-bit，比如说11001001。
  • 对于8-bit输入，您需要从代码的第三条语句开始：x = ( x >> 4 ) ^ x;

  • 这样做（步骤 1），您将获得：

    x 7  x 6  x 5  x 4  x 7 ^x 3   x 6 ^x 2   x 5 ^x 1   x 4 ^x 0

其中 x i表示ith的位x。

  • 现在第 2 步：x = ( x >> 2 ) ^ x;给出：

    x 6 ^x 2 ^x 4 ^x 0           在 的 LSB x，
    x 7 ^x 3 ^x 5 ^x 1在的           位1。x休息位置不相关。

  • 第3步：x = ( x >> 1 ) ^ x;最终给出：

    x 6 ^x 2 ^x 4 ^x 0 ^x 7 ^x 3 ^x 5 ^x 1           在 的 LSB 处x。

  • 最后一步：return (x & 1);返回这个表达式的值，它是当且仅当s 的数量是奇数xor时所有位的值。x11x

  • 您可以将此扩展到16-bit、32-bit或64-bit数字。

  • 另外，请注意，找到0s 的奇数等于找到 s 的奇数1，1因为s 和s 的总数0加起来是偶数位数。

  • 因此，上面的代码应该为您正常工作

于 2014-02-03T06:10:57.123 回答