C/C++ эффективный битовый массив

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

Вы можете использовать std :: bitset

int main() {
  const bitset<12> mask(2730ul); 
  cout << "mask =      " << mask << endl;

  bitset<12> x;

  cout << "Enter a 12-bit bitset in binary: " << flush;
  if (cin >> x) {
    cout << "x =        " << x << endl;
    cout << "As ulong:  " << x.to_ulong() << endl;
    cout << "And with mask: " << (x & mask) << endl;
    cout << "Or with mask:  " << (x | mask) << endl;
  }
}