向“世界上最快的判断32位整数二进制中1的个数的算法”挑战

yzc2002

原帖由 liubinbj 于 2006-7-21 11:29 发表


仅适用于比较苛刻计算的场合，大量的大循环计算，少量的计算楼主的算法已经够好了。

注意到你曾经提到过这个用例：
例如:在n!中2的因子的个数=n-(n的二进制中1的个数)
如:10！2的因子个数为2、6、10各1个 ...

对于一个大整数n,它的位数大约为log2(n),按你的做法是11位11位地进行计算,所以大约需log2(n)/11次计算
而用下面这个:

1. unsigned numbits(unsigned int i)
   
2. {
   
3. 
   
4.     unsigned int const MASK1  = 0x55555555;
   
5.     unsigned int const MASK2  = 0x33333333;
   
6.     unsigned int const MASK4  = 0x0f0f0f0f;
   
7.     unsigned int const MASK8  = 0x00ff00ff;
   
8.     unsigned int const MASK16 = 0x0000ffff;
   
9.    
   
10.     i = (i&MASK1 ) + (i>>1 &MASK1 );
    
11.     i = (i&MASK2 ) + (i>>2 &MASK2 );
    
12.     i = (i&MASK4 ) + (i>>4 &MASK4 );
    
13.     i = (i&MASK8 ) + (i>>8 &MASK8 );
    
14.     i = (i&MASK16) + (i>>16&MASK16);
    
15.    
    
16.     return i;
    
17. }
    

复制代码

用到的次数是log2(log2(n))的
当log2(n)/11 > log2(log2(n)), 至少当n>2^2^7(^这里是乘方)时,你的程序速度就比它慢了

另外,你好象没看懂我(yuxh)那个用例吧?

[ 本帖最后由 yzc2002 于 2006-7-21 12:24 编辑 ]

liubinbj

原帖由 unicorns 于 2006-7-21 12:07 发表
低个头很难吗.奇怪.
其实有的时候只是知与不知,先知与后知的区别.
低个头也不代表自己的水平比别人差啊.

大概是针对我的吧，那我来回。

你可能没看到一个叫“知错能改”的帖子（后被版主移动到别处了），在确认了connet的算法比我的2分法强的时候，我立即发了这个新贴，承认了我的2分算法不如connet查表快，到现在我也是肯定connet的发布的，在“知错能改”的帖子里我已经低头了，2分法确实不够快，但那种算法确实是我的不够成熟的原创。

即使connet的算法快，也不代表别人不能改进不是？追求速度的极限没什么过错吧。我一扩展connet给出的算法立即有人说是一样的，我没说不一样，我只求速度快。既然他这个线索是对的，我沿着这个线索继续发展一下怎么就不可以。难道你写一篇论文就不引用别人的成果？很多科技发展总是基于前人的工作一步步走下来的。

assiss

原帖由 yzc2002 于 2006-7-21 12:20 发表
另外,你好象没看懂我(yuxh)那个用例吧?

原来你是yuxh的马甲？难怪。

yzc2002

原帖由 assiss 于 2006-7-21 13:06 发表


原来你是yuxh的马甲？难怪。

这个我早就宣布过了
后来你也来得少了，我也不常来了。

冥王星

学习一下！

achun.shx

大家用空间换时间确实是个好办法。
其实很多优秀的程序都这样干，
不过大家的热情竟然这么高，是在是让人摸不着头脑。

lenovo

原帖由 assiss 于 2006-7-21 13:06 发表


原来你是yuxh的马甲？难怪。

晕，地球人都知道。

mailjzwu_1

学习学习！大家热情高阿！

ai4life

大家有必要这么高热情嘛！！！楼主的方法很普通啊

gamago

都别吵啦。
这个题目在这里很久以前就讨论过，不止一次。

网上有关于这个题目的总结性网页，大家不用闭 ...
assiss 发表于 2006-07-20 15:03

学习喽，呵呵。