Les opérateurs bits à bits employés sur des nombres entiers Online

Introduction du cours

Les opérateurs bits à bits (bitwise en anglais, j'emploierai ce terme désormais) permettent d'effectuer des manipulations sur des nombres binaires.

Euh, tu nous parle en quoi là ? Bits, binaire ? Késako ?
Tu peux pas parler en français ?

Je vais tout vous expliquer dans ce tuto, pas de panique ! ;)

Révision sur les puissances mathématiques

Cette sous-partie est pour ceux qui ne connaissent pas les puissances mathématiques ou qui veulent revoir ce sujet en détail (bouh les noobs :p ).
Si vous connaissez ce sujet sur le bout des doigts, vous pouvez sans aucun problème passer cette sous-partie !
Une puissance s'écrit $\(x^y\)$. Elle consiste a multiplier x par lui-même autant de fois que la valeur de y.
Par exemple, $\(2^3\)$ = 2 multiplié par lui-même 3 fois = 2 × 2 × 2 = 8
Le nombre est appelé la base de la puissance, et le nombre de fois qu'il faut le multiplier est appelé l'exposant.

En langage C, il n'y a pas d'opérateur de base pour faire une puissance.
Il faut employer la fonction pow après avoir inclus math.h.

Il existe également des puissances négatives, qui divisent le nombre 1 par la base autant de fois que le spécifie l'exposant.
Par exemple, $\(2^{-3}\)$ = 1 / (2 multiplié par lui même 3 fois) = 1 / (2 × 2 × 2) = 1 / 8.
Enfin, toute puissance dont l'exposant est 0 est égale à 1.

Quelques notions de bases sur les bases

Ne pas confondre les systèmes de numération nommés « bases » avec la base d'une puissance.

Nous allons maintenant parler des systèmes de numération dits « positionnels » comme la base décimale qu'on utilise généralement.

Dans notre système, les nombres sont écrits comme des sommes d'unités, de dizaines, de centaines, et caetera.
Et si on le dit d'une autre façon : les nombres sont écrits comme des sommes de $\(10^0\)$ , $\(10^1\)$ , $\(10^2\)$ , et caetera. Toutes ces puissances ont pour base le nombre 10, d'où le nom de base décimale. Les exposants correspondent à la position du chiffre: le premier chiffre à gauche de la virgule correspond au nombre de $\(10^0\)$, le suivant au nombre de $\(10^1\)$ et ainsi de suite.

En système de base binaire, c'est exactement la même chose sauf que les nombres sont décrits avec des $\(2^0\)$ , $\(2^1\)$ , $\(2^2\)$ , et caetera.

(et pour les nombres décimaux, on emploie des puissances négatives, mais ce n'est pas le sujet du tuto ^^ )

À cela il faut ajouter le fait que pour dire quelle quantité d'unités, de dizaines, etc. composent le nombre, on ne peut utiliser que des chiffres de 0 (inclus) au nombre de le base (exclus). (Ceci permet d'avoir une représentation unique pour chaque nombre dans chaque base si on rajoute quelques conditions.)
Donc la base décimale, ou base 10, utilise des chiffres de 0 à 9, et la base binaire, ou base 2, utilise des chiffres de 0 à 1, c'est-à-dire uniquement 0 et 1.

Voici, par exemple, la preuve que le nombre 13 en base binaire est 1101 :

1

1

0

1

$\(1\times{}2^3\)$ 

$\(1\times{}2^2\)$ 

$\(0\times{}2^1\)$ 

$\(1\times{}2^0\)$ 

8

4

0

1

Et 8 + 4 + 0 + 1 = 13 !

On retombe donc sur nos pattes.

Qu'est-ce donc qu'un bit ? Un bit est un chiffre d'un nombre écrit en système de base binaire.

Par exemple, dans notre exemple avec 1101, les bits sont 1, 1, 0, et 1. On appelle bit de poids fort le bit correspondant à l'exposant (et donc à la puissance) la plus élevée et bit de poits faible celui correspondant à l'exposant le moins élevé. Pas si compliqué hein ? :-°

Voici un algorithme pour convertir un nombre décimal en sa représentation binaire :

• On trouve d'abord la puissance de 2 (c'est-à-dire une puissance dont la base est 2) qui est directement inférieure à ce nombre et on le note.

• Ensuite on regarde la puissance dont l'exposant est le même que celui correspondant au chiffre précédent auquel on a soustrait 1, et si on peut additionner le résultat de cette puissance au nombre précédent sans dépasser le nombre décimal, on le note.

• On réitère l'étape précédente jusqu'à arriver à l'exposant -1.

• Maintenant, comment transformer ce résultat en nombre binaire ?
  Comme ceci : on regarde l'exposant de la première puissance : c'est le nombre de bits du nombre binaire, on inscrit un 1 dans ce premier bit.

• Ensuite, on regarde l'exposant de la puissance suivante, ça veut dire que le bit à la position nombre total de bits - cet exposant = 1

• On réitère cette étape jusqu'à arriver à la fin des puissances notées.

• Et on remplace les bits restants par 0.

Ça parait très compliqué comme ça, mais ce n'est pas vraiment possible de l'expliquer plus simplement, et une fois que vous aurez compris le principe, vous allez trouver ça très facile. :) (Si vous ne comprenez pas, rassurez-vous, ce n'est pas tellement essentiel. ;) )

Présentation des opérateurs bitwise

Bon, tu nous as toujours pas dis ce
que c'était tes opérateurs bizarroïdes ...

Les opérateurs bitwise effectuent des opérations sur la représentation binaire des nombres qui comparent un à un leurs bits. Ce sont des opérations extrêmement rapides car (à de rarissimes et antiques exceptions près) les processeurs travaillent sur les nombres de cette façon. Voici leur liste :

| qui vaut 1 si un des deux bits comparés contient un 1 ou si les deux le contiennent. (on l'appelle le "ou inclusif")
^ qui vaut 1 si et seulement si les deux bits sont différents. (on l'appelle le "ou exclusif")
& qui vaut 1 si les deux bits valent tous les deux 1. (on l'appelle le "et")

Quand ils ne renvoient pas 1 pour une position, ils renvoient bien sûr… 0.

Par exemple 2 ^ 3 va renvoyer 1 car :

2

^

3

--

10

^

11

= 01

--

--

--

= 1

Remarquons que le bit de poids faible donne la parité du nombre:

if (i & 1) { printf("%i est impair.\n", i); } else { printf("%i est pair.\n", i); }

Attention : Ces opérateurs effectuent des opérations bits à bits, et il faut savoir que si les nombres n'ont pas tous les deux le même nombre de bits, des 0 seront rajoutés à gauche du nombre qui a le moins de bits. Ça ne change rien au calcul quel que soit le nombre de 0 rajoutés.

Le codage interne des nombres signés négatifs et des nombres flottants est dépendant de l'implémentation. Ainsi, vous n'aurez pas toujours ce que vous attendez en employant les opérateurs bits à bits sur ce type de nombres: ceux-ci opèrent en réalité sur la représentation interne du nombre, qui n'est standardisée par la norme C que pour les entiers non signés.

Pour les nombres flottants, le compilateur refuse toute opération sur les bits sans l'utilisation d'un cast.

Les opérateurs bitwise de décalage

Mais ce que je ne vous ai pas dit, c'est qu'il y a d'autres opérateurs bitwise !

>> qui décale les bits vers la droite.
<< qui décale les bits vers la gauche.
>< qui fait un smiley bizarre et n'est pas un opérateur valide.

3 << 1 veut dire "décaler les bits du nombre 3 (soit 11) de 1 bit vers la gauche", ce qui va donner le nombre 110, soit 6 dans notre bon vieux système décimal.

(en effet, les bits non utilisés sont remplis de 0)

On constate que x << y est égal à $\(x\times{}2^y\)$.
C'est le même principe avec >>, sauf que là le nombre est tronqué !

Par exemple, pour multiplier un nombre par 2, on peut décaler ses bits de 1 vers la droite, soit effectuer l'instruction

nombre = nombre << 1; // Multiplie par 2

Enfin, il existe l'opérateur ~, qui inverse tous les bits d'un nombre. Tous ? Non, car la représentation d'un nombre en C n'est pas infinie. Si x est une variable de 32-bits valant 0, ~x est une valeur de 32-bits avec tous ses bits mis à 1.  (Ce dernier opérateur est unaire à l'inverse des autres: on l'écrit avant l'unique nombre sur lequel il opère.)

Intérêt de tout ça ?

C'est bien joli tout ça mais les opérateurs font tout le travail pour nous,
c'est facile, et en plus je ne vois pas l'intérêt de tout ça...

L'intérêt ? Bon ben je vais vous montrer quelques situations que vous ne pourriez résoudre sans les opérateurs bitwise !
Et comme je suis vicieux, ça servira aussi d'exercices !

Exercice 1

Arrondir un nombre entier stocké dans une variable non signée nommée n au nombre multiple de 8 inférieur, et ce en une ligne de code et sans utiliser de modulo !

n = (n >> 3) << 3;

Il suffisait d'y penser, n >> 3 divise le nombre par huit et le tronque, il suffit de le remultiplier par huit et on obtient un nombre arrondi !

Exercice 2

Écrire une instruction qui affiche le reste de la division d'un nombre par 8 sans utiliser de modulo ou de division !

printf("%u", (nombre & 7));

C'est tout à fait logique :
7 s'écrit 111 en binaire. Donc ça va comparer les 3 derniers bits avec 1 chacun, et sachant que 1 & 1 = 1 et que 0 & 1 = 0, les bits demeurent inchangés et les autres deviennent tous 0 car ils sont comparés avec 0. Les 3 derniers bits étant équivalents au reste de la division par 8 (c'est logique vu qu'on garde seulement la précision après le 8), eh bien ... ça marche.
Vous devez sûrement vous demander l'intérêt de ne pas utiliser le modulo ?
Le calcul est bien plus rapide par l'opération bitwise, si vous faites un petit programme, bien sûr on verra pas de différence, mais si vous le faites tourner sur un ordinosaure ou que vous devez répéter cette opération , ça peut faire une énorme différence de performances !

Cependant, le plus souvent, le compilateur peut réaliser de telles optimisations.

Exercice 3

Écrire une fonction qui renvoie le premier nombre pair qui est inférieur à un nombre impair passé en paramètre, si on envoie un nombre pair à la fonction, elle doit renvoyer ce nombre pair, et tout ça sans employer de condition et avec une seule instruction.

Ah aussi, je veux une solution utilisant les opérateurs de comparaison, et une solution utilisant les opérateurs de décalage.

Solution 1unsigned long pair_o_matic(unsigned long nombre) { return (nombre | 1) ^ 1; }

nombre | 1 remplace le dernier bit du nombre par un 1, ce qui rend le nombre impair, ensuite le ^ 1 remplace le dernier bit par un 0 ce qui le rend pair. On aurait pu également faire
Qui a dit que c'était tiré par les cheveux ?

Solution 2unsigned long pair_o_matic(unsigned long nombre) { return (nombre >> 1) << 1; }

Dans cette deuxième solution, c'est tout simplement le même principe que dans l'exercice 1 !

Exercice 4

Ecrire une fonction qui renvoie le xième bit d'un nombre en partant de la droite (la position du bit à récupérer étant passée en paramètre).

unsigned int recupererBit(unsigned int position, unsigned long nombre) { return ((1 << position) & nombre) >> position; }

Version naïve avec une boucle:

unsigned int recupererBit(unsigned int position, unsigned long nombre) { unsigned int i = 0; unsigned int puissanceDeDeux = 1; for (i = 0; i < position; i++) { puissanceDeDeux = puissanceDeDeux << 1; } return (nombre & puissanceDeDeux) >> i; }

Tout réside dans le fait que les puissances de 2 deviennent en binaire des nombres avec seulement un 1.

Du coup, quand on les compare avec & à un nombre, seul le bit précis est retenu, les autres deviennent 0. Cependant, il ne faut pas oublier de supprimer tout ce qui se trouve après le 1, car sinon on aurait des 0 en trop qui agrandiraient le nombre, d'où le décalage final.

Pour aller plus loin

Si vous vous y connaissez en électronique, les opérateurs |, &, et ^ ont du vous rappeler quelque chose...
En effet, ils sont utilisés pour décrire certains circuits électriques, et il est même possible de faire des calculs avec pour déterminer si le courant passe ou ne passe pas. Pour plus d'informations, un excellent lien de Wikipédia : L'algèbre de Boole.
Boole a également donné son nom à un type de données bien connu : le type Booléen.