当前位置 博文首页 > dadalaohua的博客：【位操作笔记】计算奇偶性 普通方法
计算奇偶性(Compute parity)指的是，计算一个数所包含1的个数是奇数还是偶数，例如一个8位数0x5b = 0b?0101 1011?，其中1的个数为5，是奇数；一个8位数0xa3 = 0b??1010 0011?，其中1的个数为4，是偶数。该算法可以用于奇偶校验位的计算与验证。
使用了一种类似于Brian Kernigan’s的位计数的方法，该算法每次清除从最低位到最高位数的第一个为1的位。所需时间与置位的位数成正比。
如果设置了奇数位数，返回true，否则返回false。
bool computing_parity(unsigned int val)
{
bool parity = false;
while (val)
{
parity = !parity;
val = val & (val - 1);
}
return parity;
}
算法核心在于val = val & (val - 1)这句代码。val & (val - 1)会使val中位置最靠右并且值为1的bit位置0，也就是用于清除掉从最低位到最高位数的第一个为1的位，循环中每次都能清除一个位，每清除一个位，奇偶性就反转一次，根据清除位的次数，就可以知道数包含1的个数奇偶性。
例如一个数为0b0110 1000
parity : parity = 0(flase)偶数
val : val = 0b0110 1000
val : val > 0
val & (val - 1)
0b0110 1000
& 0b0110 0111
---------------
0b0110 0000
parity : parity = 1(true)奇数
val : val = 0b0110 0000
val : val > 0
val & (val - 1)
0b0110 0000
& 0b0101 1111
---------------
0b0100 0000
parity : parity = 0(flase)偶数
val : val = 0b0100 0000
val : val > 0
val & (val - 1)
0b0100 0000
& 0b0011 1111
---------------
0b0000 0000
parity : parity = 1(true)奇数
val : val = 0b0000 0000
val : val = 0
最后得到结果，parity为true，1的个数为奇数。
完成奇偶性计算。
Bit Twiddling Hacks By Sean Eron Anderson
[Hacker’s Delight] 作者: Henry S. Warren Jr.
本文链接：https://blog.csdn.net/u012028275/article/details/112441315
cs