林小峰同学在其博客上贴了一道智力题，我上次回复没仔细看题，还以为是老掉牙的称8个球的问题。刚才仔细一看原来不是，这题以前还真没见过。于是就仔细想了想，抱着“不走寻常路”的观念，花了15分钟本以为想出乐，结果发现其实不对。题目如下：

题目：有12个乒乓球特征相同，其中只有一个重量异常，现在要求用一部没有砝码的天平称三次，将那个重量异常的球找出来。 （尤其特别注意：是异常，但不知是轻了还是重了）

对比网上的答案又看了一下，发现以下两个问题：

1. 其实分4组是不可能称出来的。

2. 三步其实最多能从13个球中称出。

网上流传甚广的解法如下：

把12个球编成1，2……12号，则可设计下面的称法：

左盘 右盘
第一次 1，5，6，12 2，3，7，11
第二次 2，4，6，10 1，3，8，12
第三次 3，4，5，11 1，2，9，10

此法的巧妙之处在于，通过合理的安排三次称重中球的位置，使得不同的结果能够得出不同的结论。这似乎涉及到信息论的知识（香农老先生好伟大啊……） 。

如果我们把它抽象成数学来看，大体如下：

用一个12bit的数表示称量状态，第N（1<=N<=12）bit表示第N个球被选中来进行称量。

首先，我们必须分三组来称量，直观上来看，是因为3^3=27刚好大于12x2=24，通过裁剪我们有可能把27削减到24。而如果分4组，3^4=81，削减到24的可能性很小。（谁能给出准确证明？）

其次，若分三组的话，我们如何通过合理设计把结果可能性削减到24？最基本的一个要求不能动：就是每个球必须放过，即：每一位都至少被置过一次1，这样才能保证不会出现三次称量都平衡的局面。这样也把27削减到了26。还有两种情况应该也能排除，那就是三次均为左或三次均为右的情况，这很简单，我们只要保证一个球不是三次都在左边或右边就行。

好了，我们把上面的要求转化成数学。先是每次放法的数学表示，可以用这样一个二维数组，里面有三组元素，代表三次称量，每组又有两个元素，第一个代表该次称量天平左边放入的球，第二个代表右边的球。上面的两个要求就变成了：

u12_t balls[3][2] ;

balls[0][0] | balls[0][1] | balls[1][0] | balls[1][1] | balls[2][0] | balls[2][1]==0xfff

balls[0][0] & balls[1][0] & balls[2][0] == 0

再往下走就是对这些数的筛选和判断了。筛选很简单，每个数必须是12位上的某4位置了1，其它8位均为0。这样的数共(12x11x10x9)/(4x3x2)=495个。我们每次要从里面挑6个，来进行判断，判断的方法是：对于上面说的24种情况，其中一半又是对称。这12种情况中每个情况下得出的结果必须是12位上只有一位置1的数，它就表示处于该位上的球是异常球，而且还不能重复。操作过程如下：

1. 对于每组元素，要么取其第一元素，要么取其第二个元素，要么取这两个元素的同或（至于为什么是同或，就留给您思考了）。

2. 把上面得到的三个结果进行按位与。

3. 遍历完这12种情况，把每次得到的结果或起来。若是0xfff，符合要求；否则淘汰。

这样，一个程序的雏形基本上就出来乐，如果不再进行优化的话，大概要进行237832111537020次计算。有兴趣的同学可以用Python来完成整个程序。（友情提示：Python里面的位操作和C里面的一样。）