Comment implémenter un bitset en C?

Question

J'ai utilisé la classe Bitset en Java et je voudrais faire quelque chose de similaire en C. Je suppose que je devrais le faire manuellement comme la plupart des choses en C. Qu'est-ce qu'un moyen efficace de mettre en œuvre?

byte bitset[] 

peut-être

bool bitset[] 

?

Answer 1

CCAN a une implémentation bitset vous pouvez utiliser: http://ccan.ozlabs.org/info/jbitset.html

Mais si vous finissez par la mise en œuvre vous-même (par exemple, si vous ne voulez pas les dépendances sur ce paquet), vous devez utiliser un tableau de ints et utiliser la taille native de l'architecture informatique:

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

ne pas utiliser une taille spécifique (par exemple avec uint64 ou uint32), laissez l'utilisation de l'ordinateur ce qu'il veut utiliser et adapter à qu'utiliser sizeof.

Answer 2

Eh bien, l'octet bitset [] semble un peu trompeur, non?

Utilisez des champs de bits dans une struct et vous pouvez maintenir une collection de ces types (ou les utiliser autrement comme bon vous semble)

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

Answer 3

Faites un tableau de unsigned int 64.

Answer 4

Comme d'habitude, vous devez d'abord décider quel type d'opérations vous devez effectuer sur votre bitset. Peut-être un sous-ensemble de ce que Java définit? Après cela, vous pouvez décider de la meilleure façon de l'implémenter. Vous pouvez certainement regarder la source de BitSet.java dans OpenJDK pour des idées.

Answer 5

Personne mentionné que la FAQ C recommande, ce qui est un tas de bons vieux macros:

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

(via http://c-faq.com/misc/bitsets.html)

Answer 6

Vous pouvez donner mon code PackedArray un essai avec un bitsPerItem de 1.

Il implémente un conteneur d'accès aléatoire dans lequel les éléments sont compressés au niveau du bit. En d'autres termes, il agit comme si vous étiez en mesure de manipuler, par exemple, uint9_t ou uint17_t tableau:

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, e.g. i0, i1, i2 
    . some items span two buffer cells, e.g. i3, i6 

Answer 7

Je recommande ma BITSCAN C++ library (version 1.0 vient d'être publié). BITSCAN est spécifiquement orienté pour les opérations de bitscan rapides. Je l'ai utilisé pour implémenter des problèmes combinatoires NP-Hard impliquant de simples graphes non orientés, tels que la clique maximale (voir l'algorithme BBMC, pour un solveur précis).

Une comparaison entre BITSCAN et solutions standard STL BITSET et BOOST dynamic_bitset est disponible ici: http://blog.biicode.com/bitscan-efficiency-at-glance/