Skyduino:~#
Articles
Autre, C/C++, programmation, tutoriel

[Tuto] Le "bitwise" pour les nuls

Bonjour tout le monde !

Cet article s’est fait un peu attendre je suis désolé …
Avec mon stage c’est assez compliqué de m’occuper du blog le soir en rentrant.

Bref, aujourd’hui je vous ai préparé un sujet certes simple mais que je vois revenir souvent sur le forum arduino.
Il est donc temps de régler ce probléme une bonne fois pour toute ! ;)

Le sujet du jour : le "bitwise", soit "manipulation de bits" en français.
(le premier qui fait un commentaire salace je le ban IP, compris :))

Qu’est-ce que le "bitwise" ?

Le "bitwise" est une technique qui consiste, comme son nom l’indique, à manipuler des "bits".
Pour ceux qui dormaient en classe un "bit" c’est l’élément de base de l’informatique numérique, qui peut prendre la valeur 0 ou 1.

A quoi ça sert et dans quel cas on l’utilise ?

Bonne question, prenons un exemple tout bête que j’ai vu sur le forum cette semaine :
"Stocker des booléens (Vrai / Faux) en mémoire"

Une personne débutant en programmation ferait surement ceci :

int index = 0;
int tableau[100];

void ajouterBooleen(int valeur) {
	tableau[index] = valeur;
	index++;
}

Certes ça marche, mais à quel prix ?

Premier probléme : les variables globales.
Ici on se rend compte que ces deux variables globales polluent l’espace de nom du programme, un bon programmeur ne laisserait jamais une telle chose arriver.

Deuxième probléme : la consommation de mémoire.
Ici on utilise un tableau de int, sur une architecture 8 bits un int fait deux octets.
On utilise donc ici 100 x 2 = 200 octets de mémoire RAM pour stocker une centaine de booléen !
Pour les matheux cela fait un rendement de 6,25%, une vrai catastrophe …

Mini parenthèse : comment je calcule le rendement ?
C’est simple : [(nombre de valeurs à stocker) x (taille effective en bits d'une valeur)] / [(taille du tableau de stockage) x (taille en bits d'une case du tableau)]
Soit dans ce premier exemple : (100 x 1) / (100 x 16) = 100 / 1600 = 0.0625

Solutions :
– utiliser des variables static pour ne plus polluer l’espace de nom
– utiliser un type de variable plus adapté que int

A noter qu’ici je ne fait que stocker mes valeurs, dans une vrai application je serait bien obligé de les relire à un moment ou à un autre.
C’est pourquoi le tableau de valeurs va rester en variable globale afin d’être utilisable depuis plusieurs fonctions.
Une autre solution consisterait à passer le tableau en argument mais cela alourdirait mes codes d’exemple ;)

Sur ces belles paroles une personne débutant mais suivant mon blog ferait surement ceci :

byte tableau[100];

void ajouterBooleen(byte valeur) {
	static byte index = 0;
	tableau[index] = valeur;
	if (++index == 100) index = 0; // Mes lecteurs ne font pas de buffer overflow ;)
}

C’est mieux, l’espace de nom n’est plus pollué inutilement et l’empreinte mémoire du programme a été divisé par deux.
Seulement le rendement d’un tel système est encore très bas : 12.5% …

Alors comment faire pour avoir un rendement optimum ?
La réponse est simple : le bitwise !

Avant d’expliquer plus en détails cette technique voici le code permettant d’avoir un rendement de 100% (ok, 96% pour être exact, 100 n’étant pas un multiple de 8) !

byte tableau[13]; // 13 x 8 = 104 bits

void ajouterBitAt(byte bit, byte at) {
	if (bit)
		tableau[at / 8] |= 1 << (at & 7);
	else
		tableau[at / 8] &= ~(1 << (at & 7));
}

byte lireBitAt(byte at) {
	return (tableau[at / 8] & (1 << (at & 7))) ? 1 : 0;
}

void ajouterBooleen(byte valeur) {
	static byte index = 0;
	ajouterBitAt(valeur, index);
	if (++index == 100) index = 0;
}

Je sait, pour le moment vous êtes en train de vous dire : "OMG mais c’est quoi ce truc !? C’est ultra compliqué !"
En fait c’est super simple à comprendre, c’est de la logique et un peu de math ;)

Les bases :

Avant de commencer on va reprendre les bases du calcul booléen.

En calcul "bits à bits" il existe 6 opérations de base :
– NOT (NON)
– AND (ET)
– OR (OU)
– XOR (OU exclusif)
– SHR (Décalage à droite)
– SHL (Décalage à gauche)
On utilise aussi assez souvent le NON logique (pas binaire).

-

Le NOT (NON) :

Il donne l’inverse binaire de ce qu’on lui passe en argument :

A (entrée) S (sortie)
0 1
1 0

Voici un exemple de NON binaire :

byte A = 0b10101010;
byte S = ~A; // S = NOT A
// S = 01010101

-

Le AND (ET) :

Il fait un ET entre deux bits :

A B S
0 0 0
0 1 0
1 0 0
1 1 1

Pour que le ET retourne "1" il faut que les deux bits en entrée valent "1", sinon la sortie vaut zéro.

Voici un exemple de ET binaire :

byte A = 0b10101010;
byte B = 0b10100101;
byte S = A & B; // S = A AND B
// S = 10100000

-

Le OR (OU) :

Il fait un OU entre deux bits :

A B S
0 0 0
0 1 1
1 0 1
1 1 1

Pour que le OU retourne "1" il faut qu’un des deux bits en entrée, ou les deux, valent "1", sinon la sortie vaut zéro.

Voici un exemple de OU binaire :

byte A = 0b10101010;
byte B = 0b10100101;
byte S = A | B; // S = A OR B
// S = 10101111

-

Le XOR (OU exclusif) :

Il fait un OU exclusif entre deux bits :

A B S
0 0 0
0 1 1
1 0 1
1 1 0

Pour que le OU exclusif retourne "1" il faut qu’un des deux bits en entrée MAIS PAS LES DEUX, vaut "1", sinon la sortie vaut zéro.

Voici un exemple de OU exclusif binaire :

byte A = 0b10101010;
byte B = 0b10100101;
byte S = A ^ B; // S = A XOR B
// S = 00001111

Remarque : le OU exclusif est une opération dite "symétrique".
XORer deux fois une valeur revient à avoir la valeur de base.

Exemple :

byte A = 0b10101010;
byte B = 0b10100101;
byte S = A ^ B ^ B; // S = A XOR B XOR B
// S = A

C’est pour cela que le OU exclusif est utilisé dans certain algorithme de cryptage (symétrique) léger.

-

Le SHR (Décalage à droite) :

Le décalage à droite comme son nom l’indique décale les bits d’une valeur de N bits vers la droite.
Les bits "vides" sont remplis par de "0".

Exemple :

byte A = 0b10101010;
byte S = A >> 4; // S = A SHR 4
// S = 00001010

-

Le SHL (Décalage à gauche) :

Même chose que pour le décalage à droite mais vers la gauche cette fois ci.

Exemple :

byte A = 0b10101010;
byte S = A << 4; // S = A SHL 4
// S = 10100000

Remarque : sur certain processeur (les AVR8 par exemple) il existe une opération "ROR" et "ROL" pour "Rotate Right/Left Through Carry".
Le principe est le même que pour les décalages classiques mais les bits "poussé" sur un côté reviennent de l’autre côté.

PS: Ce type d’opération n’est possible qu’en assembleur sur certain processeur, le C ne gére pas cet opérateur.
Pour ne pas vous perdre je resterai en pseudo C ;)

Exemple :

A = 0b10101111;
S = A ROL 4;
// S = 11111010

Remarque : comme me l’a rappeler flogib dans les commentaires un décalage d’un bit vers la droite divise par deux la valeur numérique.
De même un décalage d’un bit vers la gauche multiplie la valeur numérique par 2.
C’est une solution simple et optimisé de faire une division / multiplication par une puissance de 2, même si le cpu n’as pas d’instructions matériel pour.
(ce qui est souvent le cas pour la division par exemple)

-

Bonus : le NON logique :

Le NON logique diffère du NON binaire, celui ci ne fait pas une opération "bits à bits" mais directement sur la valeur logique (0 = FAUX, tout autre valeur = VRAI)

Exemple :

byte A1 = 100; // Toutes valeur autre que 0 équivaut à VRAI
byte A2 = 0;   // Zero équivaut à FAUX
byte S1 = !A1; // S1 = LOGICAL NOT A1
byte S2 = !A2; // S2 = LOGICAL NOT A2
// S1 = 0 (FAUX)
// S2 = 1 (VRAI)

Les opérations courantes :

Personnellement j’utilise régulièrement les opérations suivantes :
– Lire la valeur d’un bit
– Mettre un bit à "1"
– Mettre un bit à "0"
– Masquer un certain nombre de bits
– Faire une modification de plusieurs bits sans toucher au reste des bits
– Transformer un mot 16 bits en deux mots 8 bits
– Transformer deux mots 8 bits en un mot 16 bits
– Faire un modulo avec une puissance de 2

Vous êtes prêt ? Accrochez vous le train démarre ;)

Lire la valeur d’un bit :

Il faut tout d’abord connaitre l’usage que l’on souhaite faire du résultat.
Est-ce que celui ci sera traité comme un booléen (VRAI = !0, FAUX = 0) ou comme un bit (0 / 1) ?

Si celui ci est traité comme un booléen l’opération devient triviale.
En effet dans ce cas il suffit de faire un ET avec un masque ayant à "1" les bits que l’on souhaite lire.
Le ET va masquer les bits que l’on ne souhaite pas lire et retourner une valeur égale à 0 (FAUX) si aucun des bits qui nous intéresse n’est à "1", ou une valeur supérieur à zéro (VRAI) si un des bits est à "1".

Exemple :

byte A = 0b00010001;
byte S = A & 0b00010000; // On souhaite lire le bit 5
// S = 00010000 (VRAI)

Si on souhaite lire un bit bien précis il existe un moyen simple de créer le masque.
Il suffit de faire un décalage de bit vers la droite de N – 1 bits (0 = 1er bit).

byte A = 0b00010001;
byte S = A & (1 << 4); // On souhaite lire le bit 5
// S = 00010000

Et si on souhaite lire un bit et avoir sa valeur binaire 0 / 1 ?
Deux possibilités existe pour cela :
– décaler le résultat d’autant de bit que celui qu’on souhaite lire :

byte A = 0b00010001;
byte S = (A & (1 << 4)) >> 4;
// S = 1

- ajouter un test logique pour convertir le résultat :

byte A = 0b00010001;
byte S = (A & (1 << 4)) ? 1 : 0;
// S = 1

La deuxième solution est celle que je préfère car c’est la plus lisible et la moins génératrice d’erreur.

-

Mettre un bit à "1"

Pour mettre un bit bien précis à "1" il suffit de prendre la valeur et de lui "ajouter" le bit avec un OU :

byte A = 0b00000001;
byte S = A | (1 << 4); // On souhaite mettre le bit 5 à "1"
// S = 00010001

Version "une ligne, sur place" :

byte A = 0b00000001;
A |= 1 << 4; // On souhaite mettre le bit 5 à "1"
// A = 00010001

Mettre un bit à "0"
Pour mettre un bit bien précis à "0" il suffit de faire un ET de la valeur actuelle avec comme masque l’inverse du masque utilisé pour la mise à "1" vu ci dessus :

byte A = 0b00010001;
byte S = A & ~(1 << 4); // On souhaite mettre le bit 5 à "0"
// S = 00000001

Version "une ligne, sur place" :

byte A = 0b00010001;
A &= ~(1 << 4); // On souhaite mettre le bit 5 à "0"
// A = 00000001

-

Masquer un certain nombre de bits

Imaginons que pour une raison XYZ je souhaite lire uniquement les bits 7 et 8 d’une valeur.

Pour faire cela rien de plus simple, un ET et un décalage suffisent :

byte A = 0b10101010;
byte S = (A & 0b11000000) >> 6; // On souhaite lire les bits 7 et 8
// S = 00000010

-

Faire une modification de plusieurs bits sans toucher au reste des bits

C’est un peu le contraire de l’opération précédente, au lieu de lire une partie des bits d’une valeur on veut les écrire.

Pour faire cela il suffit de faire un ET avec un masque bien pensé et enchainer le tout par un OU :

byte A = 0b10101010;
byte S = (A & 0b11111000) | 0b00000101; // Je veut mettre les bits 1, 2 et 3 à "101"
// S = 10101101

-

Transformer un mot 16 bits en deux mots 8 bits

Masque, ET, décalage, vous devriez avoir compris le principe maintenant ;)

uint16_t A = 0b1010101010101111;
byte SH = (A & 0xFF00) >> 8; // MSB (bits 9 à 16)
byte SL = A & 0x00FF; // LSB (bits 1 à 8)
// SH = 0b10101010
// SL = 0b10101111

-

Transformer deux mots 8 bits en un mot 16 bits

Mettre principe qu’au dessus mais dans l’autre sens :

byte AH = 0b10101010; // MSB (bits 9 à 16)
byte AL = 0b10101111; // LSB (bits 1 à 8)
uint16_t S = (AH << 8) | AL;
// S = 0b1010101010101111

-

Faire un modulo avec une puissance de 2

Faire un modulo ça revient à faire quoi ?
Pour faire simple ça revient à faire une soustraction de N tant que la valeur est supérieur à N.

Et si N est égale à une puissance de 2 (1, 2, 4, 8, 16, 32, 64, …) ?
Et bien dans ce cas faire un modulo d’une puissance de 2 revient à faire un ET "bits à bits" de N – 1 !

Remarque : Pourquoi N – 1 et pas N ?
Prennons N = 8
bin(N) = 0b1000
bin(N – 1) = 0b0111
Si on souhait faire un masque il faut prendre N – 1 et non N.

Exemple, ceci :

byte A = 50;
byte S = A % 16;

Equivaut à :

byte A = 50;
byte S = A & 15;

L’avantage c’est que le ET ne demande aucune boucle, aucun test pour savoir si la valeur est inférieur à N ou pas et que par conséquent cela ce fait la plupart du temps en un seul cycle CPU.

Maintenant que vous êtes des experts en bitwise reprenons le code d’exemple du premier chapitre :

byte tableau[13]; // 13 x 8 = 104 bits
// On "perd" 4 bits mais de tout facon on ne pourrait pas faire mieux

// Cette fonction stock un bit en mémoire à l'emplacement voulu
void ajouterBitAt(byte bit, byte at) {
	if (bit) // Si le bit est à "1"
		tableau[at / 8] |= 1 << (at & 7); // Opération classique de mise à "1"
		// le [at / 8] du tableau permet d'accéder à l'emplacement du byte contenant l'index du bit voulu
		// Exemple : at = 0 -> tableau[0 / 8] = tableau[0]
		//           at = 8 -> tableau[8 / 8] = tableau[1] etc ...
		// Le (at & 7) permet de faire un modulo 8 (puissance de 2 -> ET)
		// Le reste de l'instruction n'est rien d'autre qu'une opération de mise à "1" classique
	else // Si le bit est à "0"
		tableau[at / 8] &= ~(1 << (at & 7)); // Opération classique de mise à "0"
}

// Cette fonction retourne la valeur d'un bit en mémoire à l'emplacement spécifié
byte lireBitAt(byte at) {
	return (tableau[at / 8] & (1 << (at & 7))) ? 1 : 0;
	// On retrouve le [at / 8] permettant de sélectionner le byte contenant l'emplacement voulu
	// On retrouve aussi le modulo 8 
	// Le reste n'est autre qu'une lecture de bit par masquage avec un test logique
	// pour transformer le résultat en une valeur décimal 0 ou 1.
}

// La fonction d'ajout de "haut niveau"
void ajouterBooleen(byte valeur) {
	static byte index = 0;         // Index courant
	ajouterBitAt(valeur, index);   // Ajout réel du bit en mémoire
	if (++index == 100) index = 0; // Incrémentation de l'index + anti-buffer overflow
}

Vous voyez c’était pas si compliqué que ça ;)

Maintenant que vous savez faire du bitwise vous n’aurez plus aucune excuse.
Si je vois des tableaux de int pour stocker de HIGH/LOW, booléen ou autre valeur logique je répondrai pas à votre question / topic / etc ;)

About these ads

Discussion

7 réflexions sur “[Tuto] Le "bitwise" pour les nuls

  1. Chouette article, un rappel de temps en temps ne fait pas de mal :)

    Une petite remarque pour l’exemple de "Faire une modification de plusieurs bits sans toucher au reste des bits", tu veux uniquement mettre 3 bits à 1 du coup le & 0b11111000 ne sert pas à grand chose dans ce cas.

    Sinon il pourrait être utile de préciser que chaque décalage vers la droite divise par 2 la valeur numérique, et inversement, un décalage vers la gauche multiplie par 2.

    Publié par flogib | 5 avril 2013, 22 h 18 min
    • >> Une petite remarque pour l’exemple de « Faire une modification de plusieurs bits sans toucher au reste des bits », tu veux uniquement mettre 3 bits à 1 du coup le & 0b11111000 ne sert pas à grand chose dans ce cas.

      C’est vrai, j’étais pas super inspiré sur cet exemple. Je vais en mettre un plus parlant ;)

      >> Sinon il pourrait être utile de préciser que chaque décalage vers la droite divise par 2 la valeur numérique, et inversement, un décalage vers la gauche multiplie par 2.

      Exact, j’avais pas pensé à le préciser je vais le rajouter. Merci du conseil ;)

      Publié par skywodd | 5 avril 2013, 22 h 22 min
  2. Bless. I am the laziest programmer youll ever meet, and this one hit right there, and made me feel more conscious of it !! So, thanks for the reminder… Love your stuff, by the way !!

    Publié par Ras B | 6 avril 2013, 16 h 04 min
  3. tu manipule super bien les "bits" skywood :D (non non ne banne pas mon IP stp)
    mais sinon sympas le tuto ;)

    Publié par karol | 20 mai 2013, 1 h 31 min

Rétroliens/Pings

  1. Pingback: Divers | Pearltrees - 18 novembre 2013

  2. Pingback: [Tuto/Info] Matrice de leds RGB – partie 2 | Skyduino - Le DIY à la française - 1 février 2014

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

Archives

Wow. Dogecoin. Amaze.

Laissez un tip en Dogecoin

DMMNFk6WBVTpx2Wu1Z35GL61QXSd6r6WQx

Suivre

Recevez les nouvelles publications par mail.

Rejoignez 749 autres abonnés