Bit tournant beaucoup de bits en C

J’aimerais utiliser des indicateurs binarys pour représenter un ensemble mathématique en C, où “Le bit i est défini” signifie “l’élément i est dans l’ensemble”. Ceci est pratique car des opérations comme “union” et “intersection” sont faciles à implémenter (“|” et “&”). Cependant, je souhaite que mon ensemble puisse contenir plus de 32 éléments. De plus, je souhaite que mon code fonctionne sur les machines 32 et 64 bits.

Existe-t-il un moyen simple de manipuler plus d’un mot de bits en C? Y a-t-il une meilleure façon d’aborder cette tâche?

Oui, vous définissez simplement un tableau de vos entiers 32 bits. Ensuite, vous manipulez un élément spécifique du tableau.

Avec un ID de bit compris entre 0 et 255 inclus (par exemple), ce serait un tableau:

unsigned int bits[8]; 

Afin de trouver sur quel élément opérer:

 unsigned int index = bitId >> 5; // turns 0..255 into 0..31 

Pour obtenir les masques pour un ID de bit donné:

 unsigned int masks[] = { 0x0001, 0x0002, 0x0004, 0x0008, 0x0001, 0x0020, 0x0040, 0x0080, 0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000, 0x8000 }; unsigned int mask = masks[bitId & 0x1f]; 

Si vous avez le type uint32_t disponible dans votre implémentation, c’est probablement le moyen le plus sûr. Sinon, il existe des méthodes connues pour utiliser unsigned int aide de CHAR_BIT et sizeof afin de déterminer au moment de l’exécution la taille du tableau de masks et les valeurs à utiliser pour découvrir l’index de tableau et l’index de masque de bits.

Par exemple, cet extrait de ma bibliothèque de code montre comment je l’ai fait pour un masque binary basé sur des caractères:

 static unsigned char bitmask[CHAR_BIT]; void bitsetInit (void) { unsigned char mask = 1; int i = 0; while (i < CHAR_BIT) { bitmask[i++] = mask; mask <<= 1; } } 

et en utilisant:

 bsp->bits[bitnum/CHAR_BIT] &= ~bitmask[bitnum%CHAR_BIT]; bsp->bits[bitnum/CHAR_BIT] |= bitmask[bitnum%CHAR_BIT]; 

pour effacer et régler les bits, respectivement.

Si vous voulez utiliser unsigned int au lieu de unsigned char vous calculerez simplement le nombre de bits pour cela:

 unsigned int UINT_BIT = CHAR_BIT * sizeof (unsigned int); 

et utilisez-le là où j'ai utilisé CHAR_BIT ci-dessus (le tableau de mask peut être alloué dynamicment à l'exécution si besoin est).

La bibliothèque multi-précision de Gnu fournit une implémentation d’entiers, avec une très bonne optimisation pour les entiers de précision arbitraire, et possède également la fonctionnalité de twiddling le plus utile. (lien)

En fonction des opérations spécifiques que vous devez réellement effectuer, il se peut que certaines structures de données sophistiquées permettent de mieux faire le travail. Par exemple, il existe la très intelligente structure Disjoint Sets , qui permet de modéliser un ensemble de disjoints, qui offre des performances asymptotiques vraiment étonnantes sur les 3 opérations qu’elle prend en charge.

Vous pouvez utiliser uint64_t partir de . Au-delà de ça, j’ai bien peur que vous n’ayez plus de chance en tant que & and | sont concernés et doivent rechercher une conception différente (par exemple, des structures avec les fonctions appropriées pour les gérer, ou des bibliothèques tierces).

paxdiablo semble vous avoir donné la bonne approche pour résoudre ce problème de la façon dont vous avez dit que vous souhaitiez le résoudre.

Y a-t-il une meilleure façon d’aborder cette tâche?

À moins que vous n’ayez une performance particulière ou une raison matérielle particulière pour effectuer votre travail, il existe peut-être de meilleures façons de représenter un ensemble. Par exemple, une liste liée ou une arborescence binary, dont les valeurs sont membres de l’ensemble. Ces deux structures peuvent avoir (effectivement) une taille infinie et sont faciles à parcourir.

Le fait que certaines opérations sur les ensembles soient faciles à mettre en œuvre avec une logique booléenne ne signifie pas qu’elles le sont toutes. Le code supplémentaire qui dépend de vos opérations sur les ensembles sera probablement plus clair si vous avez une interface de type ensemble plutôt qu’une interface booléenne (uniquement).

Quelle que soit la solution que vous proposez, je vous recommande de la masquer derrière une interface afin de pouvoir modifier votre solution de stockage à l’avenir. Vous pouvez le faire en définissant des fonctions auxquelles vous transmettez votre structure et en opérant uniquement sur la structure par le biais de ces fonctions.

Si vous êtes vraiment satisfait des types 32 et 64 bits, en C moderne (C99), les typedefs uint_least32_t et uint_least64_t sont assurés d’exister dans "stdint.h" . Contrairement aux types à largeur exacte uint32_t et uint64_t (qui sont facultatifs), ils peuvent correspondre à un type de base dont la largeur est supérieure à celle indiquée par le nombre.

Si la vitesse est importante, vous pouvez également utiliser uint_fast32_t et uint_fast64_t qui doivent également exister. Ils négocient la vitesse pour la taille et sont supposés utiliser le type de base correspondant qui dispose du support “le plus rapide” sur la machine cible. Cependant, l’explosion de données peut être considérable. Par exemple, sur mon ubuntu 64 bits, tous ces types “rapides” sont des types 64 bits.

Si vous utilisez gcc, vous auriez également __uint128_t sur les machines 64 bits en tant que service supplémentaire.