Binaire 010 : l'utilité des opérations bitwise et du bit shifting
- Mia Combeau
- Informatique
- 7 mai 2022
Table des matières
Les ordinateurs ne connaissent qu’une seule langue : le binaire. Nos nombreux langages de programmation nous permettent de donner des instructions dans un format lisible par l’humain. Ces instructions seront ensuite traduites en longues séquences de 0 et de 1. Bien que ce niveau d’abstraction nous est indispensable, il est parfois utile voire bien plus efficace de manipuler les bits de façon directe, à l’aide du bit shifting (décalage de bit) et des opérations bitwise (opérations bit à bit).
Nous avons précédemment eu l’occasion de voir ce qu’est le binaire et comment un ordinateur calcule avec. Voyons maintenant quels sont ces opérateurs qui nous permettent de manipuler directement les bits, et pourquoi on pourrait vouloir les utiliser.
Opérations de manipulation de bits
Dans les langages qui permettent la manipulation directe des bits, comme le C, les opérateurs sont les suivants :
| Opérateur | Description |
|---|---|
| « | décalage de tous les bits d’un champ vers la gauche |
| » | décalage de tous les bits d’un champ vers la droite |
| & | ET (AND) : opérateur logique pour comparer deux champs de bits |
| | | OU (OR) : opérateur logique pour comparer deux champs de bits |
| ^ | OU exclusif (XOR) : opérateur logique pour comparer deux champs de bits |
| ~ | NON (NOT) : complémentaire par bit |
Pour examiner chacun de ces opérateurs de plus près, créons tout d’abord un petit programme en C. Celui-ci imprimera les 32 bits d’un entier non-signé, séparés d’espaces pour la lisibilité. Malheureusement, printf ne nous offre pas de spécification pour imprimer l’entier en base 2. Nous allons donc devoir écrire notre propre fonction pour formater correctement notre nombre en binaire. Ici, il y a deux fichiers, bitwise.c que l’on va modifier tout au long de cet article pour tester les différentes opérations bitwise, et ft_unsigned_itoa_base.c qui nous permettra d’imprimer correctement nos résultats. Voici le code source :
- bitwise.c
- ft_unsigned_itoa_base.c
#include <stdlib.h>
#include <stdio.h>
char *ft_unsigned_itoa_base(unsigned n, unsigned base);
int main(void)
{
unsigned int nb;
char *nb_str;
nb = 242;
nb_str = ft_unsigned_itoa_base(nb, 2);
printf("Binary number:\t\t%s (Decimal: %010u)\n", nb_str, nb);
free(nb_str);
return (0);
}
#include <stdlib.h>
/* ft_itoa_len:
* Mesure la taille de la chaîne de caractères d'un entier non-signé.
*/
static unsigned ft_itoa_len(unsigned n, unsigned base)
{
unsigned len;
len = 0;
if (n == 0)
return (1);
while (n >= 1)
{
len++;
n /= base;
}
return (len);
}
/* ft_num_to_str:
* Traduit un entier non-signé en une chaîne de caractères selon
* la base fournie.
*/
static char *ft_num_to_str(unsigned n, char *str, unsigned len, unsigned base)
{
if (base > 16)
return (NULL);
str = malloc(sizeof *str * len + 1);
if (str == NULL)
return (NULL);
str[len] = '\0';
len--;
while (len)
{
str[len] = "0123456789ABCDEF"[n % base];
n /= base;
len--;
}
str[len] = "0123456789ABCDEF"[n % base];
return (str);
}
/* ft_pad_zeros:
* Ajoute des zéros au début de la chaîne de caractères d'un nombre
* binaire si besoin.
*/
static char *ft_pad_zeros(char *str, int len)
{
char *padded;
int i;
int j;
padded = malloc(sizeof *padded * 33);
if (!padded)
return (NULL);
i = 32;
padded[i] = '\0';
i--;
while (--len >= 0)
{
padded[i] = str[len];
i--;
}
while (i >= 0)
{
padded[i] = '0';
i--;
}
free(str);
return (padded);
}
/* ft_add_spaces:
* Ajoute des espaces à la chaîne de caractères d'un nombre binaire.
*/
static char *ft_add_spaces(char *str)
{
int i;
int j;
char *spaced;
spaced = malloc(sizeof *spaced * 41);
if (!spaced)
return (0);
spaced[41] = '\0';
i = 0;
j = 0;
while (str[i])
{
if (j % 5 == 0)
spaced[j] = ' ';
else
{
spaced[j] = str[i];
i++;
}
j++;
}
free(str);
return (spaced);
}
/* ft_unsigned_itoa_base:
* Prend en paramètres un entier non signé et une base (2 = binaire,
* 10 = décimal, 16 = hexadécimal).
* Retourne une chaîne de caractères correspondant au nombre fourni.
* Si la base est binaire, la chaîne renvoyée représentera les 32 bits
* d'un entier séparé d'espaces pour la lisibilité.
*/
char *ft_unsigned_itoa_base(unsigned int n, unsigned int base)
{
unsigned int len;
char *str;
len = ft_itoa_len(n, base);
str = ft_num_to_str(n, str, len, base);
if (base == 2)
{
if (len < 32)
str = ft_pad_zeros(str, len);
str = ft_add_spaces(str);
}
if (!str)
return (NULL);
return (str);
}
Résultat :
Avec ce petit programme, on pourra très bien observer l’effet des opérateurs bit à bit sur notre entier non-signé, en commençant par le déplacement de bits.
Bit shifting : décaler les bits
Le bit shifting, ou le déplacement de bits, c’est une simple opération lors de laquelle tous les bits d’un champ sont déplacés d’un certain nombre de crans vers la droite ou la gauche. Tentons de voir cet effet avec notre programme. En premier lieu, nous allons décaler les bits de notre nombre d’une place vers la droite, puis de 10 crans vers la gauche :
#include <stdlib.h>
#include <stdio.h>
char *ft_unsigned_itoa_base(unsigned n, unsigned base);
int main(void)
{
unsigned int nb;
unsigned int nb_mod;
char *nb_str;
nb = 242;
nb_str = ft_unsigned_itoa_base(nb, 2);
printf("Binary number:\t\t%s (Decimal: %010u)\n", nb_str, nb);
free(nb_str);
nb_mod = nb >> 1;
nb_str = ft_unsigned_itoa_base(nb_mod, 2);
printf("Bitshift 1 right:\t%s (Decimal: %010u)\n", nb_str, nb_mod);
free(nb_str);
nb_mod = nb << 10;
nb_str = ft_unsigned_itoa_base(nb_mod, 2);
printf("Bitshift 10 left:\t%s (Decimal: %010u)\n", nb_str, nb_mod);
free(nb_str);
return (0);
}
Dans ce résultat on peut voir que les bits ont bien été déplacés d’un cran vers la droite, puis de 10 crans vers la gauche. On peut aussi voir que des zéros viennent remplacer les bits déplacés et cela modifie de façon drastique mais prévisible la valeur de notre nombre.
En effet, déplacer les bits vers la droite revient à diviser notre valeur par 2 puissance le nombre de crans. Les déplacer vers la gauche revient à multiplier notre valeur par 2 puissance le nombre de crans. Notre valeur originale était ici de 242, quand on a déplacé ses bits de 10 crans vers la gauche, on a multiplié notre valeur par 2 puissance 10 (donc par 1024) : 242 x 210 = 247 808.
Par contre, si on utilise le bit shifting pour la multiplication, il ne faut pas oublier qu’il y a de grandes chances que le bit de poids fort sera perdu si le nombre est très grand, ce qui fausserait le résultat. De plus, dans les exemples de cet article nous utilisons des entiers non signés, mais si le nombre est négatif et que le complément à deux est utilisé pour représenter les nombres négatifs, le bit de signe peut être altéré lors d’un déplacement vers la gauche.
Par exemple, si notre type de donnée est de 8 bits maximum (un char) :
Entier non-signé en binaire : 1011 0111 (183)
Déplacement de 1 à gauche : 0110 1110 (110)
Or, 183 * 2 = 366, et non 110...
On a ici perdu le bit de poids fort à gauche à cause du dépassement !
Entier signé en binaire : 1011 0111 (-73)
Déplacement de 1 à gauche : 0110 1110 (+110)
Or, (-73) * 2 = -146 et non 110...
On a ici perdu le bit de poids fort qui indiquait le signe !
Les opérations logiques binaires
Les autres opérations que l’on peut effectuer sur un nombre binaire sont d’un ordre logique. Ces opérateurs sont identiques aux portes logiques d’un circuit électronique : elles prennent une ou deux entrées et produisent une sortie en fonction des entrées fournies. Ce sont les opérateurs ET, OU, OU exclusif et NON qui sont à la base du fonctionnement d’un ordinateur. Tous les calculs qu’ils effectuent sont intrinsèquement liés à cette logique physique. Voyons donc voir comment ces opérateurs fonctionnent.
L’opérateur bitwise NON (~)
Contrairement aux opérations qui suivent, l’ opération bitwise NON (NOT en anglais) ne marche qu’avec une seule entrée. Elle consiste simplement à sortir l’exact opposé d’un champ binaire. C’est à dire que si le bit est à 0, l’opérateur NON renvoie 1, et si le bit a une valeur de 1, il renvoie 0.
Un tilde, ~, représente cet opérateur NON. Testons-le :
#include <stdlib.h>
#include <stdio.h>
char *ft_unsigned_itoa_base(unsigned n, unsigned base);
int main(void)
{
unsigned int nb;
unsigned int nb_mod;
char *nb_str;
nb = 2423;
nb_str = ft_unsigned_itoa_base(nb, 2);
printf("Binary number:\t\t%s (Decimal: %010u)\n", nb_str, nb);
free(nb_str);
nb_mod = ~nb;
nb_str = ft_unsigned_itoa_base(nb_mod, 2);
printf("Bitwise NOT:\t\t%s (Decimal: %010u)\n", nb_str, nb_mod);
free(nb_str);
return (0);
}
Comme on peut le voir, tous les bits sont inversés dans le résultat de l’opération NON. C’est ce qu’on appelle aussi un complément à un.
L’opérateur bitwise ET (&)
L’ opérateur bit à bit ET (AND en anglais) compare deux bits et retourne vrai (1) si et seulement si les deux bits ont une valeur de 1. Si l’un ou l’autre ou les deux ont une valeur de 0, le résultat de l’opération sera faux (0). On peut résumer ceci dans un petit tableau :
| ET | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
Pour représenter cet opérateur ET dans une opération bitwise, on utilise un caractère spécial, l’esperluette : &. Modifions notre code un petit peu pour effectuer cela avec deux nombres :
#include <stdlib.h>
#include <stdio.h>
char *ft_unsigned_itoa_base(unsigned n, unsigned base);
int main(void)
{
unsigned int nb1;
unsigned int nb2;
unsigned int res;
char *nb_str;
nb1 = 2423;
nb2 = 10002;
nb_str = ft_unsigned_itoa_base(nb1, 2);
printf("Binary number 1:\t%s (Decimal: %010u)\n", nb_str, nb1);
free(nb_str);
nb_str = ft_unsigned_itoa_base(nb2, 2);
printf("Binary number 2:\t%s (Decimal: %010u)\n", nb_str, nb2);
free(nb_str);
res = nb1 & nb2;
nb_str = ft_unsigned_itoa_base(res, 2);
printf("Bitwise AND:\t\t%s (Decimal: %010u)\n", nb_str, res);
free(nb_str);
return (0);
}
Et en effet, on peut voir ici que seuls les bits de valeur 1 présents au même endroit dans les deux nombres ont été copiés dans le résultat de l’opération bitwise &, le reste est mis à 0.
Pour faire le contraire de l’opération ET, NON-ET (NAND en anglais), il suffit d’inverser tous les bits du résultat avec ~(nb1 & nb2) !
L’opérateur bitwise OU (|)
Contrairement à l’opérateur ET, l’ opérateur OU (OR en anglais) retourne vrai (1) si l’un des deux bits ou les deux ont une valeur de 1. C’est seulement si les deux sont à 0 qu’il renvoie aussi 0 :
| OU | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 1 |
Le caractère qu’on utilise pour représenter cet opérateur OU est la barre verticale : |. Modifions à nouveau notre programme pour démontrer ceci :
#include <stdlib.h>
#include <stdio.h>
char *ft_unsigned_itoa_base(unsigned n, unsigned base);
int main(void)
{
unsigned int nb1;
unsigned int nb2;
unsigned int res;
char *nb_str;
nb1 = 2423;
nb2 = 10002;
nb_str = ft_unsigned_itoa_base(nb1, 2);
printf("Binary number 1:\t%s (Decimal: %010u)\n", nb_str, nb1);
free(nb_str);
nb_str = ft_unsigned_itoa_base(nb2, 2);
printf("Binary number 2:\t%s (Decimal: %010u)\n", nb_str, nb2);
free(nb_str);
res = nb1 | nb2;
nb_str = ft_unsigned_itoa_base(res, 2);
printf("Bitwise OR:\t\t%s (Decimal: %010u)\n", nb_str, res);
free(nb_str);
return (0);
}
Avec exactement les mêmes valeurs que dans l’exemple de l’opérateur bitwise AND, on se retrouve avec un résultat totalement différent. Ici, dès qu’il y a un 1 à une position dans l’un ou l’autre des nombres binaires ou dans les deux, il est reporté au résultat.
Comme pour l’opération précédente, on peut effectuer l’opération contraire à celle-ci, NON-OU (NOR en anglais) en faisant un complément à un du résultat : ~(nb1 | nb2).
L’opérateur bitwise OU exclusif (^)
L’ opérateur OU exclusif (XOR en anglais) a une différence fondamentale avec sa contrepartie, OU. Il ne renvoie vrai (1) que si l’un des deux bits a une valeur de 1, mais 0 si les deux sont à 1 ou si les deux sont à 0.
| OU-ex | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
On représente cet opérateur avec un caret, ou un chapeau : ^. Regardons la différence avec l’exemple précédent :
#include <stdlib.h>
#include <stdio.h>
char *ft_unsigned_itoa_base(unsigned n, unsigned base);
int main(void)
{
unsigned int nb1;
unsigned int nb2;
unsigned int res;
char *nb_str;
nb1 = 2423;
nb2 = 10002;
nb_str = ft_unsigned_itoa_base(nb1, 2);
printf("Binary number 1:\t%s (Decimal: %010u)\n", nb_str, nb1);
free(nb_str);
nb_str = ft_unsigned_itoa_base(nb2, 2);
printf("Binary number 2:\t%s (Decimal: %010u)\n", nb_str, nb2);
free(nb_str);
res = nb1 ^ nb2;
nb_str = ft_unsigned_itoa_base(res, 2);
printf("Bitwise XOR:\t\t%s (Decimal: %010u)\n", nb_str, res);
free(nb_str);
return (0);
}
Encore une fois, sans changer les valeurs de nos nombres binaires, on obtient un résultat très différent car seuls les bits de valeur 1 qui apparaissent dans l’un des nombres mais pas dans l’autre sont ajoutés au résultat.
Et bien sûr, l’opération contraire, NON-OU exclusif (XNOR en anglais), il faut tout simplement faire ~(nb1 ^ nb2).
Pourquoi utiliser le bit shifting et les opérations bitwise ?
Evidemment, l’utilité du bit shifting et des opérations bitwise semble à première vue assez limitée. La vaste majorité des langages de programmation s’occupent de celles-ci dans les coulisses, au moment de la compilation par exemple. Mais au delà de la satisfaction intellectuelle que ces opérateurs peuvent nous donner en nous permettant de nous rapprocher du fonctionnement interne d’un ordinateur, ils sont aussi très efficaces.
En effet, les opérations de manipulation de bits sont des actions primitives, triviales pour un CPU. Elles ne prennent qu’un cycle à effectuer. Pour la plupart des processeurs, c’est largement plus rapide qu’une multiplication ou une division. Même avec les avancées technologiques des processeurs modernes qui peuvent effectuer ces opérations arithmétiques et logiques pratiquement aussi vite que les opérations bitwise et de bit shifting, ces dernières consomment tout de même moins d’énergie et de ressources.
La manipulation directe de bits est donc particulièrement intéressante dans des environnements à faibles ressources, ou l’on se doit d’optimiser autant que possible la vitesse ainsi que l’usage mémoire de notre code.
Exemples pratiques de bit shifting et d’opérations bitwise
Il y a une multitude d’applications intéressantes pour le bit shifting et les opérations bitwise, que ce soit pour optimiser une opération mathématique ou pour stocker la carte du terrain dans un jeu vidéo en 2D. Les quatre exemples ci-dessous ne sont que quelques pratiques courantes.
Vérifier rapidement si un nombre est pair ou impair
Il va de soi que si un nombre binaire est pair, le bit de poids faible sera 0, et s’il est impair, ce sera 1. On peut donc vérifier n’importe quel nombre avec l’opérateur &, comme ceci :
#include <stdio.h>
int main(void)
{
int x;
x = 108; // 0110 1100
if (x & 1) // 0110 1100 & 0000 0001 = 0000 0000 = faux
printf("%d is an odd number.\n", x);
if (!(x & 1))
printf("%d is an even number.\n", x);
return (0);
}
Vu que l’opérateur bitwise & compare deux bits et reçoit un 1 si les deux sont à 1 mais 0 autrement, la logique s’explique alors comme ceci :
108 = 1101100
1 = 0000001
& = 0000000 -> résultat faux (0), le nombre est pair.
107 = 1101011
1 = 0000001
& = 0000001 -> résultat vrai(1), le nombre est impair.
Vérifier si un nombre est une puissance de deux
La méthode pour déterminer si un nombre est une puissance deux consiste a diviser ce nombre par deux de façon répétée jusqu’à ne plus pouvoir. S’il y a un reste, ce n’est pas une puissance de 2, mais si on arrive à 1 sans avoir de reste, on sait que c’était une puissance de deux. Il existe une méthode bien plus simple et efficace avec les opérations bitwise :
#include <stdio.h>
int main(void)
{
int x;
x = 1024;
if (x != 0 && (x & (x - 1)) == 0)
printf("%d is a power of 2.\n", x);
else
printf("%d is not a power of 2.\n", x);
x = 512;
if (x != 0 && (x & (x - 1)) == 0)
printf("%d is a power of 2.\n", x);
else
printf("%d is not a power of 2.\n", x);
x = 800;
if (x != 0 && (x & (x - 1)) == 0)
printf("%d is a power of 2.\n", x);
else
printf("%d is not a power of 2.\n", x);
return (0);
}
Le fonctionnement de cette expression repose sur le fait que l’on sait qu’un nombre qui est une puissance de 2 aura une notation particulière en binaire. Chaque puissance de 2 est un nombre qui ne contient qu’un seul bit à 1, tous les autres bits sont à 0 :
x = 0100 0000 (64)
x - 1 = 0011 1111 (63)
& = 0000 0000
La condition (x & (x -1)) == 0 retourne vrai (1).
Le nombre 64 est une puissance de 2.
Par contre un nombre binaire qui n’est pas une puissance de 2 aura un “1” à plusieurs positions différentes :
x = 0010 1010 (42)
x - 1 = 0010 1001 (41)
& = 0010 1000
La condition (x & (x -1)) == 0 retourne faux (0) !
Le nombre 42 n'est pas une puissance de 2.
Échanger deux variables sans variable temporaire
Une variable temporaire, aussi éphémère qu’elle soit, prend de la place dans la mémoire. On peut échanger les valeurs de deux variables sans aucune variable temporaire grâce à l’opérateur bitwise ^ . Gardons à l’esprit que l’opérateur OU exclusif ne met de 1 que là où l’un des deux bits a une valeur de 1. Étudions l’exemple ci-dessous :
#include <stdio.h>
int main(void)
{
int a;
int b;
a = 3; // 0011
b = 2; // 0010
printf("Before swap: a = %d, b = %d\n", a, b);
// a = 0011, b = 0010
a ^= b; // a = 0011 ^ 0010: a = 0001
b ^= a; // b = 0010 ^ 0001: b = 0011
a ^= b; // a = 0001 ^ 0011: a = 0010
// a = 0010, b = 0011
printf("After swap: a = %d, b = %d\n", a, b);
return (0);
}
Stocker plusieurs drapeaux booléens
Un booléen, c’est un type de variable simple qui représente deux états possibles : vrai ou faux. Or, un booléen est toujours stocké en mémoire sur 1 byte, c’est à dire au moins 8 bits. Il nous suffit pourtant d’un seul bit pour représenter ces deux états : 1 pour vrai, 0 pour faux…
Si on a plusieurs drapeaux à gérer, il est bien plus rentable en termes d’espace mémoire de les stocker tous dans la même variable. Par exemple, trois drapeaux déclarés dans leur propre variable booléenne occuperaient chacun 1 byte, donc 3 bytes au total. Grâce aux opérations bitwise, on peut plutôt stocker ces trois drapeaux dans un seul char, c’est à dire dans 1 byte au total. C’est d’ailleurs sur ce principe que les codes erreur des environnements Unix fonctionnent, pour prendre un exemple.
#include <stdbool.h>
#include <stdio.h>
#define FLAG_1 0b00000001
#define FLAG_2 0b00000010
#define FLAG_3 0b00000100
int main(void)
{
// Si l'on utilise des booléens comme :
// bool flag_1 = true;
// bool flag_2 = false;
// bool flag_3 = false;
// On utilise 3 bytes de mémoire, 1 byte pour chaque variable.
// Par contre un char prend seulement 1 octet de mémoire
// et peut donc stocker jusqu'à 8 drapeaux !
char flags;
flags = 0; // 0000 0000
// Attribuer la valeur "vraie" (1) à un drapeau :
flags |= FLAG_2; // 0000 0000 | 0000 0010 = 0000 0010
flags |= FLAG_1; // 0000 0010 | 0000 0001 = 0000 0011
// Verifier l'état d'un drapeau :
if (flags & FLAG_1) // 0000 0011 & 0000 0001 = 0000 0001 = vrai
printf("Flag 1 is true.\n");
else
printf("Flag 1 is false.\n");
if (flags & FLAG_2) // 0000 0011 & 0000 0010 = 0000 0010 = vrai
printf("Flag 2 is true.\n");
else
printf("Flag 2 is false.\n");
if (flags & FLAG_3) // 0000 0011 & 0000 0100 = 0000 0000 = faux
printf("Flag 3 is true.\n");
else
printf("Flag 3 is false\n");
// Attibuer la valeur "faux" (0) à un drapeau :
flags ^= FLAG_2; // 0000 0011 ^ 0000 0010 = 0000 00001
if (flags & FLAG_2) // 0000 0001 & 0000 0010 = 0000 0000 = faux
printf("Oops, flag 2 is still true.\n");
else
printf("Flag 2 is now false.\n");
return (0);
}
Ce qui est bien utile, c’est que si on a besoin de stocker plus de 8 drapeaux, on peut passer à un type de variable de capacité supérieure. Un short int qui nous permettra d’en stocker jusqu’à 16 et un int, jusqu’à 32 !
Bit twiddling
On appelle la manipulation de bits le “bit twiddling” (littéralement “tripotage de bits” en français) ou le “bit bashing” (“cogner les bits”), particulièrement dans le cas de solutions astucieuses ou peu évidentes. Parfois, ces termes peuvent être utilisés de manière péjorative pour les manipulations superflues qui rendent le code source difficilement lisible et que les optimisations obtenues sont négligeables.
Prennons soin, alors, d’utiliser ces manipulations de manière appropriée, lorsque le besoin d’optimisation se fait sentir. La collection de Sean Anderson sur sa page intitulée Bit Twiddling Hacks [stanford.edu] est riche en exemples utiles de manipulation de bits.
Sources et lectures supplémentaires
- Charles Petzold, 1999, Code: The Hidden Language of Computer Hardware and Software
- Wikipédia, Fonction logique [wikipedia.org]
- Wikipédia, Manipulation de bits [wikipedia.org]
- LLWardIII, Bitwise Operations and Why You Might Care [divnull.com]
- Sreedev Kodichath, Real World Uses of Bitwise Operators [medium.com]
- Sean Anderson, Bit Twiddling Hacks [stanford.edu]