当前位置 博文首页 > dadalaohua的博客：【位操作笔记】计算奇偶性 使用乘法

最大化 缩小

    dadalaohua的博客：【位操作笔记】计算奇偶性 使用乘法

    作者：[db:作者] 时间：2021-07-27 14:49

    计算奇偶性(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位数
      00
      按照位置分成偶数位和奇数位
      11
      右移1位
      22
      两个数进行异或，会得到一个数，但我们实际只关心这个结果的偶数位，如下所示的32位数，只关心绿色格子。
      33
      在忽略掉奇数位上的数值(既上图的白色格子)后，这其实是相当于把32位数压缩成16位数，奇偶性相同。
      两个数异或不影响奇偶性，因为如果两个数分别为1和0，则是1 ^ 0 = 1，还是奇数；如果两个数分别为1和1，1 ^ 1 = 0，还是偶数；如果两个数分别为0和0，0 ^ 0 = 0，还是偶数。

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

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

    3. 第五步 val & 0x11111111U

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

      此时得到的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

    1. 第六步* 0x11111111U

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

    2. 第七步val >> 28

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

    3. 第八步& 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
    1. ?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
    1. 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
    1. 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 0000
           0001 0001 0001 0001 0001 0001 0001
           0001 0001 0001 0001 0001 0001
           0001 0001 0001 0001 0001
           0000 0000 0000 0000
           0000 0000 0000
           0000 0000
           0000
--------------------------------------------------
           0011 0011 0011 0011 0011 0010 0001 0000
    1. (val >> 28) & 1
               0011 0011 0011 0011 0011 0010 0001 0000
>> 28
--------------------------------------------------
                                              0011
&                                                1
--------------------------------------------------
                                                 1

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

    完成奇偶性计算。

    完整过程如下
    2

    拓展

    计算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

    cs
    上一篇：dadalaohua的博客：【位操作笔记】计算奇偶性 异或和右移查表法
    下一篇：没有了