《编程珠玑（第2版•修订版）》—第1章1.4节实现概要

1.4　实现概要
由是观之，应该用位图或位向量表示集合。可用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合。例如，可以用如下字符串来表示集合{1, 2, 3, 5, 8, 13}：

0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
代表集合中数值的位都置为1，其他所有的位都置为0。

在我们的实际问题中，每个7位十进制整数表示一个小于1 000万的整数。我们使用一个具有1 000万个位的字符串来表示这个文件，其中，当且仅当整数i在文件中存在时，第i位为1。（那个程序员后来找到了200万个稀疏位，习题5研究了最大存储空间严格限制为1 MB的情况。）这种表示利用了该问题的三个在排序问题中不常见的属性：输入数据限制在相对较小的范围内；数据没有重复；而且对于每条记录而言，除了单一整数外，没有任何其他关联数据。

若给定表示文件中整数集合的位图数据结构，则可以分三个自然阶段来编写程序。第一阶段将所有的位都置为0，从而将集合初始化为空。第二阶段通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。第三阶段检验每一位，如果该位为1，就输出对应的整数，由此产生有序的输出文件。令n为位向量中的位数（在本例中为10 000 000），程序可以使用伪代码表示如下：

/ phase 1: initialize set to empty /
    for i = [0, n)
        bit[i] = 0
/ phase 2: insert present elements into the set /
    for each i in the input file
        bit[i] = 1
/ phase 3: write sorted output /
    for i = [0, n)
        if bit[i] == 1
            write i on the output file

（回想在前言中所提到的，for i=[0, n)表示在从0至n-1的范围内对i进行迭代。）

这个实现概要已经足以解决那个程序员的问题了。习题2、习题5和习题7描述了他会遇到的一些实现细节。