comp.lang.c FAQ 列表· 问题 20.8

问如何实现位集或位数组？

答使用char或int类型的数组，并使用一些宏来访问数组中正确单元中的目标位。这里有一些可与char:

#include <limits.h>		/* for CHAR_BIT */

#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
#define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)

（如果您没有<limits.h>，请尝试使用 8 来代替CHAR_BIT.)

类型的数组配合使用的简单宏。这里有一些使用示例。声明一个 47 位数的“数组”

	char bitarray[BITNSLOTS(47)];

设置第 23 位

	BITSET(bitarray, 23);

测试第 35 位

	if(BITTEST(bitarray, 35)) ...

计算两个位数组的并集并将结果存放在第三个数组中（所有三个数组都按上述方式声明）

	for(i = 0; i < BITNSLOTS(47); i++)
		array3[i] = array1[i] | array2[i];

计算交集，请使用&来解决这个问题，而不是|.

作为更实际的例子，这是一个用于计算素数的埃拉托斯特尼筛法的快速实现

#include <stdio.h>
#include <string.h>

#define MAX 10000

int main()
{
	char bitarray[BITNSLOTS(MAX)];
	int i, j;

	memset(bitarray, 0, BITNSLOTS(MAX));

	for(i = 2; i < MAX; i++) {
		if(!BITTEST(bitarray, i)) {
			printf("%d\n", i);
			for(j = i + i; j < MAX; j += i)
				BITSET(bitarray, j);
		}
	}
	return 0;
}

另请参阅问题 20.7。

其他链接：更多解释

参考文献：H&S 第 7.6.7 节，第 211-216 页

关于此 FAQ 列表关于 Eskimo 搜索反馈版权

由托管