本人第一次来论坛，看了几个帖子，其中有一个贴子很让我感兴趣，题目是《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;
}

二进制中1的个数这样做其实并不快，只不过是个炫技罢了。

我一般这样做：

int base[1<<16];
for(i=1; i<(1<<16); i++)
{
    base[i] = base[i-i&-i] + 1;
}

然后查表：
int get(int x)
{
    return base[x>>16] + base[x&((1<<16)-1)];
}

随手打的，可能有小错误，但是思想就这样。

收到的鲜花

• Windy0Winll 于 2010-08-26 18:51 送鲜花  3朵   附言：好文章
• cosdos 于 2010-08-31 01:56 送鲜花  10朵   附言：好文章

最好函数参数改成unsigned int，不然遇到负数就程序崩溃，御坂提醒

收到的鲜花

• 卧龙孔明 于 2010-08-26 17:53 送鲜花  10朵   附言：谢谢~
• Windy0Winll 于 2010-08-26 18:18 送鲜花  3朵   附言：我很赞同

至于比较漂亮的算法，现想我想的肯定不全，我只列几个。

最大公约数算法(包括二进制GCD)
路径压缩的并查集
树状数组，二维树状数组
动态规划思想（主要推荐连通性状态压缩DP，矩阵优化，凸完全单调性等）
splay
最大流最小割思想
费用流思想
单纯型
SAP
Dancing Links
KMP/扩展KMP
后缀数组
Alpha-Beta及各种优化
New LCP
ZKW发明的新线段树（速度堪比树状数组）
A*/IDA*

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

2^16 = 65536，很小。初始化的时间一般可以忽略。
实际中我一般使用char base[1<<16], 无论时间空间都消耗不大。

不过我确实没测过char, int哪个快。
谁有兴趣可以测一下。
（之所以我在实践中都是用char，是因为在筛质数的时候开数组char更快。）

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

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

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

貌似用到这个函数的程序，我写过2个。
1个是usaco上的题，1个用于设计特殊的数据结构。
两个都需要大量使用这个操作，尤其是后者。
你要考虑一个界的，如果你的程序真的用这个函数不多，那么你完全可以这么做
int fun(int x)
{
    int ans = 0;
    while(x)
    {
        x -= x&-x;
        ans ++;
    }
    return ans;
}
既好写，实际效率不比楼主的那个程序慢多少（对于相对小的数更快）。
如果你的程序真的要用这个函数多次，那么用我的那种做法应该更合理。

收到的鲜花

• Windy0Winll 于 2010-08-26 18:54 送鲜花  2朵  

你写的那个算法我很早前就见过，但是我从来没用过，就是因为它有一个固定的运算数量，实际并不理想。但是那个思想很好（是log级别的），如果对于一个几万位的二进制数，当然那个算法应该大有作为。但是你也已经在前面限制了，只是一个32位以内的二进制数，那么真的，它只能看做一个炫技。

位运算上有许多思想很好的算法，如果你感兴趣可以在matrix67的博客上找一些资料。但是在32位环境中论一个不大的数的这些算法，只能用于理论，而不应该用于实践。

收到的鲜花

• Windy0Winll 于 2010-08-26 18:52 送鲜花  3朵   附言：好文章