二进制的二三事 - Parallel Labs

二进制是计算机的自然语言，逻辑门中神奇的0/1组合犹如那起起伏伏的“滴答”之声构成了曼妙的电子世界。不仅如此，二进制中的0和1往往也是我们解决实际问题的利器。

Task1：求一个固定长度集合所有子集

最直观的方法就是穷举：对集合中的每个元素来说它要么在当前子集中，要么不在当前子集中，以此依次类推穷举出所有可能的值。如果我们用0表示该元素在当前子集中，用1表示该元素不在当前子集中，我们就可以用一串0/1序列来表示当前的子集。

例如集合{a, b, c, d, e}中的子集{a, b, c}可以用“11100”来表示，子集{c, d, e}可以用“00111”来表示，空子集{}可以用“00000”来表示。

那么对任意固定长度的集合a[n]，我们可以从a[0]开始穷举a[0]在子集中和a[0]不在子集中两种情况，再依次类推从a[1]开始一直穷举到a[n-1]为止。于是我们可以得到一个很直观的递归程序：

void sub_sets_recu(int index, int length, char *array, char *bits)
{
	int j = 0;

	if (index >= length) {
		for (j = 0; j < length; j++) {
			if (bits[j] == '1') {
				printf("%c", array[j]);
			}
		}
		printf("\n");
	}
	else {
		bits[index] = '1';
		sub_sets_recu(index+1, length, array, bits);
		bits[index] = '0';
		sub_sets_recu(index+1, length, array, bits);
	}
}

但是递归版本的缺点就是需要一个额外的数组bits来存储0/1序列，那么有没有办法改进呢？我们可以先试试把递归改成迭代的方式会不会有效果。

迭代的关键就在于明白你究竟要做哪些计算步骤，为此我们可以先画出递归函数的Execution Tree来看看：

— ○
| 0/ \1
| ○ ○
| 0/ \1 .
| ○ ○ .
n层 . . .
| . .
| . .
| / \ / \
| ○ ○ ○ ○
—

上图中，第i层的值为1的边来表示a[i]在子集中，值为0的边表示a[i]不在子集中，那么从根节点到所有叶子节点所经过的边的组合就是所有可能的子集组合，例如从根节点到最左叶子节点的组合为“00000”，即空子集。根据完全二叉树的性质，第n层有2^n个节点，所以共有2^n个不同的子集。既然所有的解都已经存储在这颗二叉树中，那么我们自然就可以依此构建一个遍历所有路径的迭代算法。

思路是有了，但是实际编码中我们需要用到一个跟二进制编码相关的trick了。我们知道任意一个十进制的数是可以用二进制来表示的，反过来我们也可以用十进制来表示二进制啊，“用二进制来思考”其实就是这个trick的关键。既然我们的解是“00000”~“11111”，那么它们自然可以用十进制的0~31来表示。很自然的我们就可以想到如果我们依次遍历0~31这些数，根据它们二进制值中每一位的值是0还是1即可确定当前元素是否在子集中。关于二进制的位操作等相关知识Matrix67的blog[1]有一个系列写的很不错，在此就不再赘述。

void sub_sets_iter(int length, char *array)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < (1<<length); i++) {
		for (j = 0; j < length; j++) {
			if ((i & (1<<j)) != 0) {
				printf("%c", array[j]);
			}
		}
		printf("\n");
	}
}

再加上测试用的main函数：

int main()
{
	char a[5] = {'a','b','c','d','e'};
	char b[5];
	int i;

#ifdef USE_RECU
	for (i = 0; i < 10000000; i++) {
		sub_sets_recu(0, 5, a, b);
	}
#else
	for (i = 0; i < 10000000; i++) {
		sub_sets_iter(5, a);
	}
#endif
	return 0;
}

好，代码全写完了，当然应该比试比试两个算法孰优孰劣。测试平台是：cygwin + gcc 3.4.4 + Core2 Duo T7300@2.0GHz

在测试时已经把两个算法中的printf给注释掉了，只比拼速度。先把gcc的优化设成-O0看看：

$ time ./recu.exe

real    0m8.847s
user    0m8.811s
sys     0m0.046s

$ time ./iter.exe

real    0m5.093s
user    0m4.999s
sys     0m0.046s

再看看gcc -O3的结果：

$ time ./recu_o3.exe

real    0m8.285s
user    0m8.234s
sys     0m0.031s

$ time ./iter_o3.exe

real    0m1.887s
user    0m1.796s
sys     0m0.031s

结果显示迭代算法优于递归算法。感兴趣的朋友可以反汇编一下编译器优化后的代码，看看为什么迭代算法优化后能快那么多。关于递归与迭代已经有很多分析了，简单说来递归更加直观易懂，但是栈的开销比较大；迭代的算法不容易一开始就想出来，但是一般来说效率更高。从编译器的角度来讲，部分的编译器能把相对简单的递归算法转化成迭代算法，因为递归的算法对编译器来说是更友好的算法，更易于在此基础上做更多的优化。从体系结构的角度来讲，递归算法更易于发挥CPU流水线的特点让多步运算同时执行，而某些特定的架构，例如GPU就没有对递归提供有效的硬件支持，因为栈空间是一个大问题。

Task2：小白鼠试毒药问题

实验室里有1000个一模一样的瓶子，但是其中的一瓶有毒。可以用实验室的小白鼠来测试哪一瓶是毒药。如果小白鼠喝掉毒药的话，会在一个星期的时候死去，其他瓶子里的药水没有任何副作用。请问最少用多少只小白鼠可以在一个星期以内查出哪瓶是毒药？

这个问题关键是跳出思维，并不是说瓶子和小白鼠必须一一对应，然后我们用1000只小白鼠，每只各试一瓶药水，等一个礼拜然后出结果。其实我们仔细想想，小白鼠试毒只有两种结果，非“死”即“生”，又是一个0/1状态。很显然我们可以再次构建一个0/1组成的二叉树，由此即可表示不同的试毒结果。假设我们需要n个小白鼠，那么2^n-1应大于等于1000（因为有1000种可能的结果，减一是指要除去小白鼠全部不死的情况 — 多谢danqi指正），那么最小的n就是10了。

总结

解决此类问题的关键在于找到能用0/1表示的状态，然后想办法用0/1组成的二进制数来表示不同的结果，从而达到节省存储空间，提高解题效率的目的。

二进制真是神奇，文章的最后附一张0和1构成的Fibonacci数列（来自[2]）：

推荐订阅源

Parallel Labs

Task1：求一个固定长度集合所有子集

Task2：小白鼠试毒药问题

总结

相关文献