to 老学童

这种算法在火麒麟给的帖子里面有，甚至百度百科里面都有，我记得好像什么时候看到过，是个竞赛的题目，非常典型。浪费了一天的时间去琢磨，还不如直接上网查查算法改写一下。

那个临位相加的效率高不高的不好说，那要看算法的复杂度——那些东西早都还给老师了。我觉得，咱们不是科研人员，不用研究的那些算法的问题。嗯，本质上讲，我还是很懒的。那样写很容易理解，毕竟位运算是一种很基础的东西，也很容易扩展到类似的应用，原理我大概给你说一下，具体的算法，你可以参见火麒麟给的两个网址，比较成型的东西，可以拿来就用的。最后一种简化2的算法也可以实现，也可以应用到求m变量中的n个（n<=m）位置逻辑为1的数量。不过我能想到的方法很不成熟，需要构造2层以上得循环——这可不是一个好的结构。

临位相加，就是火麒麟给的第一个帖子中的简化1的原理。你可以这样理解，整数1在计算机中的存贮为w#1,0为W#0。那么就是说，当只有1位的时候，逻辑1的个数，就是W转换为int的数值。2位的情况是这样，00、01、10、11，这个时候，数字1的个数，就是这临近两位进行位运算加发的结果：0+0=00（整数0）,、0+1=01（整数1）、1+0=01（整数1）、1+1=10（整数2）。同理，4位就是2次临位相加，我们拿一个四位的为例，其他同理：设m0.0 bool 4，求1的个数可以分成2步：m0.0=m0.0+m0.1 m0.2=m0.2+m0.3 n=m0.0+m0.2 。运用字的逻辑运算一次处理多个，而每一次临位相加，都会使得运算的位数缩短(移位)，结果自然就是缩短循环了。而临近2个位的相加，我们完全可以用and+shr来实现。这样，32位其实只要有5次运算（32=2的5-1次方）就能实现我们需要的功能。

其实所有的原理，都在我写在程序前面那张表里面。后面在加上说明，你看这个表，自己列举几个实际的例子，应该好理解点。
[TABLE]步骤取位右移位数16位值（方便输入）说明
一2#0101_0101_0101_0101_0101_0101_0101_01011DW#16#55555555相邻的1位相加，a,b,c,d=0(a+b)0(c+d)[TR]
二2#0011_0011_0011_0011_0011_0011_0011_00112DW#16#33333333相邻的2位相加，0,a,0,b,=0(a+b)[/TR][TR]
三2#0000_1111_0000_1111_0000_1111_0000_11114DW#16#F0F0F0F相邻的4位相加，0,0,a,b,0,0,c,d=00(a+c)(b+d)[/TR][TR]
四2#0000_0000_1111_1111_0000_0000_1111_11118DW#16#FF00FF相邻的8位相加[/TR][TR]
五2#0000_0000_0000_0000_0000_0000_1111_111116DW#16#FF相邻的16位相加[/TR][/TABLE]

最后就可以直接转换为int了。

顺便说一下帖子中简化2的原理。简化2是从结果分析的（可以近似的理解不用for而是while，至于while高效可以分析伊默的程序，相当于去掉了无用的循环）所以算法的效率应该比前面那些都高。简化2的原理是模运算。32位需要判断的地址空间，最多1的个数是32，那么取32的模进行模运算就可以了。整数32用二进制表示100000，6位，每6位临位相加，再把最后的结果相加，转换为整数就是结果。模的概念很好理解，典型的date_and_time和s5time就是由模的概念组成的，比如星期，只有星期日-星期六，不会出现星期8。星期就是模，是说的一定范围内的数字。这个范围就叫做模。模运算的就是说无论怎么运算，结果也在模的范围之内。确切的概念的可以从百度上面找。什么概念的，没那么复杂，不过是为了交流而取了个名字，就好比：老学童，呵呵。