上学期学信息论这门课的时候，接触到了通信复杂度这个话题。我觉得这是一个非常有意思的领域。70年代时，姚期智老师也在这个领域作出了重要的成果。

借用Matrix67文章里的一段话，介绍一下通信复杂度的定义。

 通信复杂度（communication complexity）主要研究这么一类问题： A 持有数据 $x$ ， B 持有数据 $y$ ，他们想要合作计算某个关于 $x$ 和 $y$ 的二元函数值 $f(x, y)$ ，两人至少需要传输多少 bit 的数据才能算出$f(x, y)$的值？

下面举两个有趣的例子。这两个例子，都来自于课堂当中。前一个例子是往年的考试题，后一个例子是老师留下的思考题，不过没有留下解答。

注：下面约定两人中只要有一个人算出$f(x,y)$即算作完成计算。

Problem 1:

A和B分别持有一个不超过n的整数x和y。已知其中一个人手里的数是对方的2倍，现在要计算两人手中的数之和，要传送多少bit数据？

很明显存在$O(\log n)$的方案：A把他手里的数的二进制编码传给B,B就能完成计算了。

很快你会发现，用不着这么麻烦。A和B手里的数在二进制编码上，只有末尾0的个数不一样。实际上A只要把手中的数末尾0的个数告诉B就可以了。

由于末尾0的个数是$O(\log n)$的，编为二进制只要$O(\log \log n)$位即可。

不过，这个做法明显还没有充分利用条件。我们只用到了一个人手中的数是另外一个人的$2^k$倍，也就是说4倍,8倍,不知道是2倍,4倍还是8倍都可以用这个方案。而题目限定了只能是2倍，因此一定还有优化的空间。

还有更好的办法吗？

实际上,只要发2个bit就可以了。注意到二进制编码末尾0的个数相差1，因此A只要发出末尾0的个数除以4的余数，也就是二进制后两位，那么B就能知道他的数是A的一半还是两倍。

举个例子，A发来了11(3)，B的末尾0个数除以4的余数是2，那么B就知道他的数一定是A的一半。否则，A应该发来1才对。

到这里，发送1个bit的方案也就一目了然了：两个人末尾0的个数必然是一奇一偶，所以A的末尾0个数是奇数还是偶数，其实不必交流任何信息，B也能知道。

于是，A可以不用发出末尾0个数的二进制最后一位，也就是A只要发出：

x的二进制表示中末尾0的个数的二进制表示的倒数第二位

B就能完成计算。

只看结果，似乎这个方案的设计匪夷所思。然而其中的推理过程，每一步都顺理成章。

Problem 2:

现在考虑三个人的情况。如果现在有ABC三个人，每人有一个$n$位的二进制数，分别叫xyz。

不同的是，他们的数不是拿在手里，而是贴在额头上。

这也就是说，每个人知道另两个人的数是什么，却不知道自己的数是什么。

他们在互通信息的时候，只要一个人发出信息，另外两人都会收到。

对于3个0-1数码来说，可以定义众数。

也就是说，3个数码中出现了2个以上的0，众数就定义为0.否则，其中一定有2个以上的1，众数就定义为1.

更一般地，对于三个n位二进制数，众数定义为每一位分别取众数再连起来。举个例子，三个人手里的数分别是：

0011001

1101100

1001110

那么众数就是：

1001100

回到我们的题目。现在我们想要计算：x,y,z的众数中，1有奇数个还是偶数个？（例子中的答案是奇数个，因为有3个1）

很明显的办法是发$n$位：A把B头上的数发出来，那么B就知道了自己头上的数，从而知道了所有的信息。

能不能更快呢？

由于这个问题没有得到标准答案，我写一下我自己的解法。先说结论，2bit即可。

注意到若三个数码的众数是1，可以分为两种可能：三个数码都是1，或者两个是1，一个是0.

假设在n位中，前一种情况发生了p次，后一种情况发生了q次。题目要求的就是p+q的奇偶性。

我们先看如下方案，发送$2\log n$位：

A先看B和C头上的数，有多少位两人都是1？   将这个数a的二进制表示告诉大家

然后B看A和C头上的数，有多少位两人都是1？将这个数b的二进制表示告诉大家

最后C看A和B头上的数，有多少位两人都是1？将这个数c记在心里。

我们考察a+b+c的值。

如果有一位三个人都是1，那么三个人都会看到：另两个人头上这一位都是1，也就是这一位被算了三次。

如果有一位只有两人是1，那么只有一个人（这一位头上是0的那个）会看到另两个人头上这一位都是1，这一位被算了一次。

所以$a+b+c=3p+q$，它与$p+q$的奇偶性是一样的！于是C就能得到答案。

由于算奇偶性只要二进制的最后一位，所以A和B只要分别把a和b的二进制最后一位告诉大家，C就能知道答案了。我们只用了2bit

Open Question:

有没有1bit的方案？

惜字如金——通信复杂度问题二则