当前位置 博文首页 > dadalaohua的博客：【位操作笔记】计算奇偶性 使用64位乘法和模
计算奇偶性(Compute parity)指的是，计算一个数所包含1的个数是奇数还是偶数，例如一个8位数0x5b = 0b?0101 1011?，其中1的个数为5，是奇数；一个8位数0xa3 = 0b??1010 0011?，其中1的个数为4，是偶数。该算法可以用于奇偶校验位的计算与验证。
使用64位乘法和模除，只需要4次操作就能完成对单个字节的计算。实际就是先通过64位的乘法和模除计算出这个数里bit位置1的个数，然后判断个数是奇数还是偶数。
如果设置了奇数位数，返回true，否则返回false。
bool computing_parity(unsigned char val)
{
return (((val * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;
}
算法分为4个部分
用abcd efgh表示一个8bit数的8个bit位。
一共只需要4次操作。
val * 0x0101010101010101ULL将数值乘以0x0101010101010101，相当于将8bit的数在64bit中填满
(val * 0x0101010101010101ULL) & 0x8040201008040201ULL再乘以0x8040201008040201
((val * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF上一步得到的数值再取模运算0x1FF，就是511 = 29 - 1 ，相当于将每9bit的数相加在一起。
(((val * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1上一步得到了val这个数里bit位置1的总数，然后& 1得到数的奇偶性，完成计算。
例如一个数为0x68，二进制为0b0110 1000
0b01101000 * 0x0101010101010101ULL
?0x6868686868686868? & 0x8040201008040201ULL
第一步得到数值0x6868686868686868?， 再乘以0x8040201008040201。
0x40200008000000? % 0x1FF上一步得到的数值?0x40200008000000?再取模运算0x1FF。
4.0x3 & 1
上一步得到了这个数里bit位置1的总数为3，然后& 1得到的值为1，表示奇偶性为奇数。
完成奇偶性计算。
Bit Twiddling Hacks By Sean Eron Anderson
[Hacker’s Delight] 作者: Henry S. Warren Jr.
本文链接：https://blog.csdn.net/u012028275/article/details/112504023
cs