如何实现简单的位数组(bit array)

#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)

下面是一些简单的例子：

声明一个固定长度（50个bit）的位数组：

char bitarray[BITNSLOTS(50)];

设置位数组中的某一位：

BITSET(bitarray, 23);

检测某一位

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

求两个位数组的并集

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

求两个位数组的交集

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

下面是一个完整的例子，利用Sieve of Eratosthenes算法求素数：

#include <stdio.h>#include <string.h>#define MAX 10000int main(){    char bitarray[BITNSLOTS(MAX)];    int i, j;    memset(bitarray, 0, BITNSLOTS(MAX));    for(i = 2; i < MAX; i++) {        if(!BITTEST(bitarray, i)) {            printf("%dn", i);            for(j = i + i; j < MAX; j += i)                BITSET(bitarray, j);        }    }    return 0;}