本人第一次来论坛，看了几个帖子，其中有一个贴子很让我感兴趣，题目是《12个球的程序.....》,连接是https://www.bccn.net/Article/kfyy/cyy/jszl/200804/7191.html。那个帖子给出的代码非常清晰易懂，非常好的模拟了实际问题。但美中不足的是并没有给出称量的算法这个题目我在中学时期把它作为数学题目做过。我记得有2种大同小异的方案，那时我是用的穷举法得到答案，其实一开始就可以把所有的情况缩小到很小的范围。。我给出其中一个方法 。称量过程在代码中。

    言归正传，我发这个帖子的目的是想收集一些比较漂亮的算法，并不一定要完整的代码，几个函数或者直接用语言描述就可以了。算法能解决的问题各个方面都可以，最好和数学有点关系。也可以给出c语言编程时候的一些技巧。下面自己先发一个在其他论坛学到的算法来作为例子，(原帖http://bbs.)
unsigned fun(unsigned int x)
{      /******** 功能：计算x(x必须是32位的数,否则要修改下面的常数)的二进制位中1的个数 ********/
    const unsigned MASK1  = 0x55555555;
    const unsigned MASK2  = 0x33333333;
    const unsigned MASK4  = 0x0f0f0f0f;
    const unsigned MASK8  = 0x00ff00ff;
    const unsigned MASK16 = 0x0000ffff;

    x = (x & MASK1 ) + (x >> 1  & MASK1 );
    x = (x & MASK2 ) + (x >> 2  & MASK2 );
    x = (x & MASK4 ) + (x >> 4  & MASK4 );
    x = (x & MASK8 ) + (x >> 8  & MASK8 );
    x = (x & MASK16) + (x >> 16 & MASK16);
    return x;
}

如果int base[1<<16]；要的空间可能可能比较大吧，还有在初始化的时候也比较耗时间，循环的次数也不少啊。
不知道改成char base[1<<8]是不是要稍微好点，不过在get 函数中作4次加法和4次位与运算。如果不是特别的
常用的话，我想那个初始化有点耗时间。

----实际中我一般使用char base[1<<16]----
呵呵，char 还要 1<<16 ？

我找到的那个算法，一共就不到20次位运算和不到10次加法运算。
初始化中，2^16=65536次循环，一起要65536次比较，65536*2次加法，65536次转跳。这样可以运行 至少 100以上那个fun函数。一个程序应该调用这个函数不会这么多吧？

[ 本帖最后由 Windy0Winll 于 2010-8-26 18:17 编辑 ]

-----程序真的要用这个函数多次，那么用我的那种做法应该更合理----
这点我非常非常的赞同。

不过你给的那个函数还不如这样：
int fun(int n){ //最高位的符号位1不考虑。
    int s = 0 ;
    if ( 0==(n&=0x7fffffff) ) return 0;
    while( ++s,n&=n-1 )
            ;
    return s;
}
这样的函数要用循环来实现，有可能需要31次循环，每次循环也要比较，位运算，转跳，减法等。对于1的位数比较小的数，确实要快一点。

----你写的那个算法我很早前就见过，但是我从来没用过，就是因为它有一个固定的运算数量，实际并不理想。----
说的也是，不过我还是比较喜欢那个算法。如果要算64位的数，可以运行2次那个函数就可以了。或者重新写一个函数，
把 MASK1  = 0x5555555555555555ULL ,其它也对应改掉，还有 再加一个MASK32 = 0x00000000ffffffffULL;就可以了。
我喜欢的是那个算法，不是那个函数。


----如果你感兴趣可以在matrix67的博客上找一些资料----
 恩，先谢谢了。以前我也学习过一点点位运算，我去学习学习这些资料。

----给我选用的话，我会根据情况，但多数情况下我选用孔明的算法，或者用8位的弱化版本，或者最简单的循环，但绝对不使用网上流传的那种看起来很炫的代码，可读性差，----
  可读性差，我个人觉得这个跟对这个算法的熟悉度有关。如果一个简单的算法，但如果我不懂的话，读起代码来的话，也是很费力的。如果你真正理解了某个算法，一般情况应该也是能读懂代码的吧。

----hacker's delight 里面类似这种精妙的位运算算法比比皆是。。。----
恩 ,这是一本很好的书.