EEPW论坛

问

/*
* hweightN: returns the hamming weight (i.e. the number
* of bits set) of a N-bit word
*/

static inline unsigned int generic_hweight32(unsigned int w)
{
unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555);
res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F);
res = (res & 0x00FF00FF) + ((res >>８) & 0x00FF00FF);
return (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF);
}

呵呵,
哪位大虾不妨看看，这个的数学公式怎样的，我推导了半天也写不出（数学不行）．

答 1: 哈哈，LZ正向推好像是困难点，试试反向推导请看下图的推导，这是16位的示例，32位的一样： 答 2: 漂亮,谢谢,推导的真棒! 答 3: 这个家伙解释的也挺妙,贴上来,源自linuxfans.org "loveccy 发表于: 2006年 09月25日 12:37"

这是内核里面的代码吗？有意思！聪明！妙！

我好像看明白了。
所谓的 hamming weight 就是指的 1 的个数吧。想知道 32 位里一共有多少个 1 ，只要分别得到高 16 位和低 16 位里 1 的个数，再加起来就行了。也就是最后的这行 (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF) 。
那要想知道 16 位里有多少个 1 ，只要知道它的高 8 位和低 8 位里分别有几个 1 就行了。也就是倒数第二行的 (res & 0x00FF00FF) + ((res >>８) & 0x00FF00FF) 。
依此类推，最后只要知道 2 位里有几个 1 。这就简单了，高 1 位和低 1 位一加就行了。这就是第一行的 (w & 0x55555555) + ((w >> 1) & 0x55555555) 。

答 4: 还是俺这个直观、经典；这是典型的递归的思路，妙！妙！妙！沾沾自喜。。。。 答 5: 妙