Как реализовать битовый набор в C?

Я использую class Bitset в Java, и я хотел бы сделать что-то подобное в C. Я полагаю, что мне придется делать это вручную как большинство вещей в C. Что было бы эффективным способом реализации?

byte bitset[] 

может быть

 bool bitset[] 

?

    CCAN имеет реализацию битового набора, которую вы можете использовать: http://ccan.ozlabs.org/info/jbitset.html

    Но если вы в конечном итоге реализуете его самостоятельно (например, если вам не нравятся зависимости от этого пакета), вы должны использовать массив int и использовать собственный размер компьютерной архитектуры:

     #define WORD_BITS (8 * sizeof(unsigned int)) unsigned int * bitarray = (int *)calloc(size / 8 + 1, sizeof(unsigned int)); static inline void setIndex(unsigned int * bitarray, size_t idx) { bitarray[idx / WORD_BITS] |= (1 << (idx % WORD_BITS)); } 

    Не используйте определенный размер (например, с uint64 или uint32), позвольте компьютеру использовать то, что он хочет использовать, и адаптироваться к нему с помощью sizeof.

    Никто не упомянул о том, что рекомендует C FAQ, который представляет собой кучу добрых-старых макросов:

     #include  /* 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) 

    (через http://c-faq.com/misc/bitsets.html )

    Ну, байтовый битсет [] кажется немного вводящим в заблуждение, нет?

    Используйте битовые поля в структуре, а затем вы можете поддерживать коллекцию этих типов (или использовать их в любом случае по своему усмотрению)

     struct packed_struct { unsigned int b1:1; unsigned int b2:1; unsigned int b3:1; unsigned int b4:1; /* etc. */ } packed; 

    Я рекомендую свою библиотеку BITSCAN C ++ (версия 1.0 только что была выпущена). BITSCAN специально ориентирован на быстрые операции с битами. Я использовал его для реализации комбинаторных задач NP-Hard с использованием простых неориентированных графов, таких как максимальная клика (см. Алгоритм BBMC , для ведущего точного решателя).

    Сравнение BITSCAN и стандартных решений STL bitet и BOOST dynamic_bitset доступно здесь: http://blog.biicode.com/bitscan-efficiency-at-glance/

    Вы можете дать мой код PackedArray попробовать с bitsPerItem 1 .

    Он реализует контейнер произвольного доступа, где элементы упаковываются на уровне бит. Другими словами, он действует так, как будто вы можете манипулировать uint9_t или uint17_t :

     PackedArray principle: . compact storage of <= 32 bits items . items are tightly packed into a buffer of uint32_t integers PackedArray requirements: . you must know in advance how many bits are needed to hold a single item . you must know in advance how many items you want to store . when packing, behavior is undefined if items have more than bitsPerItem bits PackedArray general in memory representation: |-------------------------------------------------- - - - | b0 | b1 | b2 | |-------------------------------------------------- - - - | i0 | i1 | i2 | i3 | i4 | i5 | i6 | i7 | i8 | i9 | |-------------------------------------------------- - - - . items are tightly packed together . several items end up inside the same buffer cell, eg i0, i1, i2 . some items span two buffer cells, eg i3, i6 

    Как обычно, вам нужно сначала решить, какие операции вам нужно выполнять на вашем битете. Возможно, какое-то подмножество того, что определяет Java? После этого вы можете решить, как лучше всего его реализовать. Вы можете конечно посмотреть источник для BitSet.java в OpenJDK для идей.

    Сделайте массив массив unsigned int 64.

    Давайте будем гением компьютера.