c - 如何检查一个值是否具有偶校验位或奇校验位？

Question

一个值有 even parity如果它有偶数个“1”位。如果一个值具有奇数个“1”位，则该值具有奇校验。例如，0110 为偶校验，1110 为奇校验。

如果 x 具有偶校验，我必须返回 1。

int has_even_parity(unsigned int x) {
    return
}

Answer 1

x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return (~x) & 1;

假设您知道整数是 32 位。

---

让我们看看它是如何工作的。为了简单起见，让我们使用一个 8 位整数，为此我们可以跳过前两个移位/异或运算。让我们将位标记为 a 到 h。如果我们查看我们的号码，我们会看到:

( a b c d e f g h )

---

第一个操作是x ^= x >> 4 (记住我们跳过了前两个操作，因为在这个例子中我们只处理一个 8 位整数)。让我们通过将异或运算的字母组合在一起来写入每个位的新值(例如，ab 表示该位的值为 a xor b).

( a b c d e f g h ) 异或 ( 0 0 0 0 a b <我>c d )

结果是以下几位:

( a b c d ae bf cg dh )

---

下一个操作是x ^= x >> 2 :

( a b c d ae bf cg dh ) 异或 ( 0 0 a b c d ae bf )

结果是以下几位:

( a b ac bd ace bdf aceg bdfh )

注意我们是如何开始累加右侧的所有位的。

---

下一个操作是x ^= x >> 1 :

( a b ac bd ace bdf aceg bdfh ) 异或 ( 0 a b ac bd ace bdf aceg )

结果是以下几位:

( a ab abc abcd abcde abcdef abcdefg abcdefgh )

---

我们已经累积了原始单词中的所有位，并在最低有效位中将它们异或在一起。因此，当且仅当输入字中有偶数个 1 位(偶校验)时，该位现在为零。相同的过程适用于 32 位整数(但需要我们在本演示中跳过的那两个额外的移位)。

最后一行代码简单地去除了除最低有效位之外的所有位 (& 1)，然后翻转它 (~x)。那么，如果输入字的奇偶性是偶数，则结果为 1，否则为零。