本文共 2946 字，大约阅读时间需要 9 分钟。
hamming weight(汉明权重)算法是一种用于计算字节串中1bit的数目。
比如，0b1001 0000，ob0000 0011, 0b1000 0001的汉明权重均为2，ob 1110 0001, 0b1100 1100, 0b1001 1001的汉明权重均为4.
汉明权重的算法(32位)：
int Hamming_weight(uint32_t n ) {
n = (n&0x55555555) + ((n>>1)&0x55555555);
n = (n&0x33333333) + ((n>>2)&0x33333333);
n = (n&0x0f0f0f0f) + ((n>>4)&0x0f0f0f0f);
n = (n&0x00ff00ff) + ((n>>8)&0x00ff00ff);
n = (n&0x0000ffff) + ((n>>16)&0x0000ffff);
return n;
}
下面，我们来逐一分析各行的意图。
n = (n&0x55555555) + ((n>>1)&0x55555555)
将n的bit位从高位(bit31)到低位(bit0)分组，每1bits一组，共计32组，相邻两组两两相加，相加的结果用2bits来存储。
这里的计算结果含义为，输入数据n，从高位到低位分组，每1位一组，共计32组，这32组，相邻两组相加，结果存放在两组所有bits对应的bits上。
这样，计算结果的32位数据，由16份组成，每一份为输入参数n的相邻2组(每组1bit)的bit为1的数目。
要计算输入参数n的hamming weight, 就转化为计算这个新32数据的16份2bits数据之和。
下面，我们就进一步计算：即新的32位数据，被划分为16分，每份2bits，要计算的是这16个2bits的数据之和。
n = (n&0x33333333) + ((n>>2)&0x33333333)
将32位数从高位(bit31)到低位(bit0)分组，每2bits一组，共计16组，相邻两组两两相加，相加的结果用4bits来存储。
这里的计算结果的含义：将n从高位(bit31)到低位(bit0)分组，每2bits划分为一组，共计16组，且组两两相加，用4bits来存放，存放bit位置为对应的2组所有bits(4个bits)对应的bit位置。
这样，计算结果的32位数据，由8份数据组成，每份4bits。
所以，这里将hamming weight算法中的输入n的有多少个bit 1的问题转换为这里的计算结果的32位数据中的8份4bits数据之和。即要计算这个新32位数据的每4bits之和。
下面，我们就来进一步分解计算这个新32位数据的每4bits之和。
n = (n&0x0f0f0f0f) + ((n>>4)&0x0f0f0f0f)
将32位数据分组，每4bits一组，共计8组，相邻组两两相加，结果用8bits来存储。
这里的计算结果的含义：将n从高位(bit31)到低位(bit0)分组，每4bits划分为一组，共计8组，且组两两相加，用8bits来存放，存放bit位置为对应的2组所有bits(8个bits)对应的bit位置。
这样，计算结果的32位数据，由4份数据组成，每份8bits。
所以，这里将hamming weight算法中的输入n的有多少个bit 1的问题转换为这里的计算结果的32位数据中的4份8bits数据之和。即要计算这个新32位数据的每8bits之和。
下面，我们就来进一步分解计算这个新32位数据的每8bits之和。
n = (n&0x00ff00ff) + ((n>>8)&0x00ff00ff);
将32位数据分组，每8bits一组，共计4组，相邻组两两相加，结果用16bits来存储.
这里的计算结果的含义：将n从高位(bit31)到低位(bit0)分组，每8bits划分为一组，共计4组，且组两两相加，用16bits来存放，存放bit位置为对应的2组所有bits(16个bits)对应的bit位置。
这样，计算结果的32位数据，由2份数据组成，每份16bits。
所以，这里将hamming weight算法中的输入n的有多少个bit 1的问题转换为这里的计算结果的32位数据中的2份16bits数据之和。即要计算这个新32位数据的每16bits之和。
下面，我们就来进一步分解计算这个新32位数据的每16bits之和。
n = (n&0x0000ffff) + ((n>>16)&0x0000ffff)
将32位数据分组，每16bits一组，共计2组，相邻组两两相加，结果用32bits来存储.
这里的计算结果的含义：将n从高位(bit31)到低位(bit0)分组，每16bits划分为一组，共计2组，且组两两相加，用32bits来存放，存放bit位置为对应的2组所有bits(32个bits)对应的bit位置。
所以，hamming weight算法中的输入n的有多少个bit 1，其值为这里的计算结果的32位数据。
下面我们来看看kernel中的hamming weight算法的实现：
kernel中的实现和我们之前讲的不一样。
我们只讲图中蓝色方框中的实现。
unsigned int res = w - ((w >> 1) & 0x55555555);
这个语句是什么含义？
思路一样，将32位数据分32组，每2组做一个分析单元。即分析相邻两组(2bits)中1的数目。我们以b0, b1为例(图中最右的红色框)。
如果 b0 == b1，则最右边的红框中的减法结果为 b1 0, 当b0 == b1 == 1时，减法结果为0b 1 0, 即十进制数2，表示b0, b1中有2个bit 的值为1；当b0 == b1 == 0时，减法结果为0b 00,即十进制数0，表示b0, b1中有0个bit的值为1.
如果b0 != b1, 即他们中只有一个为1，则最后边的红框中的减法结果为0b 0 1, 即十进制数1，表示b0, b1中有1个bit的值为1.
所以，计算结果中的每个红色框的值(2bits数据)表示对应两组中所有bits中bit为1的数目。
很显然，后面要计算这里的16个红色框的2bits的数据的和。
res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
这一步和前面的算法实现一样，跳过。
res = (res + (res >> 4)) & 0x0F0F0F0F;
这一步和前面的算法实现一样，跳过。(有人说不一样，前面的实现中res & 0x0F0F0F0F, 这里没有。其实是一样的做与不做res & 0x0F0F0F0F，其结果都是相邻4bits相加。)
res = res + (res >> 8);
这一步和前面的算法实现一样，跳过。
return (res + (res >> 16)) & 0x000000FF;
这一步和前面的算法实现一样，跳过。
所以，kernel的实现，除了第一步的思想不一样外，后面的都是一样的。
转载地址：http://ntlci.baihongyu.com/