【位操作笔记】计算奇偶性 使用乘法

本文主要是介绍【位操作笔记】计算奇偶性 使用乘法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

计算奇偶性(Compute parity) 使用乘法

计算奇偶性(Compute parity)指的是，计算一个数所包含1的个数是奇数还是偶数，例如一个8位数0x5b = 0b‭0101 1011‬，其中1的个数为5，是奇数；一个8位数0xa3 = 0b‭‭1010 0011‬，其中1的个数为4，是偶数。该算法可以用于奇偶校验位的计算与验证。

算法说明

使用乘法运算，仅在8次运算中计算32位数值的奇偶性 。实际就是先通过乘法计算出这个数里bit位置1的个数，然后判断个数是奇数还是偶数。

如果设置了奇数位数，返回true，否则返回false。

实现代码

bool computing_parity(unsigned int val)
{val ^= val >> 1;val ^= val >> 2;val = (val & 0x11111111U) * 0x11111111U;return (val >> 28) & 1;
}

算法计算过程

算法分为8步。

1. 第一步和第二步val ^= val >> 1

   用于将相邻的两个bit位进行异或，结果存在偶数位上(从第0位开始算)。因为异或操作和奇偶性的特点，这个操作只会减少置位的bit数，但不影响奇偶性。
   例如下面是个32位数
   
   按照位置分成偶数位和奇数位
   
   右移1位
   
   两个数进行异或，会得到一个数，但我们实际只关心这个结果的偶数位，如下所示的32位数，只关心绿色格子。
   
   在忽略掉奇数位上的数值(既上图的白色格子)后，这其实是相当于把32位数压缩成16位数，奇偶性相同。
   两个数异或不影响奇偶性，因为如果两个数分别为1和0，则是1 ^ 0 = 1，还是奇数；如果两个数分别为1和1，1 ^ 1 = 0，还是偶数；如果两个数分别为0和0，0 ^ 0 = 0，还是偶数。

2. 第三步和第四步val ^= val >> 2

   将上一步得到的结果，再进行相邻的两个数进行异或操作。这步进一步减少置位的bit数，但不影响奇偶性。
   继续使用上一步得到的数
   
   再分成两种颜色
   
   右移两位
   
   两个数进行异或，会得到一个数，但我们实际只关心这个结果的4倍数的位，如下所示的32位数，只关心橙色格子。
   
   在忽略掉奇数位上的数值(既上图的白色格子)后，这其实是相当于把32位数压缩成16位数，奇偶性相同。现在实际就只有8个bit位有意义。

3. 第五步 val & 0x11111111U

   剔除无用的bit位的数据。
   下图中白色格子内的数值被清空。
   

   此时得到的32位数据如下，a,b,c,d,e,f,g,h都是表示一个bit位，数值未知。此时a+b+c+d+e+f+g+h的和的奇偶性就是原数值val的奇偶性。

000a 000b 000c 000d 000e 000f 000g 000h

4. 第六步* 0x11111111U

   将上一步得到的结果乘以0x11111111U
   

5. 第七步val >> 28

   上一步计算的结果，28-31bit位置存储着a+b+c+d+e+f+g+h的和，将这个数右移28位，得到的就是这个数里bit位置1的总数。
   

6. 第八步& 1

   上一步得到了val这个数里bit位置1的总数，然后& 1得到数的奇偶性，完成计算。

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

1. val ^= val >> 1

‭‭           0011 0101 0101 1100 0100 1110 0010 0101‬
>> 1
--------------------------------------------------0001 1010 1010 1110 0010 0111 0001 0010‬
^          0011 0101 0101 1100 0100 1110 0010 0101‬
--------------------------------------------------0010 1111 1111 0010 0110 1001 0011 0111

2. ‭val ^= val >> 2;

           0010 1111 1111 0010 0110 1001 0011 0111
>> 2
--------------------------------------------------0000 1011 1111 1100 1001 1010 0100 1101
^          0010 1111 1111 0010 0110 1001 0011 0111
--------------------------------------------------0010 0100 0000 1110 1111 0011 0111 1010

3. val & 0x11111111U

           0010 0100 0000 1110 1111 0011 0111 1010
&          0001 0001 0001 0001 0001 0001 0001 0001
--------------------------------------------------0000 0000 0000 0000 0001 0001 0001 0000

4. val = (val & 0x11111111U) * 0x11111111U

           0000 0000 0000 0000 0001 0001 0001 0000
*          0001 0001 0001 0001 0001 0001 0001 0001
--------------------------------------------------0000 0000 0000 0000 0000 0000 0000 00000001 0001 0001 0001 0001 0001 00010001 0001 0001 0001 0001 00010001 0001 0001 0001 00010000 0000 0000 00000000 0000 00000000 00000000
--------------------------------------------------0011 0011 0011 0011 0011 0010 0001 0000

5. (val >> 28) & 1

           0011 0011 0011 0011 0011 0010 0001 0000
>> 28
--------------------------------------------------0011
&                                                1
--------------------------------------------------1

上一步得到了这个数里bit位置1的总数为3，然后& 1得到的值为1，表示奇偶性为奇数。

完成奇偶性计算。

完整过程如下

拓展

计算64位的奇偶性 。使用乘法运算，同样只用8次运算就能完成计算。

bool computing_parity(unsigned long long val)
{val ^= val >> 1;val ^= val >> 2;val = (val & 0x1111111111111111UL) * 0x1111111111111111UL;return (val >> 60) & 1;
}

---

[参考资料]

Bit Twiddling Hacks By Sean Eron Anderson

[Hacker’s Delight] 作者: Henry S. Warren Jr.

---

本文链接：https://blog.csdn.net/u012028275/article/details/112596947

这篇关于【位操作笔记】计算奇偶性 使用乘法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---