bool computing_parity(unsigned int val)
{
    val ^= val >> 16;
    val ^= val >> 8;
    val ^= val >> 4;
    val &= 0xf;
    return (0x6996 >> val) & 1;
}

算法计算过程

1. 第一步和第二步v ^= v >> 16

   将32位数值压缩成16位数值。因为异或操作和奇偶性的特点，这个操作只会减少置位的bit数，但不影响奇偶性。接下来就只关心低16位的数值。

2. 第三步和第四步v ^= v >> 8

   将16位数值压缩成8位数值。因为异或操作和奇偶性的特点，这个操作只会减少置位的bit数，但不影响奇偶性。接下来就只关心低8位的数值。

3. 第五步和第六步v ^= v >> 4

   将8位数值压缩成4位数值。接下来就只关心低4位的数值。

4. 第七步v &= 0xf

   剔除无用的bit位的数据，只剩下低4位的数值。

5. 第八步0x6996 >> val

   0x6996 转换成二进制就是 0110 1001 1001 0110，这个相当于是一个16位奇偶性表格，通过右移上一步计算出的数值，就能得到数值的奇偶性。

6. 第九步& 1

   得到奇偶性。

例如一个数为0x355C4E25，二进制为0b?00110101010111000100111000100101?，共15bit

1. v ^= v >> 16

2. v ^= v >> 8
   

3. v ^= v >> 4
   

4. v &= 0xf

5. 0x6996 >> val
   

6. & 1
   

最后得到结果，为奇数。

完成奇偶性计算。

完整过程

拓展

计算8位的奇偶性 。使用该方法运算，只用5次运算就能完成计算。

bool computing_parity(unsigned int val)
{
    val ^= val >> 4;
    val &= 0xf;
    return (0x6996 >> val) & 1;
}