曲径通幽论坛

标题: 汉明重量 [打印本页]

作者: beyes 时间: 2011-5-11 21:28
标题: 汉明重量
在 linux 内核里，在计算 CPU 个数时用到了 hweight32 这个函数，这个函数就是汉明重量的计算方法。对于二进制串来说，它就是计算这个二进制串里含有多少个 1 。hweight32() 函数实现如下：

[C++] 纯文本查看 复制代码

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 的数量的计算推出上面的公式：
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 的个数。

从上面的一系列推演，我们验证了 hweight32() 函数公式。汉明重量方法十分快速，这要比循环比较来说要高效不少。顺便说下，听一个到 TX 面试的兄弟说，它当时被问到“不用循环的方法如何算出一个二进制数中的 1 的个数”，实际上，考官正是想考汉明重量算法。

欢迎光临曲径通幽论坛 (http://www.groad.net/bbs/)