Aller au contenu
Topos Uranos
Français

Bits et bibliothèque mathématique

Résumé

Pour le processeur, un entier est une rangée de bits, et C++ offre des opérateurs qui agissent sur cette rangée colonne par colonne : &, |, ^ et ~, ainsi que les décalages << et >>. Cette leçon apprend à les calculer à la main, à s’en servir pour ranger plusieurs drapeaux dans un seul entier par la technique des masques, et à reconnaître les décalages que la norme ne définit pas. Elle explique ensuite pourquoi 2 ^ 3 vaut 1 et non 8, et pourquoi les opérateurs bit à bit exigent des parenthèses. La seconde moitié présente la bibliothèque mathématique : les fonctions de <cmath>, les constantes de <numbers>, le plus grand commun diviseur et le plus petit commun multiple de <numeric> et les fonctions de bits de <bit>, avec un principe qui vaut dans tout langage : ce que la bibliothèque offre correct et éprouvé ne se réécrit pas.

Objectifs d’apprentissage

  1. Calculer à la main le résultat de &, |, ^, ~ et des décalages sur de petits entiers.
  2. Distinguer les décalages définis (y compris ceux des nombres strictement négatifs, depuis C++20) de ceux qui sont un comportement indéfini, et prédire le résultat des premiers.
  3. Utiliser des masques pour tester, allumer, éteindre et basculer un bit.
  4. Expliquer pourquoi 2 ^ 3 vaut 1 et non 8, et choisir entre std::pow et un décalage selon le cas.
  5. Utiliser des fonctions de <cmath> (std::sqrt, std::pow, std::abs, std::hypot, les fonctions trigonométriques) et les constantes de <numbers>, comme std::numbers::pi, dans des formules.

Opérateurs bit à bit

La leçon Les entiers et leur représentation a montré qu’un int est une rangée de bits, 32 sur les systèmes du cours, et que sa valeur est la somme des poids des positions où se trouve un 1. Jusqu’ici, pourtant, le programme n’a traité l’entier que comme un nombre : il l’a additionné, multiplié et divisé. Or la même rangée admet une autre lecture, comme une collection de 32 réponses par oui ou par non, et pour cette lecture C++ dispose de quatre opérateurs qui travaillent sur les bits un par un, sans retenue d’une position à l’autre.

On numérote les bits depuis la droite, en commençant par 0 : le bit kk est celui de poids 2k2^k. Ainsi, dans 1212, qui s’écrit 1100 en binaire, les bits 2 et 3 sont allumés, et les bits 0 et 1 éteints.

Voici les opérateurs. Le ET bit à bit, a & b, a un 1 à chaque position où a et b ont tous deux un 1. Le OU bit à bit, a | b, a un 1 là où au moins l’un des deux en a un. Le OU exclusif, a ^ b, a un 1 là où exactement l’un des deux en a un, c’est-à-dire là où les bits diffèrent. La négation bit à bit, ~a, n’a qu’un opérande et inverse chaque bit. Les tables des trois premiers, pour un couple de bits pp et qq, sont celles de la conjonction, de la disjonction et de la disjonction exclusive :

pqp&qp∣qp^q11110100110101100000\begin{array}{cc|ccc} p & q & p \mathbin{\&} q & p \mid q & p \mathbin{\hat{}} q \\ \hline 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}

Qui a étudié le cours Logique mathématique I reconnaîtra ici les connecteurs propositionnels, avec 1 pour vrai et 0 pour faux : un opérateur bit à bit n’est rien d’autre qu’un connecteur appliqué à toutes les colonnes à la fois. De là découle la méthode de calcul à la main : on écrit les deux nombres en binaire, l’un au-dessus de l’autre, alignés à droite, et on applique la table dans chaque colonne, sans se soucier des voisines.

ExempleDouze et dix, colonne par colonne

Les nombres 12=12 = 1100 et 10=10 = 1010 ont la propriété que leurs quatre colonnes parcourent les quatre combinaisons de deux bits ; c’est pourquoi ils permettent de voir les trois tables à la fois.

Démonstration

  1. Les données : 1100 vaut 12 et 1010 vaut 10. Les colonnes, de gauche à droite, portent les couples (1,1)(1, 1), (1,0)(1, 0), (0,1)(0, 1) et (0,0)(0, 0).

  2. Première colonne de 12 & 10 : les deux bits valent 1, et le ET donne 1.

  3. Deuxième colonne : 1 et 0. Il suffit d’un 0 pour que le ET donne 0.

  4. Troisième colonne : 0 et 1 ; le ET donne encore 0.

  5. Quatrième colonne : 0 et 0 donnent 0. La rangée résultat, 1000, vaut 8 : 12 & 10 vaut 8.

  6. Le OU allume chaque colonne qui contient au moins un 1 : 1110, c’est-à-dire que 12 | 10 vaut 14.

  7. Le OU exclusif n’allume que les colonnes dont les bits diffèrent : 0110, et 12 ^ 10 vaut 6.

Le programme suivant vérifie la figure. La spécification de format {:04b}, présentée dans la leçon sur les entiers, écrit une valeur en binaire avec quatre chiffres, complétés par des zéros.

Programme en C++
#include <print>​int main(){    const int a{0b1100};    const int b{0b1010};    std::println("a     = {:04b} = {}", a, a);    std::println("b     = {:04b} = {}", b, b);    std::println("a & b = {:04b} = {}", a & b, a & b);    std::println("a | b = {:04b} = {}", a | b, a | b);    std::println("a ^ b = {:04b} = {}", a ^ b, a ^ b);    std::println("~a    = {}", ~a);}
Sortie
a     = 1100 = 12b     = 1010 = 10a & b = 1000 = 8a | b = 1110 = 14a ^ b = 0110 = 6~a    = -13

La dernière ligne mérite une explication. La négation inverse les 32 bits de a, et pas seulement les quatre qu’on écrit : les 28 zéros de gauche deviennent des uns, et un int qui commence par 1 est strictement négatif en complément à deux. Or, en complément à deux, l’opposé d’un nombre s’obtient en inversant ses bits et en ajoutant 1, c’est-à-dire −x=∼x+1-x = {\sim}x + 1 ; par conséquent, ∼x=−x−1{\sim}x = -x - 1, et ~12 vaut −13-13. La négation bit à bit d’un entier signé donne donc un nombre qui intéresse rarement comme nombre : il intéresse comme motif, et c’est pourquoi on manipule de préférence les bits dans des types non signés, comme on le verra à propos des masques.

Un avertissement sur les petits types. Avant d’opérer, C++ convertit en int tout opérande d’un type entier plus étroit, comme std::uint8_t ; c’est la promotion que la leçon Arithmétique a décrite pour les opérations arithmétiques, et elle vaut aussi ici. Il s’ensuit que ~flags, avec flags de type std::uint8_t et de valeur 5, n’est pas l’octet 11111010, mais l’int −6-6, dont les 32 bits comprennent 24 uns ajoutés à gauche ; ce n’est qu’en le rangeant de nouveau dans un std::uint8_t qu’on le réduit à huit bits et qu’on retrouve l’octet attendu, 250.

Il ne faut pas confondre les opérateurs bit à bit avec les opérateurs logiques de la leçon Relations et logique. 6 && 3 vaut true : les deux opérandes sont non nuls, et le résultat est un bool. 6 & 3, en revanche, est un entier, celui que forment les colonnes où les deux ont un 1. De plus, && s’évalue en court-circuit et & évalue toujours ses deux opérandes.