Ouvrir le menu principal

Les opérations bit à bit/Les opérations bit à bit

< Les opérations bit à bit

Pour commencer ce livre, nous devons d'abord parler des opérations logiques : que sont-elles, à quoi servent-elles ? Ces opérations logiques travaillent sur des suites de bits d'une longueur fixe, des nombres pour simplifier. Ces opérations modifient directement l'écriture binaire d'un nombre, la suite de bits correspondante. Il en existe de deux types, les instructions bit à bit et les instructions de décalage, que nous allons voir l'une après l'autre. Pour les connaisseurs, nous allons voir quelques opérations iconiques, comme les décalages et les rotations, mais aussi comment concevoir une unité de calcul 2 à 3 bit, les masques et quelques autres opérations.

Sections

Opérations bit à bit proprement ditModifier

Les instructions logiques les plus courantes sont au nombre de 4 : le NON, le ET, le OU, et le XOR. Toutes ces instructions vont travailler sur des bits individuels d'un ou de deux nombres, et leur faire subir une opération bien précise. Cette opération prend deux bits (un seul pour le NON) et donne un résultat codé sur un bit. Le fonctionnement de cette opération peut être définie par ce qu'elle fait sur un bit, son comportement étant résumé dans un tableau qu'on appelle la table de vérité. Leur résultat n'est pas vraiment interprétable mathématiquement, ou alors avec un sens vraiment idiosyncratique. La plus simple est clairement l'opération NOT, qui inverse tous les bits d'un nombre. Mais il est aussi possible de prendre deux nombres, de faire un ET/OU/XOR entre les bits de même poids, et de renvoyer le tout en guise de résultat. Formellement, ce sont les seuls types d'opérations bits à bit : l'inversion des bits d'un nombre, un ET entre deux nombres, un OU entre deux nombres, et un XOR entre deux nombres (avec leurs dérivées, tel un NAND ou un NOR).

L’opération d'inversion (NOT)Modifier

L'inversion bit à bit va inverser tous les bits d'un nombre : Les 0 deviennent des 1, et les 1 deviennent des 0. Exemple : le nombre 01110011 va devenir 10001100. La table de vérité du NOT est celle-ci :

Bit A Résultat (NOT A)
0 1
1 0

Le NOT d'un bit et/ou d'un nombre sera noté comme ceci :  .

On peut remarquer qu'inverser deux fois de suite un bit redonne le bit initial. Autrement dit,  .

 
La droite Δ d’équation x = − 1/2 partage le domaine des opérations bit à bit en deux moitiés, contenant chacune 2^31 nombres entiers. L’opérateur NOT transforme un entier n donné en – (n + 1), en inversant les valeurs de ses trente-deux bits. La symétrie d’axe Δ donne une image mentale de cette inversion des bits.

Le résultat de cette opération dépend de l'encodage du nombre. Plus précisément, l'interprétation du résultat n'est pas la même selon que le nombre inversé soit non-signé, en complément à 1, en complément à 2, etc.

  • Pour un entier en complément à 1, le NOT sert à obtenir l'opposé d'un nombre : dit autrement,  .
  • Pour un entier en complément à deux, le NOT donne l'opposé d'un nombre auquel on aurait retranché 1 :  .
  • Pour un entier non-signé, le NOT va donner la valeur  .

Le dernier résultat est facile à comprendre. On sait que la somme   donne un nombre de n bits dont tous les bits sont à 1. Un tel nombre vaut exactement, par définition,  . On a donc  , ce qui donne le résultat précédent avec quelques manipulations algébriques triviales. L'image de droite montre ce que fait l'opérateur NOT sur un entier en complément à deux.

L'opération ET (AND)Modifier

Vient ensuite le ET bit à bit, aussi appelé AND bit à bit. Celui-ci prend deux nombres en opérandes et donne un nombre comme résultat. Sur ces deux nombres, il va prendre les bits qui sont à la même place et va effectuer dessus une petite opération qui donnera le bit du résultat. Cette opération est un simple AND binaire. Ce AND binaire prend deux bits, A et B, et fonctionne comme ceci :

Bit a Bit b Résultat
0 0 0
0 1 0
1 0 0
1 1 1

Cet opérateur AND bit à bit est symbolisé comme ceci :  

Exemple :  

L'instruction AND bit à bit est commutative :  

Elle est aussi associative :  

Elle est aussi distributive avec le OR bit à bit :  

On peut aussi remarquer qu'elle dispose de la propriété d'idempotence :  

Petite remarque :  

De plus,  

L'opération OU (OR)Modifier

Vient ensuite le OR bit à bit. Il fonctionne comme le AND bit à bit sauf qu'il effectue un OR binaire entre les bits du nombre. Ce OR binaire prend deux bits, A et B, et fonctionne comme ceci :

Bit a Bit b Résultat
0 0 0
0 1 1
1 0 1
1 1 1

Cet opérateur OR bit à bit est symbolisé comme ceci :  . Cependant, pour éviter toute ambiguité en présence d'addition, nous utiliserons parfois le symbole   dans la suite du cours.

Exemple :  

L'opérateur OR est commutatif :  

Il est aussi associatif :  

Il est aussi distributif avec le AND bit à bit :  

On peut aussi remarquer qu'il dispose de la propriété d'idempotence :  

Petite remarque :  

L'opération OU exclusif (XOR)Modifier

Vient ensuite le XOR bit à bit. Il fonctionne comme le AND et le OR bit à bit sauf qu'il effectue un XOR binaire entre les bits du nombre. Ce XOR binaire prend deux bits, A et B, et fonctionne comme ceci :

Bit a Bit b Résultat
0 0 0
0 1 1
1 0 1
1 1 0

Cet opérateur XOR bit à bit est symbolisé comme ceci :  

Exemple :  

L'opérateur XOR est commutatif :  

Il est aussi associatif :  

Petite remarque :  

Autre remarque :  

Décalages et rotationsModifier

A coté des opérations précédentes, on trouve les opérations de décalage, qui décalent un nombre binaire de un ou plusieurs rangs vers la gauche ou la droite. A priori, cette opération n'a rien de compliqué, à un détail près : lorsqu'on décale un nombre, certains bits sont inconnus, ce qui laisse des vides qu'il faut combler. Pour résoudre ce petit problème, il existe diverses solutions, qui donnent naissance à plusieurs types de décalages : les décalages logiques, les décalages arithmétiques et les rotations.

Décalages logiquesModifier

 
Décalage logique

L'idée la plus immédiate serait de remplir ces vides avec des zéros, ce qui donne un décalage logique. Pour les décalages à droite, on peut aussi remplir les vides avec le bit de poids fort (on verra plus tard pourquoi dans le cours). On peut remarquer que les décalages logiques ne sont pas spécifiques au binaire. L'opération similaire en décimal serait d'ajouter des zéros à la fin d'un nombre, ce qui serait équivalent à multiplier par 10, 100, 1000, bref : par une puissance de 10. Cette logique vaut aussi pour le décalage en binaire, si on se rappelle toutefois qu'on doit compter en base 2 : un décalage logique correspond à une multiplication ou division par 2, 4, 8, 16, ..., bref, par une puissance de deux. L'utilité principale des opérations de décalage est donc qu'elles permettent de faire simplement des multiplications ou divisions par  , pour les entiers non signés. Précisément, un décalage vers la gauche de   rangs est équivalent à une multiplication par  , alors que le décalage vers la droite qui revient à diviser un nombre entier par  . Cette propriété est souvent utilisée par certains compilateurs, qui préfèrent utiliser des instructions de décalages (qui sont des instructions très rapides) à la place d'instructions de multiplication ou de division qui ont une vitesse qui va de moyenne (multiplication) à particulièrement lente (division). Il faut cependant signaler que lorsqu'on effectue un décalage à droite, certains bits de notre nombre vont sortir du résultat et être perdus : le résultat est tronqué ou arrondi vers zéro. Plus précisément, le résultat d'un décalage à droite de n rangs sera égal à la partie entière du résultat de la division par  .

Décalages arithmétiquesModifier

 
Décalage arithmétique

Le décalage logique ne donne cependant pas de bons résultats avec des nombres signés : on obtient un résultat qui n'a pas grand sens mathématiquement. Il faut dire que le bit de signe est alors remplacé par un zéro, ce qui peut inverser le signe du résultat. Pour pouvoir effectuer des divisons par   sur des nombres négatifs avec un décalage, on a inventé les décalages arithmétiques ou arithmetical shift. Ces instructions sont équivalentes à une multiplication/division par  , que le nombre soit signé ou non. La différence avec un décalage logique est la méthode d'arrondi des nombres négatifs. Avec les décalages arithmétiques, les nombres négatifs sont arrondis vers moins l'infini. Pour donner un exemple, 92 sera arrondi en 4, tandis que −92 sera arrondi en −5.

Rotations de bitsModifier

 
Rotation de bits

Les rotations sont identiques aux décalages, à part que les bits qui sortent du nombres sont ceux qui rentrent pour combler les vides. Ces opérations sont très utiles en cryptographie, et sont notamment très utilisées dans certaines algorithmes de chiffrement. Les rotations sont aussi très utiles dans certains particuliers dans lesquels ont doit manipuler des données bits par bits. Par exemple, un calcul du nombre de bits à 1 dans un nombre peut s'implémenter de façon naïve avec des instructions de rotation.

Règles de calcul utilesModifier

Dans la suite du cours, nous ferons souvent usage de quelques équations qui mélangerons les différentes opérations bit à bit. Ne vous étonnez donc pas si vous voyez des équations de ce style :

 

Il existe quelques règles mathématiques qui nous permettront de simplifier de telles équations.

Règles pour les expressions booléennesModifier

Commençons par les règles qui impliquent uniquement des opérations bit à bit/booléens. Nous en avons déjà vu la plus grande partie plus haut, en parlant de la distributivité et de l'associativité des différents opérateurs. En voici la liste complète :

Commutativité

 
 
 

Associativité

 
 
 

Distributivité

 
 

Idempotence

 
 

Élément nul

 
 

Élément Neutre

 
 
 

Loi de De Morgan

 
 

Complémentarité

 
 
 
 
 
 

Règles pour les expressions booléennes et arithmétiquesModifier

Il est parfaitement possible de mixer des opérations booléennes avec des opérations arithmétiques. Par exemple, on peut se demander ce que vaut  , un calcul qui sera notamment beaucoup utilisé dans la suite du cours. Les règles qui régissent les mélanges/interactions entre opérations mathématiques et opérateurs bit à bit dépendent sdu codage des nombres, notamment pour les nombres signés. Nous allons supposer que les nombres signés sont codés en complètement à deux. Les règles qui en découlent sont résumées dans le tableau suivant :

Addition

 
 
 
 

Soustraction  

 
 
 

Opposé  

 
 
 
 

Les équations pour l'opposé et la soustraction peuvent se déduire assez facilement de l'équation  , définition de l'opposée d'un nombre en complètement à deux. En guise d'exercice, vous pouvez tenter d'en déduire l'équation  . Si vous utilisez les règles sur les opérateurs booléens, vous devriez y arriver sans trop de peine.

Règles pour les expressions booléennes et comparaisonsModifier

Il est parfaitement possible de comparer des expressions booléennes, et certaines égalités ou inégalités sont toujours vraies. On peut rapidement se rendre compte que :

 

Pour les opérations mathématiques, les relations suivantes sont importantes à connaitre :

  ;

  ;

 .