#内核里的神函数# 之 hweight32

原创
2016/04/14 18:57
阅读数 2.1K

    在阅读iptables内核模块的代码时,我遇到了这样一个函数hweight32:

unsigned int hweight32(unsigned int w)
{
    unsigned int res = w - ((w >> 1) & 0x55555555);
    res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
    res = (res + (res >> 4)) & 0x0F0F0F0F;
    res = res + (res >> 8);
    return (res + (res >> 16)) & 0x000000FF;
}

    乍看起来,似乎很难理解这段代码的功能,其实它就完成了“统计给定数字中值为1的bit位个数”的功能,怎么样,是不是有点风马牛不相及的感觉。

    下面我们先看网络上的一篇分析文章

============转载:华丽的分割线============

在 linux 内核里,在计算 CPU 个数时用到了 hweight32 这个函数,这个函数就是汉明重量的计算方法。对于二进制串来说,它就是计算这个二进制串里含有多少个 1 。hweight32() 函数实现如下:

/*代码如上*/

下面先对一个任意的二进制串中 1 的数量的计算推出上面的公式:
1. 假设有 1 个字串为:0110 1100 1011 1010,姑且将这个字串简称为 A
2. 我们先将 A 以每 2 位一组进行分组,即 01 10 11 00 10 11 10 10 ,然后计算出每组含有 1 的个数,方法如下:

<1> 首先用 0101 0101 0101 0101 即 (0x5555) 来和 A 相与:
0110 1100 1011 1010
0101 0101 0101 0101 &
---------------------------------
0100 0100 0001 0000                    (将这个结果设为 B)

经过上面的计算,实际上我们已经得出了 A 中每小组中(每 2 位一组)的偶数位的 1 的个数,即(1,0,1,0,0,1,0,0)。

<2> 在步骤 <1> 中我们算出了每组中偶数位 1 的个数,接下来要算出奇数位中 1 的个数,方法是先将 A 右移 1 位 (A >> 1),然后与 0x5555 再相与。A 右移 1 位就是将原来的奇数位变为偶数位:
0011 0110 0101 1101      (A>>1)
0101 0101 0101 0101      &
---------------------------------------------
0001 0100 0101 0101                    (将这个结果设为 C)

<3> 现在,将 B 和 C 相加起来,就能得到 A 中每 2 位为一组的每组中的 1 的个数:
D = B + C
D =  0100 0100 0001 0000  + 0001 0100 0101 0101 = 01 01 10 00 01 10 01 01
                                                                                      (1   1   2   0   1   2   1   1)

好,现在我们已经算出了 A 中以每 2 位分成一组的每个小组中 1 的个数。同理,接下来我们要利用上面的结果(D)算出 A 中以每 4 位分成一组中每个小组中 1 的个数:

<4> 用 D 和 0011 0011 0011 0011 (0x3333)进行相与:
0101 1000 0110 0101
0011 0011 0011 0011  &
---------------------------------
0001 0000 0010 0001                (将这个结果设为 E)

<5> 再将 D 右移 2 位,即 D >> 2 后,再和 0x3333 相与:
0001 0110 0001 1001                 (D>>2)
0011 0011 0011 0011      &
------------------------------------
0001 0010 0001 0001                (将这个结果设为 F)

<6> 将 E 和 F 相加:
G = E + F
G = 0001 0000 0010 0001 + 0001 0010 0001 0001 = 0010 0010 0011 0010
                                                                                     (2      2       3       2     )
也就是说,A 中以每 4 位分成一组后,每小组中 1 的个数分别为 2, 2, 3, 2

<7> 同样的方法,下面再计算每 8 位一组的每小组中的 1 的个数 (逐步逼近)

先将 G 和 0x0F0F 相与:
0010 0010 0011 0010
0000 1111 0000 1111  &
--------------------------------
0000 0010 0000 0010               (将这个结果设为 H)

同理再将 G 右移 4 位后与 0x0F0F 相与:
0000 0010 0010 0011
0000 1111 0000 1111   &
---------------------------------
0000 0010 0000 0011                (将这个结果设为 I)

<8> H 和 I 相加后即得每 4 位分组后每小组 1 的个数:
J = H + I
J = 0000 0010 0000 0010  + 0000 0010 0000 0011 = 0000 0100 0000 0101
                                                                                    (          4            5        )

<9> 到此,之差最后逼近一步,便可得到我们想要的结果,现在将 J  与 0x00FF 相与:
0000 0100 0000 0101
0000 0000 1111 1111   &
--------------------------------
0000 0000 0000 0101          (将这个结果设为 K)

<10> 将 J 右移 8 位后再与 0x00FF 相与:
0000 0000 0000 0100
0000 0000 1111 1111  &
---------------------------------
0000 0000 0000 0100           (将这个结果设为 L)

<11> 将 K 和 L 相加:
M = K + L = 0000 0000 0000 0101 + 0000 0000 0000 0100 = 5 + 4 = 9

最终结果为 9 ,这就是字串 A 中的 1 的个数。

============转载: 华丽的分割线============

    下面再来简单的逐行分析一下:

unsigned int res = w - ((w >> 1) & 0x55555555);

    将w按2bit为一组划分,统计每组中1的个数;

    这里并没有做两次“位与&“的操作,其中蕴含的一个小技巧是:对于一个2bit的数字,其值减去它右移一位的结果就是这个2bit数字中1的个数,例如:

    11 - 01 = 10 (2):11中含有的1的个数为2;

    10 - 01 = 01 (1):10中含有的1的个数为1;

    01 - 00 = 01 (1):01中含有的1的个数为1;

    00 - 00 = 00 (0):00中含有的1的个数为0;

res = (res & 0x33333333) + ((res >> 2) & 0x33333333);

    将第一步的计算结果以每4位为一组,计算每组中1的个数;

res = (res + (res >> 4)) & 0x0F0F0F0F;

    将上一步的计算结果以每8位为一组,计算每组中1的个数;

    由于上一步中计算的是每4位为一组的结果,因此其最大值为4(0100),因此可以直接相加而不用担心溢出,并将高四位归0;

res = res + (res >> 8);

    将上一步的计算结果以每16位为一组,计算每组中1的个数;

return (res + (res >> 16)) & 0x000000FF;

    将高16bit中1的个数与低16bit中1的个数相加,就得到了最后的结果;


结论:请收下我的膝盖!




展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
1 收藏
2
分享
返回顶部
顶部