我也贴个题目，效率要高

stonemason

1. 
   
2. typedef unsigned long long u64;
   
3. 
   
4. #define m1 ((u64)0x5555555555555555)
   
5. #define m2 ((u64)0x3333333333333333)
   
6. 
   
7. unsigned int popcount(const u64 b)
   
8. {
   
9.         unsigned int n;
   
10.         const u64 a = b - ((b >;>;1 ) & m1);
    
11.         const u64 c = (a & m2) + ((a >;>; 2) & m2);
    
12.         n = ((unsigned int)c) + ((unsigned int)(c >;>; 32));
    
13.         n = (n & 0x0f0f0f0f) + ((n >;>; 4) & 0x0f0f0f0f);
    
14.         n = (n & 0xffff) + (n >;>; 16);
    
15.         n = (n & 0xff) + (n >;>; 8);
    
16.         return n;
    
17. }

复制代码

看花眼了，呵呵。

forest077

虽然没有仔细研究，但是可以不用循环，真是N啊。两个算法都N精妙，PFPF。

win_hate

[quote]原帖由 "forest077"]虽然没有仔细研究，但是可以不用循环，真是N啊。两个算法都N精妙，PFPF。[/quote 发表：


forest 兄， 我来深究一下。

方法1：
很妙。 实际上方法 1 在循环中的每一步，即 b &= b-1 的作用是去掉最右面的一个1，n 记数一次。到 b 变为 0 的时候，n 就记住了有多少个 1。循环的次数是 b中含1的个数，即返回值了。在多数情况下，比用移位的方法快多了。

方法2：
更妙：该方法采用的是并行计算的方式。

a = b - ((b >;>;1 ) & m1);

从左到右， 每两位为一组，进行上述操作后，每组的二进制值为操作前含1的个数。实际上，上述操作对每个组，无外乎:
xy = 00, 01, 10, 11
进行了如下操作：
xy - ((xy>;>;1) & 01)
得到相应的：
00, 01, 01, 10
正好是00, 01, 10, 11中1的个数。
然后？ 然后把这些个数加起来就完了，加的时候尽量用并行的方式，相对简单，我就不说了，请看代码。

在b含1的个数很少的时候，方法1比2要快，但多数情况下，方法2快。因为采用了并行的方法，所以方法2在b的位数越大的时候，优势也越大。

至于我说的查表，那是头脑简单的方法，实际效果应该比1好，比2差，但对64位（long long, 假64）来讲， 差不了太多。我没有仔细对比过。

就说这么多了。

哦， stonemason, 你的这两个方法是那里找到的啊？可以提供连接或更多资料吗，win_hate 不胜感谢！

forest077

如果是64位的话，按照概率平均会出现32个1，方法1就是32次循环，平均运行96次+,-法运算和32次按位与运算。方法2固定是6次位移运算，4次按位与运算，6次加减法运算，位数越多，方法2比起方法1 的效率越高，当然一般是受到机器位数的限定，不可能有十分多的位数，unsigned long long也只是某些机器才能提供。
bingbingnorth的算法固定运行64次位移，64次按位与，192次加减法运算，效率最低。如果要我来设计算法，也只能想出这种来了。

win_hate

查表的方法也是固定时间的。具体做法如下，你得先做一个256项的表(数组)，记录每个byte 中1的个数，这算是预计算，用什么方法算就不管了。这个表要放到源码里。

然后，在对 64 位整数进行 popcount的时候，把这个 64 bit 的整数割成 8 个byte， 分别查表，求和。主要部分为 8 个查表操作和 8 个 加法。

这个算法的好处是简单、易懂，效率也不错。

win_hate

[quote]原帖由 "forest077"]如果是64位的话，按照概率平均会出现32个1，方法1就是32次循环，平均运行96次+,-法运算和32次按位与运算。方法2固定是6次位移运算，4次按位与运算，6次加减法运算，位数越多，方法2比起方法1 的效率越高，当然一般是..........[/quote 发表：



在 32 位的机器上，实际上硬件是无法进行直接的 64 位与运算及移位运算的，long long 对程序员来说是 64 位，对机器来讲就不一定了。所以算法 2 在 32 位机器上效率要比看上去的低一些。

罗格纳

查表的时间效率最高，空间效率最低

第2中实质上就是一种查表，只不过分块的大小不同，算法比较巧妙

win_hate

原帖由 "罗格纳" 发表：
查表的时间效率最高，空间效率最低

第2中实质上就是一种查表，只不过分块的大小不同，算法比较巧妙

算法2 是查表么？ 呵呵，没看出来。