¿Cómo implementar un conjunto de bits en C?

He estado usando la clase Bitset en Java y me gustaría hacer algo similar en C. Supongo que tendría que hacerlo manualmente como la mayoría de las cosas en C. ¿Cuál sería una forma eficiente de implementar?

byte bitset[] 

tal vez

 bool bitset[] 

?

CCAN tiene una implementación de conjunto de bits que puede usar: http://ccan.ozlabs.org/info/jbitset.html

Pero si termina implementándolo usted mismo (por ejemplo, si no le gustan las dependencias de ese paquete), debe usar una matriz de entradas y usar el tamaño nativo de la architecture de la computadora:

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

No use un tamaño específico (por ejemplo, con uint64 o uint32), deje que la computadora use lo que quiere usar y adáptelo usando sizeof.

Nadie mencionó lo que recomienda la C FAQ, que es un montón de viejas macros:

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

(a través de http://c-faq.com/misc/bitsets.html )

Bueno, byte bitset [] parece un poco engañoso, ¿no?

Usa campos de bits en una estructura y luego puedes mantener una colección de estos tipos (o usarlos de otra manera como mejor te parezca)

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

Recomiendo mi biblioteca BITSCAN C ++ (la versión 1.0 acaba de ser lanzada). BITSCAN está específicamente orientado para operaciones rápidas de bitscan. Lo he usado para implementar problemas combinados NP-Hard que involucran gráficos simples no dirigidos, como la máxima camarilla (ver algoritmo BBMC , para un solucionador exacto líder).

Una comparación entre BITSCAN y soluciones estándar STL bitset y BOOST dynamic_bitset está disponible aquí: http://blog.biicode.com/bitscan-efficiency-at-glance/

Puede probar mi código PackedArray con un bitsPerItem de 1 .

Implementa un contenedor de acceso aleatorio donde los artículos se empaquetan a nivel de bit. En otras palabras, actúa como si pudieras manipular una uint9_t eg uint9_t o 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 

Como de costumbre, primero debe decidir qué tipo de operaciones necesita realizar en su conjunto de bits. ¿Tal vez algún subconjunto de lo que Java define? Después de eso, puede decidir cómo implementarlo mejor. Sin duda, puede ver la fuente de BitSet.java en OpenJDK para obtener ideas.

Conviértalo en una matriz de int sin firmar 64.

    Intereting Posts