有趣,大家看看Linux如何实现hamming weigh！

fineamy 发表于 2006-9-25 10:47:10

/*
* 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);
}

有两个问题，挺感兴趣，
１．哪位大虾不妨看看，这个的数学公式怎样的，我推导了半天也写不出（数学不行）．
２．这样做会比通常移位判断有效率吗（不过好象是呀！）．

loveccy 发表于 2006-9-25 12:37:53

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

我好像看明白了。
所谓的 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) 。

fineamy 发表于 2006-9-25 18:48:55

楼上的回答很妙,

看看另外的回答,拓展拓展思路,
源自21IC.COM BBS "平常人发表于 2006-9-25 11:46 "

哈哈，LZ正向推好像是困难点，试试反向推导

请看下图的推导，这是16位的示例，32位的一样:
http://blog.21ic.org/uploadfile-/2006925184226631.gif

loveccy 发表于 2006-9-26 12:23:35

21ic 论坛的搜索怎么用啊……找不到你说的帖子……

“平儿出来吩咐林之孝家的道：‘“大事化为小事，小事化为没事”，方是兴旺之家。……’”
官人老爷们对此颇有研究。

我想那个 1000 个盘子装 10 个箱子的题目，也可以用这个思路来做。结果就是 500、250、125、63、31、16、8、4、2、1。从《十万个为什么》上抄来的是另一个答案。

呵呵。昨天在博客中国上看了好多文章。想不做 fq 都难。大多数人都有思想，比自己左的，就说他是 fq 呗，哼。

页: [1]

中国Linux公社论坛's Archiver

有趣,大家看看Linux如何实现hamming weigh！

楼上的回答很妙,