Поскольку вы упоминаете как C, так и C ++, я предполагаю, что ориентированное на C ++ решение, такое как boost::dynamic_bitset, может быть неприменимо, и вместо этого расскажу о низкоуровневой реализации 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 *. По-прежнему нет способа изменить размер набора битов в течение срока его службы, а также нет никаких проверок границ, но в этот момент добавить их будет несложно.