c++ - C/C++ 高效位数组

Question

你能推荐一种有效/干净的方法来操作任意长度的位数组吗？

现在我正在使用常规的 int/char 位掩码，但是当数组长度大于数据类型长度时，这些位掩码不是很干净。

std vector<bool>我无法使用。

Answer 1

由于您提到了 C 和 C++，我将假设像 boost::dynamic_bitset 这样面向 C++ 的解决方案可能不适用，并改为讨论低级 C 实现。请注意，如果像 boost::dynamic_bitset 这样的东西适合你，或者你可以找到一个预先存在的 C 库，那么使用它们会比自己滚动更好。

警告:以下代码均未经过测试甚至编译，但应该非常接近您的需要。

首先，假设您有一个固定的位集大小 N。然后类似以下的工作:

typedef uint32_t word_t;
enum { WORD_SIZE = sizeof(word_t) * 8 };

word_t data[N / 32 + 1];

inline int bindex(int b) { return b / WORD_SIZE; }
inline int boffset(int b) { return b % WORD_SIZE; }

void set_bit(int b) { 
    data[bindex(b)] |= 1 << (boffset(b)); 
}
void clear_bit(int b) { 
    data[bindex(b)] &= ~(1 << (boffset(b)));
}
int get_bit(int b) { 
    return data[bindex(b)] & (1 << (boffset(b));
}
void clear_all() { /* set all elements of data to zero */ }
void set_all() { /* set all elements of data to one */ }

正如所写，这有点粗糙，因为它只实现了一个具有固定大小的全局位集。要解决这些问题，您需要从如下所示的数据结构开始:

struct bitset { word_t *words; int nwords; };

然后编写函数来创建和销毁这些位集。

struct bitset *bitset_alloc(int nbits) {
    struct bitset *bitset = malloc(sizeof(*bitset));
    bitset->nwords = (n / WORD_SIZE + 1);
    bitset->words = malloc(sizeof(*bitset->words) * bitset->nwords);
    bitset_clear(bitset);
    return bitset;
}

void bitset_free(struct bitset *bitset) {
    free(bitset->words);
    free(bitset);
}

现在，将之前的函数修改为采用 struct bitset * 参数相对简单。仍然无法在其生命周期内重新调整位集的大小，也没有任何边界检查，但此时两者都不会难以添加。