Explication d’un algorithme pour définir, effacer et tester un seul bit

Dans le livre Programming Pearls, il existe un code source pour définir, effacer et tester un bit de l’index donné dans un tableau d’ints qui est en fait une représentation d’ensemble.

Le code est le suivant:

#include #define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F #define N 10000000 int a[1+ N/BITSPERWORD]; void set(int i) { a[i>>SHIFT] |= (1<>SHIFT] &= ~(1<>SHIFT] & (1<<(i & MASK)); } 

Quelqu’un pourrait-il m’expliquer la raison de la définition de MAJ et du MASK? Et quels sont leurs objectives dans le code?

J’ai déjà lu la question précédente.

VonC a posté une bonne réponse sur les masques de bits en général. Voici quelques informations plus spécifiques au code que vous avez publié.

Étant donné un entier représentant un bit, nous déterminons quel membre du tableau contient ce bit. C’est-à-dire que les bits 0 à 31 résident dans a[0] , les bits 32 à 63 dans a[1] , etc. Tout ce que i>>SHIFT fait est i / 32 . Cela détermine le membre du bit qui habite. Avec un compilateur d’optimisation, ceux-ci sont probablement équivalents.

Évidemment, maintenant que nous avons découvert dans quel membre de ce bitflag habite, nous devons nous assurer que nous définissons le bit correct dans cet entier. C’est ce que 1 << i fais. Cependant, nous devons nous assurer que nous n'essayons pas d'accéder au 33e bit dans un entier de 32 bits, de sorte que l'opération de décalage est contrainte en utilisant 1 << (i & 0x1F) . La magie ici est que 0x1F est 31, donc nous ne décalerons jamais à gauche le bit représenté par i plus de 31 places (sinon, il aurait dû être inséré dans le prochain membre de a ).

À partir d’ ici (réponse générale pour démarrer ce fil)

Un masque de bits est une valeur (pouvant être stockée dans une variable) qui vous permet d’isoler un ensemble spécifique de bits dans un type entier.

Normalement, le bit masqué aura les bits qui vous intéressent définis sur 1 et tous les autres bits définis sur 0. Le masque vous permet ensuite d’isoler la valeur des bits, d’effacer tous les bits ou de définir tous les bits ou de définir une nouvelle valeur. aux bits.

Les masques (en particulier ceux à bits multiples) ont souvent une valeur de décalage associée qui correspond à la quantité dont les bits doivent être décalés à gauche, de sorte que le bit masqué le moins significatif soit déplacé vers le bit le moins significatif du type.

Par exemple, en utilisant un type de données court de 16 bits, supposons que vous souhaitiez pouvoir masquer les bits 3, 4 et 5 (LSB est le numéro 0). Vous masquez et changez quelque chose comme

 #define MASK 0x0038 #define SHIFT 3 

Les masques sont souvent atsortingbués en hexadécimal, car il est plus facile de travailler avec des bits du type de données de cette base, par opposition à décimal. Historiquement octal a également été utilisé pour les masques de bits.

Si j’ai une variable, var, qui contient des données pour lesquelles le masque est pertinent, je peux alors isoler les bits comme ceci

 var & MASK 

Je peux isoler tous les autres bits comme celui-ci

 var & ~MASK 

Je peux effacer les bits comme ça

 var &= ~MASK; 

Je peux effacer tous les autres bits comme celui-ci

 var &= MASK; 

Je peux mettre tous les bits comme ça

 var |= MASK; 

Je peux définir tous les autres bits comme celui-ci

 var |= ~MASK; 

Je peux extraire la valeur décimale des bits comme ceci

 (var & MASK) >> SHIFT 

Je peux assigner une nouvelle valeur aux bits comme ceci

 var &= ~MASK; var |= (newValue << SHIFT) & MASK; 

Lorsque vous voulez définir un peu dans le tableau, vous devez

  1. chercher le bon index de tableau et
  2. définissez le bit approprié dans cet élément de tableau.

Il existe des BITSPERWORD (= 32) dans un élément de tableau, ce qui signifie que l’index i doit être divisé en deux parties:

  • les 5 bits les plus à droite servent d’index dans l’élément de tableau et
  • le rest des bits (le plus à gauche 28) sert d’index dans le tableau.

Vous recevez:

  • les 28 bits les plus à gauche en éliminant les cinq derniers , ce qui est exactement ce que i>>SHIFT fait, et
  • les cinq bits les plus à droite en masquant tout sauf les cinq bits les plus à droite , ce que fait i & MASK .

Je suppose que vous comprenez le rest.

L’opération au niveau du bit et les paragraphes principaux de Mask sont une explication concise et contiennent des indications à approfondir.

Pensez à un octet de 8 bits en tant qu’ensemble d’éléments d’un univers de 8 membres. Un membre est dans l’ensemble lorsque le bit correspondant est activé. Définir un peu plus d’une fois ne modifie pas l’ appartenance à un ensemble (un bit ne peut avoir que 2 états). Les opérateurs binarys en C permettent d’accéder aux bits par masquage et décalage .

Le code tente de stocker N bits par un tableau, chaque élément du tableau contenant BITSPERWORD (32) bits.

Ainsi, si vous essayez d’accéder au bit i , vous devez calculer l’index de l’élément de tableau qui le stocke ( i/32 ), ce que fait i>>SHIFT .

Et ensuite, vous devez accéder à ce bit dans l’élément de tableau que nous venons de recevoir.

(i & MASK) donne la position du bit dans l’élément de tableau (mot). (1<<(i & MASK)) active le bit à cette position.

Vous pouvez maintenant définir / effacer / tester ce bit dans a[i>>SHIFT] en (1< .

Vous pouvez également penser que i est un nombre de 32 bits, que les bits 6 ~ 31 sont l’indice de l’élément de tableau qui le stocke, les bits 0 ~ 5 représentent la position du bit dans le mot.