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

mik

这样做没什么意义吧~

适当则可了吧

assiss

啥叫算法，啥叫程序，唉。

liubinbj

原帖由 mik 于 2006-7-20 18:01 发表


这样做没什么意义吧~

适当则可了吧

存脆为了速度，只不过我的长了点，呵呵，其实都是查表啊，谈不上算法了。

liubinbj

略微修改一下代码,会看起来简短些

1. 
   
2. unsigned char table[]={
   
3. 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,
   
4. 3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,
   
5. 3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,
   
6. 4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,
   
7. 3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,
   
8. 6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,
   
9. 4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,
   
10. 6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,
    
11. 3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,
    
12. 4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,
    
13. 6,7,6,7,7,8,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,
    
14. 4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,
    
15. 4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,
    
16. 4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,
    
17. 6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,
    
18. 7,5,6,6,7,6,7,7,8,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    
19. 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,
    
20. 5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,3,4,
    
21. 4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,
    
22. 7,6,7,7,8,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,
    
23. 6,7,7,8,6,7,7,8,7,8,8,9,1,2,2,3,2,3,3,4,2,3,3,4,3,
    
24. 4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,
    
25. 4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,
    
26. 7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,
    
27. 4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,
    
28. 5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,2,3,3,4,3,4,4,5,3,4,
    
29. 4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,
    
30. 5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,
    
31. 6,7,7,8,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,
    
32. 6,6,7,5,6,6,7,6,7,7,8,4,5,5,6,5,6,6,7,5,6,6,7,6,7,
    
33. 7,8,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,2,3,3,4,3,4,4,
    
34. 5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
    
35. 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,
    
36. 6,6,7,6,7,7,8,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,
    
37. 5,6,5,6,6,7,5,6,6,7,6,7,7,8,4,5,5,6,5,6,6,7,5,6,6,
    
38. 7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,3,4,4,5,
    
39. 4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,
    
40. 7,7,8,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,
    
41. 7,8,6,7,7,8,7,8,8,9,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,
    
42. 8,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,5,6,6,7,6,7,7,8,
    
43. 6,7,7,8,7,8,8,9,6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,1,
    
44. 2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,
    
45. 4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,
    
46. 5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,
    
47. 4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,
    
48. 5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,
    
49. 7,8,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,
    
50. 6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
    
51. 4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,3,4,4,5,4,5,5,6,4,
    
52. 5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,4,5,
    
53. 5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,
    
54. 8,7,8,8,9,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,
    
55. 4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,
    
56. 6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,3,4,4,5,4,5,
    
57. 5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,
    
58. 8,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,
    
59. 6,7,7,8,7,8,8,9,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,
    
60. 5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,4,5,5,6,5,6,6,7,5,6,
    
61. 6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,4,5,5,
    
62. 6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,8,
    
63. 7,8,8,9,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,6,7,7,8,7,
    
64. 8,8,9,7,8,8,9,8,9,9,10,2,3,3,4,3,4,4,5,3,4,4,5,4,5,
    
65. 5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,
    
66. 6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
    
67. 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,
    
68. 6,6,7,6,7,7,8,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,
    
69. 6,7,6,7,7,8,6,7,7,8,7,8,8,9,3,4,4,5,4,5,5,6,4,5,5,
    
70. 6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,4,5,5,6,
    
71. 5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,8,7,
    
72. 8,8,9,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,
    
73. 7,8,6,7,7,8,7,8,8,9,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,
    
74. 9,6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,3,4,4,5,4,5,5,6,
    
75. 4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,4,
    
76. 5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,
    
77. 7,8,7,8,8,9,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,
    
78. 7,6,7,7,8,6,7,7,8,7,8,8,9,5,6,6,7,6,7,7,8,6,7,7,8,
    
79. 7,8,8,9,6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,4,5,5,6,5,
    
80. 6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,8,7,8,
    
81. 8,9,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,6,7,7,8,7,8,8,
    
82. 9,7,8,8,9,8,9,9,10,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
    
83. 6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,6,7,7,8,7,8,8,9,7,
    
84. 8,8,9,8,9,9,10,7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
    
85. };
    
86. 
    
87. int bitcount(unsigned int m)
    
88. {
    
89.     unsigned n;
    
90.     n = table[m & 0x7FF];
    
91.     n+= table[m>>11 & 0x7FF];
    
92.     n+= table[m>>22 & 0x3FF];
    
93.     return n;
    
94. }
    

复制代码

benwood068

好贴。。。。。版主用心了

isjfk

我无语......

yuxh

liubinbj 的程序思想上与楼主没有差异（都是穷举），但用这么大的数组。。。
程序的时间与空间应该有个合理的可接受的比例，这个比例严重失调啊！
偷颗白菜犯得着用大炮轰么？

caibird3rd

原帖由 yuxh 于 2006-7-21 08:44 发表
liubinbj 的程序思想上与楼主没有差异（都是穷举），但用这么大的数组。。。
程序的时间与空间应该有个合理的可接受的比例，这个比例严重失调啊！
偷颗白菜犯得着用大炮轰么？

单纯追求算法的精美是一种误区
有时候看起来最笨的办法也许在某些方面是最好的
以前看过一个帖子，讲google的高手追求的是如何用最简单的办法最有效的解决问题

liubinbj

原帖由 yuxh 于 2006-7-21 08:44 发表
liubinbj 的程序思想上与楼主没有差异（都是穷举），但用这么大的数组。。。
程序的时间与空间应该有个合理的可接受的比例，这个比例严重失调啊！
偷颗白菜犯得着用大炮轰么？

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

注意到你曾经提到过这个用例：
例如:在n!中2的因子的个数=n-(n的二进制中1的个数)
如:10！2的因子个数为2、6、10各1个，4两个，8三个，所以共有3+2+3=8，也=10-2
100=(1100100), 所以100！中2的因子个数为100-3=97,等等

有没有考虑到n!有10万个bit，而且循环计算n+1,n+2...的情况？这种情况也许你会考虑一下我后给出的方法。

[ 本帖最后由 liubinbj 于 2006-7-21 11:36 编辑 ]

unicorns

低个头很难吗.奇怪.
其实有的时候只是知与不知,先知与后知的区别.
低个头也不代表自己的水平比别人差啊.

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