图13-1 3种深浅不同的阴影区域
第9章中描述的集合可以包含任意元素，因为这些元素只能通过客户程序提供的函数操作。与此相比，整数的集合灵活性较少，但使用很频繁，我们有理由将其实现为一个独立的ADT。Bit接口导出了操作位向量的函数，位向量可用于表示从0到N-1的整数集合。例如，256位的位向量可用于高效地表示字符的集合。
Bit接口提供了Set接口中大部分的集合操作函数，以及少量特定于位向量的函数。不同于Set接口提供的集合，由位向量表示的集合有一个定义明确的全集，即从0到N-1的所有整数构成的集合。因而，Bit接口可以提供Set接口所不能提供的函数，如集合的补集。
“位向量”这个名称揭示了这种整数集合的表示实质上是比特位的序列。尽管如此，Bit接口仍然只导出了一个不透明类型，来表示位向量：
〈bit.h 〉≡ #ifndef BIT_INCLUDED #define BIT_INCLUDED #define T Bit_T typedef struct T *T; 〈exported functions 142〉 #undef T #endif
一个位向量的长度是固定的，由Bit_new在创建位向量时指定：
〈exported functions
142〉≡
extern T Bit_new (int length);
extern int Bit_length(T set);
extern int Bit_count (T set);
Bit_new创建一个包含length个比特位的新向量，并将所有比特位都设置为0。该向量表示了从0到length-1的所有整数（包含0和length-1）。传递负的length值，是一个已检查的运行时错误。Bit_new可能引发Mem_failed异常。
Bit_length返回set中的比特位数，Bit_count返回set中1的数目（即置位的比特位数）。
向该接口中任何例程（Bit_union、Bit_inter、Bit_minus和Bit_diff除外）传递的T值为NULL，是已检查的运行时错误。
〈exported functions
142〉+≡
extern void Bit_free(T *set);
Bit_free释放*set并将*set清零。set或*set是NULL，则造成已检查的运行时错误。
集合中的各个元素（即向量中的各个比特位），通过下列函数操作：
〈exported functions
142〉+≡
extern int Bit_get(T set, int n);
extern int Bit_put(T set, int n, int bit);
Bit_get返回比特位n，因而测试了n是否在set中，即如果set中的比特位n是1，Bit_get将返回1，否则返回0。Bit_put将集合中的比特位n设置为bit，并返回该比特位的原值。如果n为负值或大于等于set的长度，或bit是0和1以外的值，都会造成已检查的运行时错误。
上述函数操作集合中的单个比特位，而以下的函数
〈exported functions
142〉+≡
extern void Bit_clear(T set, int lo, int hi);
extern void Bit_set (T set, int lo, int hi);
extern void Bit_not (T set, int lo, int hi);
将操作集合中连续的比特序列，即集合的子集。Bit_clear将lo到hi的所有比特位清零（包含比特位lo和hi），Bit_set将lo到hi的所有比特位置位（含比特位lo和hi），而Bit_not将lo到hi的所有比特位取反。如果lo大于hi，或lo/hi为负值，或lo/hi大于等于set的长度，都会造成已检查的运行时错误。
〈exported functions
142〉+≡
extern int Bit_lt (T s, T t);
extern int Bit_eq (T s, T t);
extern int Bit_leq(T s, T t);
如果s⊂t，Bit_lt返回1，否则返回0。如果s⊂t，s是t的一个真子集（proper subset）。如果s=t，Bit_eq返回1，否则返回0。如果s⊆t，Bit_leq返回1，否则返回0。对这三个函数来说，如果s和t的长度不同，则是已检查的运行时错误。
下列函数
〈exported functions
142〉+≡
extern void Bit_map(T set,
void apply(int n, int bit, void *cl), void *cl);
从比特位0开始，对set中的每一个比特位调用apply。n是比特位的编号，介于0和集合的长度减1之间，bit是比特位n的值，cl由客户程序提供。apply不同于传递到Table_map的函数，它可以改变set。如果对比特位n调用apply时，apply改变了比特位k，其中k>n，那么这一次修改在此后（对比特位k）调用apply时将是可见的，因为Bit_map必须就地处理集合中的各个比特位。如果要禁用这种语义，Bit_map需要在开始处理比特位之前，将位向量复制一份。
下列函数实现了4个标准的集合操作，这些操作已经在第9章中描述过。每个函数都返回一个新的集合，作为操作的结果。
〈exported functions
142〉+≡
extern T Bit_union(T s, T t);
extern T Bit_inter(T s, T t);
extern T Bit_minus(T s, T t);
extern T Bit_diff (T s, T t);
Bit_union返回s和t的并集，记作s+t，实际上是两个位向量的可兼容的按位或。Bit_inter返回s和t的交集s*t，它是两个位向量的按位与。Bit_minus返回s和t的差集s-t，是t的补集和s按位与。Bit_diff返回s和t的对称差s/t，它是两个位向量的按位异或。
该4个函数的参数s或t可以为NULL指针，但不能同时为NULL，NULL指针可以解释为空集。因而Bit_union(s, NULL)返回s的一个副本。这些函数总是返回非NULL的T值。如果s和t同时为NULL，或s和t的长度不同，均为已检查的运行时错误。这些函数可能引发Mem_Failed异常。
Bit_T是一个指向某个结构实例的指针，该结构实例包含了位向量的长度和向量本身：
〈bit.c 〉≡ #include <stdarg.h> #include <string.h> #include "assert.h" #include "bit.h" #include "mem.h" #define T Bit_T struct T { int length; unsigned char *bytes; unsigned long *words; }; 〈macros 145〉 〈static data 148〉 〈static functions 152〉 〈functions 145〉
length字段给出了向量中比特位的数目，而bytes指向一个至少包含<length / 8>个字节的内存区。这些比特位通过索引bytes来访问：字节bytes[i]中包含了从比特位8·i到8·i+7，其中比特位8·i是该字节的最低位。请注意，该约定只使用了每个字符的8个比特位，在字符位宽大于8的机器上，多余的比特位不会使用。
如果所有访问各个比特位的操作都使用相同的约定（就像Bit_get那样），那么也可以将位向量的各个比特位存储到其他类型（比如unsigned long）的数组中。Bit使用字符数组，这使得可以对Bit_count、Bit_set、Bit_clear和Bit_not使用表驱动的实现 [1] 。
一些操作（如Bit_union）同时操作所有比特位。对这些操作，访问位向量时，可通过words每次访问BPW个比特位，其中
〈macros
145〉≡
#define BPW (8*sizeof (unsigned long))
words必须指向整数个unsigned long，nwords计算了包含len个比特位的位向量所需要的unsigned long的数目 [2] ：
〈macros 145〉+≡ #define nwords(len ) ((((len ) + BPW - 1)&(~(BPW-1)))/BPW)
Bit_new在分配新的T实例时使用nwords：
〈functions
145〉≡
T Bit_new(int length) {
T set;
assert(length >= 0);
NEW(set);
if (length > 0)
set->words = CALLOC(nwords(length),
sizeof (unsigned long));
else
set->words = NULL;
set->bytes = (unsigned char *)set->words;
set->length = length;
return set;
}
Bit_new最多可能分配sizeof(unsigned long)-1个多余的字节。这些多余的字节必须清零，才能使下述函数正常工作。
Bit_free释放集合并将其参数清零，Bit_length返回length字段。
〈functions
145〉+≡
void Bit_free(T *set) {
assert(set && *set);
FREE((*set)->words);
FREE(*set);
}
int Bit_length(T set) {
assert(set);
return set->length;
}
Bit_count返回集合中成员的数目，即集合中值为1的比特位的数目。完全可以简单地遍历集合并测试每一个比特位，但使用每个字节中两个四比特位的“半字节”来索引一个表同样很容易（四比特位的半字节值共有16种可能性，因此该表只需要16个项，分别给出各个半字节值中置位的比特位数目）。
〈functions 145〉+≡ int Bit_count(T set) { int length = 0, n; static char count[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 }; assert(set); for (n = nbytes(set->length); --n >= 0; ) { unsigned char c = set->bytes[n]; length += count[c&0xF] + count[c>>4]; } return length; } 〈macros 145〉+≡ #define nbytes(len ) ((((len ) + 8 - 1)&(~(8-1)))/8)
nbytes宏计算了<len / 8>，它用于按比特遍历位向量的操作中。在上述函数中，循环的每次迭代计算集合的字节n中置位的比特位数目（将两个半字节中置位的比特位数目相加至length）。该循环可能访问一些多余的比特位，但因为Bit_new将多余的比特位初始化为0，因而不会破坏结果。
位向量中的比特位n，是字节n/8中的比特位n%8，在一个字节中，比特位的编号从0开始，从右向左递增，即最低位是比特位0，最高位是比特位7。Bit_get返回比特位n的值时，首先将字节n/8右移n%8位，然后只返回最右边的比特位：
〈functions 145〉+≡ int Bit_get(T set, int n) { assert(set); assert(0 <= n && n < set->length); return 〈bit n in set 147〉; } 〈bit n in set 147〉≡ ((set->bytes[n/8]>>(n%8))&1)
Bit_put使用类似的惯用法来设置比特位n的值：在bit为1时，Bit_put将1左移n%8位，将其结果按位或到字节n/8中。
〈functions 145〉+≡ int Bit_put(T set, int n, int bit) { int prev; assert(set); assert(bit == 0 || bit == 1); assert(0 <= n && n < set->length); prev = 〈bit n in set 147〉; if (bit == 1) set->bytes[n/8] |= 1<<(n%8); else set->bytes[n/8] &= ~(1<<(n%8)); return prev; }
如上述代码所示，在bit为0时，Bit_put需要将比特位n清零，首先构造一个掩码，其中的比特位n%8为0，其余比特位均为1，然后将该掩码按位与到字节n/8中。
Bit_set、Bit_clear和Bit_not都使用了类似的技术，分别将集合中某个范围内的比特位置位、清零、取反，但这些函数更为复杂，因为它们必须处理比特位范围跨越字节边界的情形。例如，如果set有60个比特位，
Bit_set(set, 3, 54)
将第一个字节中的比特位3到7置位，将字节1到5中的全部比特位置位，将字节6中的比特位0到6置位，其中字节编号从0开始。在图13-1中，这3个区域从右到左排列，分别对应3种深浅不同的阴影区域。
图13-1 3种深浅不同的阴影区域
字节7中的最高4位不使用，因而总是0。Bit_set的代码反映出了图中的3个区域：
〈functions 145〉+≡ void Bit_set(T set, int lo, int hi) { 〈check set, lo, and hi 148〉 if (lo/8 < hi/8) { 〈set the most significant bits in byte lo/8 148〉 〈set all the bits in bytes lo/8+1..hi/8-1 148〉 〈set the least significant bits in byte hi/8 148〉 } else 〈set bits lo%8..hi%8 in byte lo/8 149〉 } 〈check set, lo, and hi 148〉≡ assert(set); assert(0 <= lo && hi < set->length); assert(lo <= hi);
当lo和hi指的是不同字节中的比特位时，字节lo/8中被置位的比特位数目取决于lo%8：如果lo%8为0，那么该字节中所有比特位都被置位，如果它是7，那么只有最高位置位。这些以及其他可能的情况由掩码表示，存储在一个表中，通过lo%8索引
〈static data
148〉≡
unsigned char msbmask[] = {
0xFF, 0xFE, 0xFC, 0xF8,
0xF0, 0xE0, 0xC0, 0x80
};
将msbmask[lo%8]按位或到字节lo/8中，即可将适当的比特位置位：
〈set the most significant bits in byte
lo/8 148〉≡
set->bytes[lo/8] |= msbmask[lo%8];
在第二个区域中，每个字节中所有的比特位都将被设置为1：
〈set all the bits
in bytes lo/8+1..hi/8-1 148〉≡
{
int i;
for (i = lo/8+1; i < hi/8; i++)
set->bytes[i] = 0xFF;
}
hi%8确定了字节hi/8中哪些比特位被置位：如果hi%8为0，仅最低位置位，如果它是7，那么该字节中所有比特位均置位。同样，可以将hi%8用作索引，从一个表中选择适当的掩码，按位或到字节hi/8中：
〈set the least significant bits in byte hi/8 148〉≡ set->bytes[hi/8] |= lsbmask[hi%8]; 〈static data 148〉+≡ unsigned char lsbmask[] = { 0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F, 0x7F, 0xFF };
当lo和hi指向同一字节中的两个比特位时，可以将msbmask[lo%8]和lsbmask[hi%8]给出的掩码合并起来确定一个掩码，来指定需要置位的比特位。例如，
Bit_set(set, 9, 13)
将集合中第二个字节的比特位0到5置位，这可以通过与掩码0x3E按位或来完成，该掩码是msbmask[1]和lsbmask[5]按位与的结果。一般来说，这两个掩码重叠的部分，刚好对应于那些应该置位的比特位，因此处理该情形的代码是：
〈set bits lo%8..hi%8 in byte lo/8 149〉≡ set->bytes[lo/8] |= 〈mask for bits lo%8..hi%8 149〉; 〈mask for bits lo%8..hi%8 149〉≡ (msbmask[lo%8]&lsbmask[hi%8])
Bit_clear和Bit_not类似于Bit_set，都以类似的方式使用了msbmask和lsbmask。对Bit_clear来说，将msbmask和lsbmask取反 得到相应的掩码，分别按位与到lo/8和hi/8字节中即可。
〈functions 145〉+≡ void Bit_clear(T set, int lo, int hi) { 〈check set, lo, and hi 148〉 if (lo/8 < hi/8) { int i; set->bytes[lo/8] &= ~msbmask[lo%8]; for (i = lo/8+1; i < hi/8; i++) set->bytes[i] = 0; set->bytes[hi/8] &= ~lsbmask[hi%8]; } else set->bytes[lo/8] &= ~〈mask for bits lo%8..hi%8 149〉; }
Bit_not必须将lo到hi各比特位取反，这通过与适当掩码的按位异或来完成：
〈functions 145〉+≡ void Bit_not(T set, int lo, int hi) { 〈check set, lo, and hi 148〉 if (lo/8 < hi/8) { int i; set->bytes[lo/8] ^= msbmask[lo%8]; for (i = lo/8+1; i < hi/8; i++) set->bytes[i] ^= 0xFF; set->bytes[hi/8] ^= lsbmask[hi%8]; } else set->bytes[lo/8] ^= 〈mask for bits lo%8..hi%8 149〉; }
Bit_map对一个集合中的每个比特位调用apply。它将比特位编号、比特值及一个由客户程序提供的指针传递给apply。
〈functions 145〉+≡ void Bit_map(T set, void apply(int n, int bit, void *cl), void *cl) { int n; assert(set); for (n = 0; n < set->length; n++) apply(n, 〈bit n in set 147〉, cl); }
如上述代码所示，Bit_map所采用的比特位编号方式，与Bit_get和其他将比特位编号作为参数的Bit函数所暗含的比特位编号方式是相同的，Bit_map正是这样将各个比特位逐一传递给apply。每过8个比特位n/8的值改变一次，因此这很容易诱导我们将set->bytes[n/8]的值复制到一个临时变量，然后通过移位和掩码分别获取各个比特位。但这种改进违背了接口的语义：如果apply改变了一个它尚未“看到”的比特位，那么在对apply的后续调用中，apply应该可以看到该比特位的新值。
Bit_eq比较集合s和t，如果二者相等则返回1，否则返回0。这可以通过比较s和t中的相对应的各个unsigned long值来完成，在发现s≠t时即可停止循环：
〈functions
145〉+≡
int Bit_eq(T s, T t) {
int i;
assert(s && t);
assert(s->length == t->length);
for (i = nwords(s->length); --i >= 0; )
if (s->words[i] != t->words[i])
return 0;
return 1;
}
Bit_leq比较集合s和t，确定s是否等于t或是t的真子集。如果对s中每个置位的比特位，t中对应的比特位都是1，那么即有s⊆t。在集合方面，如果t的补集与s的交集为空，那么s⊆t。因而，如果s& ~t等于0，既有s⊆t，对s和t中的每个unsigned long来说，该关系仍然成立。如果对所有i，都有s->u.words[i]⊆t->u.words[i]，那么就有s⊆t。Bit_leq利用该性质，在结果已知的情况下停止比较。
〈functions
145〉+≡
int Bit_leq(T s, T t) {
int i;
assert(s && t);
assert(s->length == t->length);
for (i = nwords(s->length); --i >= 0; )
if ((s->words[i]& ~t->words[i]) != 0)
return 0;
return 1;
}
如果s是t的真子集，Bit_lt返回1，如果s⊆t且s≠t，那么有s⊂t，这可以通过检查以下两项来确认：对每个i，都有s->u.words[i]& ~t->u.words[i]等于0；至少有一个i，使得s->u.words[i]不等于t->u.words[i]：
〈functions
145〉+≡
int Bit_lt(T s, T t) {
int i, lt = 0;
assert(s && t);
assert(s->length == t->length);
for (i = nwords(s->length); --i >= 0; )
if ((s->words[i]& ~t->words[i]) != 0)
return 0;
else if (s->words[i] != t->words[i])
lt |= 1;
return lt;
}
实现集合操作s + t、s * t、s - t和s / t的函数可以按每次一个长整数来处理集合，因为其功能与比特位编号无关。这些函数还将T的NULL值解释为空集，但s或t中至少有一个不能为NULL值，这样才能确定结果集的长度。这些函数的实现类似，但有三个差别：当s和t指向同一集合时结果集不同，处理NULL参数的方式不同，处理两个非空集时形成结果的方式不同。这些函数的相似性通过setop宏捕获：
〈macros 145〉+≡ #define setop(sequal, snull, tnull, op ) \ if (s == t) { assert(s); return sequal ; } \ else if (s == NULL) { assert(t); return snull ; } \ else if (t == NULL) return tnull ; \ else { \ int i; T set; \ assert(s->length == t->length); \ set = Bit_new(s->length); \ for (i = nwords(s->length); --i >= 0; ) \ set->words[i] = s->words[i] op t->words[i]; \ return set; }
Bit_union可以代表这些函数：
〈functions
145〉+≡
T Bit_union(T s, T t) {
setop(copy(t), copy(t), copy(s), |)
}
如果s和t指向同一集合，则结果是该集合的一个副本。如果s或t二者之一为NULL，结果是另一个集合（必须不为NULL）的一个副本。否则，结果是一个集合，其中的各个unsigned long值是s和t中对应的unsigned long值按位或的结果。
私有函数copy会将其参数集合复制一份，它首先分配一个同样长度的新集合，而后将参数集合中的各个比特位复制到新的集合：
〈static functions
152〉≡
static T copy(T t) {
T set;
assert(t);
set = Bit_new(t->length);
if (t->length > 0)
memcpy(set->bytes, t->bytes, nbytes(t->length));
return set;
}
Bit_inter如果有任何一个参数是NULL，则返回空集，否则，它将返回一个集合，是其参数集合的按位与结果：
〈functions
145〉+≡
T Bit_inter(T s, T t) {
setop(copy(t),
Bit_new(t->length), Bit_new(s->length), &)
}
如果s为NULL，s-t是空集，但如果t为NULL，s-t等于s。如果s和t都不是NULL，s-t是t的补集 和s的按位与结果。当s和t指向同一Bit-T集合时，s-t为空集。
〈functions
145〉+≡
T Bit_minus(T s, T t) {
setop(Bit_new(s->length),
Bit_new(t->length), copy(s), & ~)
}
setop的第三个参数为& ~，这使得setop中的循环体在Bit_minus中展开后的结果如下所示：
set->words[i] = s->words[i] & ~t->words[i];
Bit_diff实现了对称差s / t，它是s和t的按位异或结果。当s为NULL时，s / t等于t，反之亦然。
〈functions
145〉+≡
T Bit_diff(T s, T t) {
setop(Bit_new(s->length), copy(t), copy(s), ^)
}
如上述代码所示，当s和t指向同一集合时，s / t为空集。
[Briggs and Torczon，1993]描述了一种集合表示，专门为大的稀疏集合设计，可以在常数时间内初始化集合。[Gimpel，1974]介绍了多道空间（spatially multiplexed）的集合，习题13.5描述了这种集合。
13.1 在稀疏集合中，大部分比特位都是0。修改Bit的实现，使之通过一些措施对稀疏集合节省空间，例如，不存储大量重复的0。
13.2 设计一个接口，支持[Briggs and Torczon，1993]描述的稀疏集合，并实现你的接口。
13.3 Bit_set使用下述循环
for (i = lo/8+1; i < hi/8; i++)
set->bytes[i] = 0xFF;
将从lo/8+1到hi/8的各字节的所有比特位置位。Bit_clear和Bit_not也有类似的循环。修改这些循环，在可能的情况下，对unsigned long（而不是字节）来清零、置位和取反。注意对齐约束。这项改变可能对某些应用程序的执行时间有可测量的改进，你能找到这样的应用程序吗？
13.4 假定Bit接口中的函数可以跟踪集合中置位的比特位的数目。Bit接口中哪些函数可以简化或改进？实现这种方案，并设计一个测试程序，来测定速度的提高。请确定在何种情况下，这种做法的好处可以抵消其成本。
13.5 在多道空间集合 中，比特位是按字存储的。在一台int位宽为32位的计算机上，一个包含N个unsigned int的数组，可以容纳32个N比特位的集合。该数组的每个比特位列都是一个集合。一个32位的掩码，仅在比特位i置位，即标识了列i处的集合。这种表示的一个好处是，通过操作这种掩码，一些操作可以在常数时间内完成。例如两个集合的并集，其掩码是两个源集合的掩码的并集。许多N位集合，可以共享同一个N字的数组，分配一个新集合时，只需从数组中分配一个空闲的位列即可（如果没有空闲位列，则需要分配新数组）。这种性质可以节省空间，但却使存储管理大大复杂化，因为对任意N值，实现都必须跟踪有空闲位列的N字数组。使用这种表示重新实现Bit接口。如果必须改变原接口，可以设计一个新接口。
[1] 实际上是基于数组的预计算实现。——译者注
[2] 不是length个比特位。——译者注