Ouvrir le menu principal

Les opérations bit à bit/Version imprimable

< Les opérations bit à bit
Nuvola-inspired File Icons for MediaWiki-fileicon-ps.png

Ceci est la version imprimable de Les opérations bit à bit.

  • Si vous imprimez cette page, choisissez « Aperçu avant impression » dans votre navigateur, ou cliquez sur le lien Version imprimable dans la boîte à outils, vous verrez cette page sans ce message, ni éléments de navigation sur la gauche ou en haut.
  • Cliquez sur Rafraîchir cette page pour obtenir la dernière version du wikilivre.
  • Pour plus d'informations sur les version imprimables, y compris la manière d'obtenir une version PDF, vous pouvez lire l'article Versions imprimables.


Les opérations bit à bit

Une version à jour et éditable de ce livre est disponible sur Wikilivres,
une bibliothèque de livres pédagogiques, à l'URL :
https://fr.wikibooks.org/wiki/Les_op%C3%A9rations_bit_%C3%A0_bit

Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la Licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans Texte de dernière page de couverture. Une copie de cette licence est incluse dans l'annexe nommée « Licence de documentation libre GNU ».

Sections

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.

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 :

  ;

  ;

 .


Les subtilités du XOR

Dans cette partie, nous allons voir ce qu'il est possible de faire avec l'instruction XOR. Les techniques suivantes se basent sur les propriétés de l'opération XOR. Pour rappel, nous avons vu au premier chapitre que :   et  . Ces deux propriétés sont assez importantes, surtout la dernière. La première méthode a été utilisée dans le chapitre sur les masques, aussi nous ne l'utiliserons pas plus.

Inégalité des signes de deux entiersModifier

Déterminer si deux entiers ont des signes différents peut sembler trivial, mais vous n'aurez peut-être pas pensé que cela pouvait se faire avec une seule comparaison. Un code naïf pour résoudre ce problème devrait utiliser plusieurs comparaisons : une expression pour vérifier si la première variable est positive et l'autre négative (deux comparaisons), et une autre expression pour vérifier l'inverse (deux comparaisons, encore). Le code qui correspond serait le suivant :

int SignUnequals (int a , int b)
{
    return ( a >= 0 && b < 0 ) || ( a < 0 && b >= 0 ) 
}

Mais l'opération XOR permet de faire cette vérification en une seule comparaison. Pour comprendre pourquoi, il faut rappeler que le bit de poids fort donne le signe du nombre, peu importe la représentation des nombres utilisée. Cela fonctionne non seulement en signe-magnitude, mais aussi en complément à 1 ou à 2. Lorsque l'on fait un XOR entre deux nombres, les deux "bits de signe" seront XORés, comme tous les autres bits. OR, l'opération XOR renvoie un 1 si les deux bits sont différents et un 0 s'ils sont égaux ! Ainsi, après avoir XORé les deux nombres, le bit de poids fort dira si les deux bits de signe étaient égaux ou non. Il faudra juste comparer sa valeur avec 1 et/ou 0. Pour cela, on pourrait penser utiliser le code suivant :

int SignUnequals (int a , int b)
{
    return ((a ^ b) >> 31) & 1 ;
}

Mais il y a plus simple encore : on peut déduire le signe du résultat (et donc la valeur du bit de signe) en comparant avec 0 ! Si le résultat a pour bit de signe 1, il est négatif, donc inférieur à 0. Si ce bit de signe vaut 0, le résultat est supérieur ou égal à 0. On peut donc remplacer la sélection du bit de signe assez simplement par une comparaison avec 0. Ce qui donne le code suivant :

int SignUnequals (int a , int b)
{
    return (a ^ b) < 0 ;
}

Émulation d'instructionsModifier

L'instruction XOR permet parfois d'émuler certaines opérations plus complexes. Elle permet notamment d'émuler des transferts entre registres/variables ou des initialisations de registres. Son utilisation première est notamment la mise à 0 d'un registre ou d'une variable.

Mise à zéro rapideModifier

Initialiser une variable à 0 est une opération extrêmement courante. En conséquence, il vaut mieux la rendre la plus rapide possible. S'il n'y a pas de méthode particulière pour cela dans les langages de haut-niveau, les compilateurs ont cependant quelques possibilités d'optimisation. Il y a en effet plusieurs méthodes pour mettre un registre à 0 en assembleur, certaines n'étant compatibles qu'avec certains processeurs. Certains processeurs ont une instruction machine pour mettre à 0 un registre : c'est alors la solution idéale dans la (quasi-)totalité des cas. Sur les architectures n'ayant pas cette instruction, on peut utiliser une instruction MOV (ou équivalent). On peut l'utiliser en adressage immédiat : on place alors la constante 0 dans le registre. D'autres processeurs possèdent un registre spécial, qui conserve en permanence la valeur 0 et n'est pas accessible en écriture. Il suffit alors d'effectuer un MOV de ce registre vers le registre à initialiser. Mais il existe une dernière solution : faire un XOR entre le registre et lui-même. C'est notamment ce qui est fait sur les architectures x86. L'utilisation d'une opération XOR peut permettre d'utiliser moins de cycles d'horloge (exécution plus rapide) et/ou économiser de la mémoire (encodage plus court).

Pour comprendre pourquoi cette solution fonctionne, il faut rappeler que l'on obtient 0 lorsque l'on XOR un bit avec lui-même :  . Si cela vaut pour un bit, cela s'applique aussi quand on effectue un XOR bit à bit sur un nombre : chacun de ses bits sera donc XORé avec lui-même, ce qui fait qu'un nombre XOR lui-même donnera toujours zéro. Cette propriété est utilisé par les compilateurs pour mettre à zéro un registre. Sur les architectures x86, cette solution est légèrement meilleure que celle utilisant un MOV avec adressage immédiat. Cette dernière solution demande d'intégrer une constante en adressage immédiat, qui prend facilement 8 à 16 bits. Un nom de registre est beaucoup plus court, ce qui fait que la solution avec un XOR donne des instructions plus petites. Sur d'autres processeurs, qui ne supportent pas l'adressage immédiat, la constante est lue depuis la mémoire. En comparaison, un XOR entre deux registres ne va rien charger en RAM et est donc plus rapide.

Émulation du MOVModifier

L'opération XOR permet d'émuler une instruction MOV sur les processeurs qui n'en disposent pas, comme certains processeurs MIPS. Le MOV est alors remplacé par une opération XOR à trois adresses, qui XOR le registre à copier avec zéro, et place le résultat dans le registre de destination. L'opération est d'autant plus utile que ces processeurs disposent d'un registre en lecture seule, qui contient toujours la valeur 0.

Pour résumer : MOV Ra -> Rb <=> Ra XOR 0 -> Rb

Échange de deux variablesModifier

Si je vous demande d'échanger le contenu de deux entiers a et b, vous allez certainement écrire un code similaire à celui-ci :

int t = a ;
a = b ;
b = t ;

Mais il est possible d'échanger les valeurs de deux registres/variables, sans utiliser de registre/variable temporaire ! Pour cela, il existe différentes méthodes assez simples.

Échange par addition et soustractionModifier

La première méthode alternative qui utilise des additions et soustractions. Il faut effectuer ces opérations dans l'ordre suivant :

  •   ;
  •  ;
  •  .

Pour comprendre plus profondément pourquoi cette méthode marche, il suffit de regarder à chaque étape ce que l'on trouve dans A et dans B.

Etape Variable A Variable B
Avant l'opération A B
Première étape A - B B
Seconde étape A - B B + (A - B) = A
Troisième étape A - (A - B) = B A

Cependant, il y a un risque de débordement au niveau de l'addition, qui fait que cette technique fonctionne mal avec certaines opérandes. Cette technique utilise de plus des opérations arithmétiques, qui sont plus lentes que les opérations logiques sur de nombreux processeurs. Bref : il n'y a pas vraiment de raisons d'utiliser cette méthode.

Stupid XOR trickModifier

 
Stupid XOR Trick.

Une autre méthode se base sur les particularités de l'instruction XOR et est connue sous le nom de stupid XOR trick chez nos amis anglo-saxons. Il est en effet possible d'échanger le contenu de deux registres/variables A et B en effectuant les opérations suivante, dans l'ordre :

  •   ;
  •  ;
  •  .

Le code source correspondant, en C/C++, est un joli oneliner :

x ^= y ^= x ^= y ;

Toutefois il faut faire attention quand les variables utilisées sont indirectement accédées à travers des pointeurs ou des références : il ne faut pas que les deux pointeurs ou références pointent la même adresse mémoire, sinon le contenu est perdu et remis à zéro.

Cette technique était autrefois utilisée comme optimisation par quelques programmeurs, mais a perdu de sa superbe aujourd'hui. En effet, les processeurs modernes peuvent échanger facilement deux registres très rapidement, parfois en 0 cycle d'horloge. Quelques optimisations liées au renommage de registre permettent de réaliser cet échange en 0 cycles, bien plus rapidement qu'avec la méthode abordée. En conséquence, cette méthode est utilisable seulement sur les petits microcontrôleurs qui ne possèdent que très peu de registres, dans un objectif d'optimisation certain. Ce qui réduit largement son utilité...

Le fonctionnement de cette méthode se base sur le fait que  . Faites les calculs vous-même :  . Pour comprendre plus profondément pourquoi cette méthode marche, il suffit de regarder à chaque étape ce que l'on trouve dans A et dans B.

Etape Variable A Variable B
Avant l'opération A B
Première étape   B
Seconde étape    
Troisième étape    

Vu que XOR est associatif, commutatif, distributif, on peut alors supprimer les parenthèses. Les identités   et   nous permettent alors de simplifier fortement les expressions. Les simplifications précédentes donnent :

Etape Variable A Variable B
Avant l'opération A B
Première étape   B
Seconde étape    
Troisième étape    

Ce qui se simplifie en :

Etape Variable A Variable B
Avant l'opération A B
Première étape   B
Seconde étape   A
Troisième étape B A

Comme on le voit, nos données ont bien étés inversées.

Piège avec les pointeursModifier

Il faut faire attention au cas où des pointeurs sont utilisés pour adresser indirectement les variables à échanger, par exemple si une fonction est créée pour procéder à l'échange, comme celle-ci :

void exchangeIntegers(int* px, int* py)
{
    *px ^= *py ^= *px ^= *py ;
}

Dans le cas où l'on passe deux adresses différentes, aucun problème ne se produit :

int a = 5;
int b = 10;
exchangeIntegers(&a, &b);

Dans le cas où l'on passe deux adresses identiques, la variable pointée est remise à zéro (a XOR a) :

int a = 5;
exchangeIntegers(&a, &a);

Ce n'est pas l'effet voulu par la fonction. Il faut donc soit utiliser la technique de la variable intermédiaire qui n'a pas ce problème, soit vérifier les adresses passées en paramètres.

void exchangeIntegers(int* px, int* py)
{
    if (px != py) *px ^= *py ^= *px ^= *py ;
}

Listes chainées XORModifier

 
Liste doublement chainée normale.
 
Liste chainée XOR.

La propriété   est aussi utilisée pour créer des listes doublement chainées plus économes en mémoire que la normale, appelées listes chainées XOR. Une liste doublement chainée normale stocke deux pointeurs : un vers le nœud suivant, et un vers le nœud précédent. Les XOR linked list permettent de ne pas stocker les deux pointeurs : à la place ils stockent un seul pointeur. Celui-ci contient le XOR entre le pointeur vers le prochain nœud, et le pointeur vers le nœud précédent. Ainsi, on gagne un petit peu de mémoire : au lieu de stocker deux pointeurs, on n'en stocke plus qu'un seul. La consommation mémoire est aussi identique à celle d'une liste simplement chainée.

Dans ce qui suit, le pointeur sur le nœud précédent sera noté P (pour Précédent), le pointeur contenu dans le nœud actuellement visité est appelé Ptr et le pointeur vers le nœud suivant sera noté S (pour Suivant). Pour rappel, le pointeur stocké dans le nœud est égal au XOR entre P et S :  . Traverser cette liste ne se fait que dans un sens : soit on part du début pour arriver à la fin, soit on va dans l'autre sens. Dans ce qui suit, on étudiera un parcours commençant par le début de la liste vers la fin de celle-ci. Obtenir le pointeur vers le prochain élément demande de faire un XOR entre le pointeur vers l’élément précédent avec le pointeur stocké dans le nœud. En effet,  . Ce calcul donne l'adresse du prochain nœud dans la liste. Le même raisonnement peut s'adapter dans le cas où l'on parcours la liste dans l'autre sens., si ce n'est qu'il faut XORer le pointeur de l’élément précédemment visité (qui correspond alors à Next) avec le pointeur stocké dans le nœud.


Les masques

Dans certains cas prévis, il arrive que certaines informations soient codées sur un nombre limité de bits, qui peuvent être rassemblés dans un seul entier. De telles structures, formées en concaténant des bits dans un seul entier, sont appelées des champs de bits. Pour donner un exemple d'utilisation, supposons que j'ai regroupé plusieurs bits, dont chacun a une signification bien précise. Par exemple, je peux regrouper les droits d'accès dans un fichier dans un nombre : un des bits du nombre me dira alors si je peux écrire dans le fichier, un autre me dira si je peux le lire, un autre si… Bref, si jamais je veux modifier mes droits en écriture de mon fichier, je dois mettre un bit bien précis à 1 ou à 0 (suivant la situation). Cela peut se faire facilement en utilisant une instruction bit à bit entre ce nombre et une constante bien choisie.

Un autre cas typique est celui où un développeur compacte plusieurs données dans un seul entier. Par exemple, prenons le cas d'une date, exprimée sous la forme jour/mois/année. Un développeur normal stockera cette date dans trois entiers : un pour le jour, un pour le mois, et un pour la date. Mais un programmeur plus pointilleux sera capable d'utiliser un seul entier pour stocker le jour, le mois, et l'année. Pour cela, il raisonnera comme suit :

  • un mois comporte maximum 31 jours : on doit donc encoder tous les nombres compris entre 1 et 31, ce qui peut se faire en 5 bits ;
  • une année comporte 12 mois, ce qui tient dans 4 bits ;
  • et enfin, en supposant que l'on doive gérer les années depuis la naissance de Jésus jusqu'à l'année 2047, 11 bits peuvent suffire.

Dans ces conditions, notre développeur décidera d'utiliser un entier de 32 bits pour le stockage des dates :

  • les 5 bits de poids forts serviront à stocker le jour ;
  • les 4 bits suivant stockeront le mois ;
  • et les bits qui restent stockeront l'année.

Dans cette situation, le développeur qui souhaite modifier le jour ou le mois d'une date devra modifier une partie des bits, tout en laissant les autres intacts. Encore une fois, cela peut se faire facilement en utilisant une instruction bit à bit entre ce nombre et une constante bien choisie.

Modifier un bitModifier

Dans ce qui va suivre, nous allons voir comment modifier un bit dans un nombre, sans toucher aux autres. Pour donner un exemple d'utilisation, cela permet de modifier une date si les jours/mois et année sont regroupées dans un seul entier. Modifier des bits individuellement dans un champ de bit demande naturellement d'utiliser des opérations bit à bit. Suivant ce que l'on veut faire, l'instruction utilisée sera différente, mais le principe reste le même. Il suffit d'effectuer une instruction bit à bit entre notre nombre, et une constante bien précise.

Mettre à 1 un bitModifier

Tout d'abord, nous allons voir comment mettre à 1 un bit dans un nombre. Pour cela, nous allons utiliser une opération bit à bit entre le nombre en question, et un nombre appelé masque qui indique les bits à mettre à 1. Si le bit du masque est à 0, cela signifie que le bit du nombre, situé à la même place, ne doit pas être modifié. Mais si le bit du masque est à 1, le bit du nombre devra être mis à 1. Par exemple, pour modifier le 4éme bit d'un nombre en partant de la droite, le masque est une constante dont le 4éme bit en partant de la droite est 1, et le reste des bits est à 0, soit la constante : 000000001000.

Nous allons devoir trouver quelle opération bit à bit convient. Rien de compliqué au demeurant : il suffit d'écrire la table de vérité de cette opération et de reconnaitre la porte logique.

Nombre Masque Résultat
0 0 0
0 1 1
1 0 1
1 1 1

On remarque que l’opération bit à bit à effectuer est un OU.

Mettre à zéro un bitModifier

Mettre un bit à 0 dans un nombre fonctionne sur le même principe que mettre un bit à 1 : on effectue une opération bit à bit entre le nombre en question et un masque qui indique quels bits mettre à 0. Encore une fois, écrire la table de vérité de l'opération nous donne l'opération bit à bit à effectuer. Il s’avère que c'est un ET bit à bit.

Nombre Masque Résultat
0 0 0
0 1 0
1 0 0
1 1 1

On peut se demander à quoi peut bien servir de mettre à 0 certains bits. L'utilité première est d'accéder à un bit particulier dans un nombre, ou à des groupes de bits. Un cas classique est celui de la sélection du bit de signe, pour calibrer certaines opérations arithmétiques. Dans ce cas, on va mettre à zéro les bits inutiles avant d'effectuer un décalage pour caler ces bits à droite. Mais d'autres utilisations plus importantes existent. Par exemple, vous avez peut-être déjà entendu parler des masques de sous-réseau, dans des cours sur le protocole IP. Ceux-ci permettent de mettre à 0 certaines bits d'une adresse IP pour obtenir une adresse de sous-réseau. L'obtention de l'adresse de sous-réseau s'effectue avec un simple ET entre l'adresse IP et le masque de sous-réseau. Et ce n'est là qu'un exemple parmi tant d'autres !

Inverser un bitModifier

Le même raisonnement que pour les deux opérations précédentes vaut aussi pour ce qui est de l'inversion d'un bit. On obtient alors l'opération XOR à partir de la table de vérité.

Nombre Masque Résultat
0 0 0
0 1 1
1 0 1
1 1 0

Sélection d'un champ de bitsModifier

Reprenons l'exemple du développeur qui a stocké une date dans un seul entier. Supposons qu'il veuille récupérer le jour stocké dans cette date. Comment doit-il s'y prendre ? Rien de plus simple : il suffit de mettre tous les autres bits du nombre à zéro, et de décaler le tout pour placer le résultat sur le bit de poids faible. Il suffit juste de choisir le bon décalage, et la bonne constante. Toutefois, cette méthode a un défaut : les constantes utilisées sont souvent très longues, ce qui empêche d'utiliser le mode d'adressage immédiat pour celles-ci. Raccourcir ces constantes permet de gagner pas mal de place. On peut ruser un petit peu en effectuant le décalage avant la mise à zéro.

Le cas le plus simple est quand le développeur souhaite récupérer un seul bit. Par exemple, si je veux récupérer le 5 éme bit en partant de la droite dans le nombre 1111 0011. Il me suffit de mettre tous les bits à zéro, sauf le bit voulu. Pour cela, je dois effectuer un AND entre 1111 0011 et la constante 0001 0000. J'obtiens alors 0001 0000. Ensuite, un décalage logique de 4 rangs vers la droite me donnera le bit voulu : 0000 0001. Autre exemple : je décale mon nombre 1111 0011 de 4 rangs vers la droite. J'obtiens 0000 1111. Ensuite, je mets tous les bits à zéro, sauf le bit de poids faible. La constante à utiliser est alors 0000 0001. Dans cette situation, on remarque que la constante à utiliser est très courte : c'est 1. Cette constante est très courte, ce qui permet d'utiliser le mode d'adressage immédiat pour l'instruction AND. De quoi gagner quelques cycles.


Le poids de Hamming

Il arrive qu'on aie besoin de compter les bits d'un certain nombre. Par exemple, certaines application en cryptographie ont besoin de savoir combien de bit sont à 1 dans un nombre. Même chose pour la détection ou correction d'erreurs de transmission entre deux composants électroniques. Certaines de ces opérations, comme le poids de Hamming, se calculent fort bien avec des opérations bit à bit. Le poids de Hamming d'un nombre est le nombre de ses bits qui sont à 1. Ce calcul est souvent effectué quand on cherche à vérifier l'intégrité de données transmises ou stockées sur un support peu fiable et il est à la base d'un grand nombre de code de détection ou de correction d'erreurs usuels. Ce calcul est tellement fréquent que certains processeur disposent d'une instruction dédiée pour le calcul du poids de Hamming. Alors certes, ces architectures sont surtout des architectures anciennes, comme les SPARC, les CDC ou autres processeurs Cray. Mais à l'heure actuelle, les processeurs x86 possèdent une telle instruction, dans leurs extension SSE 4.1. Même chose pour les architectures ARM et Power PC. Ce calcul, s'il n'est pas effectué par le matériel, est pris en charge par un bout de code souvent rudimentaire. Si quelques compilateurs fournissent ainsi des opérateurs spécialisés pour faire ce calcul, le poids de Hamming n'est pas implémenté par la plupart des langages de programmation. Il faut dire que son utilisation essentiellement bas-niveau fait que la majorité des langages de haut-niveau actuel n'en a pas l'utilité.

Méthode itérativeModifier

Pour faire ce calcul, on pourrait penser naïvement à utiliser une simple boucle pour additionner les bits un par un. Le nombre d'itération est alors égal au nombre de bits du nombre, peu importe le nombre de 1. Le code, écrit en C, devrait être le suivant, pour un entier 32 bits :

unsigned HammingWeight (unsigned x)
{
    unsigned HammingWeight = 0 ;
    while (x > 0)
    {
        HammingWeight += x & 1 ;
        x = x >> 1 ;
    }
    return HammingWeight ;
}

Une autre version, un peu plus rapide, se base sur une boucle similaire. Elle consiste à mettre à 0 le 1 de poids faible (celui le plus à droite) à chaque tour de boucle. A chaque itération, le poids de Hamming diminue donc de 1. Il suffit de compter le nombre d'itération avant d'arriver à 0 pour déterminer le poids de Hamming. Le nombre d'itération est alors plus faible qu'avec le code précédent : le nombre d'itération passe du nombre de bits total au nombre de bits à 1. Le nombre d’itérations dans le pire des cas est alors le même qu'avec le code précédent, mais le nombre moyen ou dans le meilleur des cas diminue fortement. Le code obtenu est alors le suivant :

unsigned HammingWeight (unsigned x)
{
    unsigned HammingWeight = 0 ;
    while (x > 0)
    {
        x = x & (x - 1) ;
        HammingWeight += 1 ;
    }
    return HammingWeight ;
}

Méthode par pré-calculModifier

On peut aussi faire le calcul octet par octet. Pour cela, il suffit d'utiliser un tableau où la case d'indice i contient le poids de Hamming de i. Il suffit ensuite d'utiliser ce tableau dans une boucle pour faire l'addition octet par octet. On peut même dérouler totalement la boucle, si l'on connait exactement le nombre d'octets de l'entier à traiter. Cette technique a cependant le défaut d'effectuer des accès à la mémoire, qui sont des opérations assez lentes.

unsigned HammingWeight (unsigned x)
{ 
    static char table[256] = { 0, 1, 1, 2, 1, 2, 2, ... , 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 } ; // Tableau qui contient les poids de Hamming de chaque octet

    FirstByte = x & 0xFF ;
    SecondByte = (x >> 8) & 0xFF ;
    ThirdByte = (x >> 16) & 0xFF
    ForthByte = (x >> 24) & 0xFF

    return table[FirstByte] + table[SecondByte] + table[ThirdByte] + table[ForthByte] ;
}

Méthode récursive (diviser pour régner)Modifier

 
Calcul récursif du poids de Hamming.

Une autre solution effectue ce calcul avec une fonction récursive, avec une approche par dichotomie. On sait que je découpe un nombre en deux morceaux, je sais que son poids de Hamming est égal à la somme des poids de Hamming des deux morceaux. Et je peux appliquer le même raisonnement sur chaque morceau. Au final, je finirais par avoir des morceaux de plus en plus petits, jusqu'à obtenir des morceaux de 1 bit. Dans ce cas, je sais que la population count d'un morceau de 1 bit vaut 1 si le bit est à 1, et zéro s'il vaut zéro. En clair : la population count de 1 bit vaut…le bit en question. Dans les deux cas, le code devrait donc faire le calcul en N cycle, N étant le nombre de bits du nombre. Mais il y a moyen de faire beaucoup plus rapide, avec un calcul en log(N) opérations ! Pour cela, il faut utiliser une méthode qui s'inspire de la méthode récursive, mais utilise des opérations bit à bit pour faire certains calculs en parallèle. La méthode en question est, à mon avis, le plus beau algorithme utilisant des opérations bit à bit au monde.

L’algorithmeModifier

Pour illustrer l'algorithme, nous allons prendre l'exemple d'un nombre sur 8 bits que nous noterons N. L'algorithme commence par grouper les bits du nombre par groupes de deux et les additionne dans deux variables. La première variable va stocker tous les bits à une position paire, les autres bits étant mis à zéro. L'autre variable va faire la même chose avec les bits en position impaire, mais décalé d'un rang vers la droite, histoire que les bits des deux variables soient sur la même colonne. Les deux variables sont alors additionnées : variable 1 + variable2 >> 1. La première étape effectue donc le calcul suivant :

  • variable1 = N . 01010101
  • variable2 = (N . 10101010) >> 1
  • variable 1 + variable 2.

Regardons en détail ce qui se passe sur les bits de N.

Variable groupe de deux bits groupe de deux bits groupe de deux bits groupe de deux bits
Nombre N a7 a6 a5 a4 a3 a2 a1 a0
Variable1 0 a6 0 a4 0 a2 0 a0 0 a6 0 a4 0 a2 0 a0
Variable 2 >> 1 0 a7 0 a5 0 a3 0 a1
Variable 1 + Variable 2 >> 1 (a7 + a6) (a5 + a4) (a3 + a2) (a1 + a0)

La seconde étape est similaire, si ce n'est qu'elle isole les groupes de deux bits crées à l'étape précédente deux à deux, et les additionne.

Variable groupe de quatre bits groupe de quatre bits
Opérande (a7 + a6) (a5 + a4) (a3 + a2) (a1 + a0)
Variable1 (a7 + a6) 00 (a3 + a2) 00
Variable 2 >> 2 00 (a5 + a4) 00 (a1 + a0)
Variable 1 + Variable 2 >> 2 (a7 + a6 + a5 + a4) (a3 + a2 + a1 + a0)

Et on, poursuit ainsi de suite, jusqu'à obtenir la population count de notre nombre. Dans notre exemple, une troisième étape suffit pour obtenir le résultat.

Variable groupe de huit bits
Opérande (a7 + a6 + a5 + a4) (a3 + a2 + a1 + a0)
Variable1 0000 (a7 + a6 + a5 + a4)
Variable 2 >> 4 0000 (a3 + a2 + a1 + a0)
Variable 1 + Variable 2 >> 4 (a7 + a6 + a5 + a4 + a3 + a2 + a1 + a0)

Détermination des masquesModifier

L'algorithme demande de calculer des variables avec des groupes de bits en position paire et impaire, le reste des bits étant mis à 0. Il est évident que cela demande d'utiliser des masques pour mettre les bits inutiles à zéro. Dans le cas de la seconde variable, les bits doivent être décalés histoire d'être mis sur la même colonne que l'autre variable. On peut penser qu'il est naturel d'appliquer les masques avant des décalages, ce qui donne : variable1 = N . 01010101 et variable2 = N . 10101010. Dans ce cas, le calcul de variable2 et de variable1 ne s'effectuent pas avec les mêmes constantes. Ceci dit, il est aussi possible de faire le décalage de la seconde variable avant d'appliquer le masque. Dans ce cas, les masques des deux variables deviennent identiques. Pour le montre, partons des calculs où le masque est appliqué avant le décalage :

  • variable2 = (N . 10101010) >> 1
  • variable2 = (N . 11001100) >> 2
  • variable2 = (N . 11110000) >> 4

Vu que les décalages sont distributifs par rapport au AND, (a . b) >> n = (a >> n) . (b >> n), on obtient :

  • variable2 = (N >> 1) . (10101010 >>1) = (N >> 1) . 01010101
  • variable2 = (N >> 2) . (11001100 >>2) = (N >> 2) . 00110011
  • variable2 = (N >> 3) . (11110000 >>4) = (N >> 3) . 00001111

Les constantes utilisées sont exactement les mêmes que celles utilisée dans le calcul de la première variable.

Cela a un avantage sur certaines architectures RISC où les constantes immédiates ont une taille limitée. En conséquence, si une constante dépasse cette taille, elle ne peut pas utiliser le mode d'adressage immédiat. A la place, la constante est placée dans la mémoire, et est chargée dans un registre à chaque utilisation. Le fait de réutiliser la même constante pour le calcul de variable1 et de variable2 permet ainsi de charger cette constante une seule fois, et la réutiliser depuis le registre lors du calcul de variable2. En utilisant deux constantes différentes, on aurait deux accès mémoire, ce qui aurait été bien plus lent.

Le code en CModifier

Fort de ce qui a été dit précédemment, on trouve que le code de calcul du poids de Hamming est le suivant pour un entier de 32 bits :

unsigned HammingWeight (unsigned x)
{
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
    x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
    x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);

    return x ;
}

Il est possible de simplifier encore plus ce code, en supprimant quelques ET.

unsigned HammingWeight (unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}


Bit de parité

Les données d'un ordinateur ne sont pas des plus sûres qui soit. Évidemment, ces données peuvent être corrompues par un tiers malveillant, contenir des virus, etc. Mais certaines données sont corrompues pour des raisons qui ne relèvent pas de la volonté de nuire. Par exemple, les transmissions de données via un réseau local ou internet peuvent subir des perturbations électromagnétiques entre leur envoi et leur réception. Évidemment, les câbles réseaux sont conçus pour limiter les erreurs, mais ils ne sont pas une protection magique, capable de supprimer les erreurs de transmission. Dans le même genre, les mémoires ne sont pas des dispositifs parfaits, capables de fonctionner sans erreur. Pour donner un exemple, on peut citer l'incident de Schaerbeek. Le 18 mai 2003, dans la petite ville belge de Schaerbeek, une défaillance temporaire d'une mémoire faussa les résultats d'une élection. Cette ville utilisait une machine à voter électronique, qui contenait donc forcément une mémoire. Et on constata un écart de 4096 voix en faveur d'un candidat entre le dépouillement traditionnel et le dépouillement électronique. Mais ce n'était pas une fraude : le coupable était un rayon cosmique, qui avait modifié l'état d'un bit de la mémoire de la machine à voter. Cet incident n'était pas trop grave : après tout, il a pu corriger l'erreur. Mais imaginez la même défaillance dans un système de pilotage en haute altitude... Mais qu'on se rassure : il existe des techniques pour détecter et corriger les erreurs de transmission, ou les modifications non-prévues de données. Pour cela, divers codes de détection et de correction d'erreur ont vu le jour. Ce chapitre vous parlera du code le plus simple qui soit : le bit de parité/imparité, et de ses variantes.

Bit de parité horizontal mono-dimensionnelModifier

Le bit de parité est une technique utilisée dans un grand nombre de circuits électroniques, comme certaines mémoires RAM, ou certains bus (RS232, notamment). Il permet de détecter des corruptions qui touchent un nombre impair de bits. Si un nombre pair de bit est modifié, il sera impossible de détecter l'erreur avec un bit de parité. Il faut noter que ce bit de parité, utilisé seul, ne permet pas de localiser le bit corrompu. Ce bit de parité est ajouté aux bits à stocker. Avec ce bit de parité, le nombre stocké (bit de parité inclus) contient toujours un nombre pair de bits à 1. Ainsi, le bit de parité vaut 0 si le nombre contient déjà un nombre pair de 1, et 1 si le nombre de 1 est impair. Si un bit s'inverse, quelle qu'en soit la raison, la parité du nombre total de 1 est modifié : ce nombre deviendra impair si un bit est modifié. Et ce qui est valable avec un bit l'est aussi pour 3, 5, 7, et pour tout nombre impair de bits modifiés. Mais tout change si un nombre pair de bit est modifié : la parité ne changera pas. Ainsi, on peut vérifier si un bit (ou un nombre impair) a été modifié : il suffit de vérifier si le nombre de 1 est impair. Le bit d'imparité est similaire a bit de parité, si ce n'est que le nombre total de bits doit être impair, et non pair comme avec un bit de parité. Sa valeur est l'inverse du bit de parité du nombre : quand le premier vaut 1, le second vaut 0, et réciproquement. Mais celui-ci n'est pas meilleur que le bit de parité : on retrouve l'impossibilité de détecter une erreur qui corrompt un nombre pair de bits.

Reste que ce bit de parité doit être calculé, avec un morceau de code dédié qui prend un nombre et renvoie le bit de parité.

Poids de Hamming et bit de paritéModifier

Par définition, le bit de parité n'est autre que la parité du poids de Hamming. Par définition, le bit de parité a pour but de faire en sorte que la population count d'une donnée soit toujours pair : la donnée à laquelle on ajoute le bit de parité sera pair, et aura toujours son bit de poids faible à zéro. En conséquence, le bit de parité d'un nombre est égal au bit de poids faible de la population count d'un nombre. Et cette propriété permet de donner des algorithmes de calcul du bit de parité d'un nombre assez efficace. Son calcul demande donc simplement de calculer le poids de Hamming et de déterminer s'il est pair ou non. Vu que le calcul du poids de Hamming a une complexité logarithmique en le nombre de bits de la donnée d'entrée, le code qui va suivre sera aussi dans ce cas. Cet algorithme est parfois utilisé sur des systèmes qui ont peu de mémoire, quand on a déjà programmé une fonction pour le poids de Hamming : cela permet d'économiser un peu de mémoire programme. Mais cet algorithme n'est pas le plus efficace en terme de temps de calcul.

unsigned population_count (unsigned word) ;

unsigned parity_bit (unsigned word)
{
    return population_count (word) & 1 ;
}

Il est cependant possible d'obtenir un code plus simple, qui est plus rapide. Pour cela, il suffit de spécialiser le code pour le poids de Hamming, de manière à ce qu'il calcule uniquement le bit de parité. En conséquence, la suite de cette partie se contentera de reprendre les algorithmes pour calculer le code de Hamming et de les adapter pour le bit de parité.

Algorithme itératifModifier

Nous allons commencer par adapter le code itératif du calcul du poids de Hamming. Pour faire simple, la structure générale du code est conservée, mais il nous faudra remplacer les additions par une autre opération. Pour savoir quelle est cette opération, nous allons voir un cas simple : le calcul de la parité d'un nombre de 2 bits. Le circuit étant simple, il suffit d'utiliser les techniques vues précédemment, avec le tables de vérité. En écrivant la table de vérité du calcul, on remarque rapidement que la table de vérité est celle d'une porte XOR.

Bit 1 Bit 2 Bit de parité
0 0 0
0 1 1
1 0 1
1 1 0

Pour la suite, nous allons rajouter un troisième bit au nombre de 2 bits précédent. L'ajout de ce troisième bit modifie naturellement le bit de parité du nombre précédent. Dans ce qui va suivre, nous allons voir comment calculer le bit de parité final, à partir : du bit de parité du nombre de 2 bits, et du bit ajouté. On voit alors que la table de vérité est celle d'une porte XOR.

Bit de parité précédent Bit ajouté Bit de parité final
0 0 0
0 1 1
1 0 1
1 1 0

Chose assez intéressante, ce mécanisme fonctionne quelque soit le nombre de bits du nombre auquel on ajoute un bit. Ajouter un bit à un nombre modifie sa parité, celle-ci état alors égale à : bit ajouté XOR bit-parité du nombre. L’explication est relativement simple : ajouter n 0 ne modifie pas le nombre de 1, et donc le bit de parité, tandis qu'ajouter un 1 inverse le bit de parité. Ainsi, on déduit que le bit de parité peut se calculer simplement : il suffit de faire un XOR entre tous les bits du nombre. Effectué naïvement, il suffit d'enchainer des portes XOR les unes à la suite des autres. Mais en réfléchissant, on peut faire autrement. Prenons deux nombres et concaténons-les. On peut déduire facilement le bit de parité de la concaténation à partir des bits de parité de chaque nombre : il suffit de faire un XOR entre ces deux bits de parité.

Il suffit donc de faire un XOR de tous les bits pour calculer le bit de parité d'un nombre. L’algorithme de calcul du nombre de parité est alors assez évident.

unsigned parity_bit (unsigned word ,unsigned size)
{    
    unsigned parity_bit = 0 ;

    // on itère sur chaque bit du mot à traiter
    for(unsigned index = 0 ; index < size ; ++index)
    {
        //sélection du bit de poids faible
        unsigned temp = word & 1
        word = word >> 1 ;

        // XOR entre le bit sélectionné et le bit de parité des bits précédents.
        parity_bit = parity_bit ^ temp ;
    }

    return parity_bit ;
}

Cette solution a un temps de calcul qui est linéaire en le nombre de bits de la donnée dont on veut calculer le bit de parité. On peut faire mieux en utilisant d'autres propriétés du bit de parité. Naturellement, on peut travailler non sur des bits, mais aussi sur des octets. Prenons un mot de 16 bits, par exemple : il me suffit de faire un XOR entre les bits de parité de ces deux octets. Or, la parité d'un octet peut se pré-calculer et être stockée dans un tableau une fois pour toute, afin d'éviter de nombreux calculs. Ainsi, l'algorithme vu précédemment peut être amélioré pour traiter non pas un bit à la fois, mais plusieurs bits à la fois.

unsigned ParityBit (unsigned x)
{ 
    static char table[256] = { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ... , 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,} ; // Tableau qui contient les bits de parité de chaque octet

    FirstByte = x & 0xFF ;
    SecondByte = (x >> 8) & 0xFF ;
    ThirdByte = (x >> 16) & 0xFF
    ForthByte = (x >> 24) & 0xFF

    return table[FirstByte] ^ table[SecondByte] ^ table[ThirdByte] ^ table[ForthByte] ;
}

Algorithme récursifModifier

On peut améliorer l'algorithme du dessus en utilisant la propriété suivante : si on concatène deux mots binaire, alors le bit de parité du mot obtenu est égal au XOR des bits de parité des deux mots concaténés. Cette propriété peut s'expliquer assez simplement. Pour cela, il suffit de regarder le nombre de bits à 1 dans chaque mot à concaténer.

Nombre de bits à 1 dans le mot binaire de gauche Nombre de bits à 1 dans le mot binaire de droite Nombre de bits à 1 dans le résultat
Pair Pair Pair
Pair Impair Impair
Impair Pair Impair
Impair Impair Pair

Si on remplace Pair et Impair par la valeur du bit de parité correspondant, on obtient exactement le fonctionnement d'une porte XOR.

On peut aussi inventer un autre algorithme du calcul du bit de parité, assez inefficace, basé sur une fonction récursive. Le principe est de couper le mot dont on veut la parité en deux morceaux. On calcule alors la parité de ces deux morceau, et on fait un XOR entre ces deux parités. Le code obtenu est alors celui-ci :

unsigned parity (unsigned word, size)
{
    if (word <= 1)
    {
        return word ;
    }
    else
    {
        unsigned gauche = word >> (size/2) ;
        unsigned droite = word % (size/2) ;
        return parity(gauche, size/2) ^ parity (droite, size/2)) ;
    }
}

Algorithme récursif optimiséModifier

Il est aussi possible de réutiliser l'algorithme de calcul du poids de Hamming, celui récursif basé sur des masques et des additions, pour calculer le bit de parité. La différence est que les bits ne doivent pas être additionnés, mais XORés. Fort de ce qui a été dit précédemment, on trouve que le code de calcul du bit de parité est le suivant pour un entier de 32 bits :

unsigned ParityBit (unsigned x)
{
    x = (x & 0x55555555) ^ ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) ^ ((x >> 2) & 0x33333333);
    x = (x & 0x0F0F0F0F) ^ ((x >> 4) & 0x0F0F0F0F);
    x = (x & 0x00FF00FF) ^ ((x >> 8) & 0x00FF00FF);
    x = (x & 0x0000FFFF) ^ ((x >> 16) & 0x0000FFFF);

    return x ;
}

Il faut noter que cet algorithme est cependant simplifiable pour le calcul du bit de parité. L'usage des masques permet de XOR les bits de position paire et impaire, puis des groupes consécutifs de 2 bits, puis de 4 bits, etc. Mais pour le bit de parité, on peut effectuer le calcul dans l'autre sens. Pour des entiers de 64 bits, on peut commencer par XOR les 32 bits de poids fort avec les 32 bits de poids faible. Plus, sur les 32 bits du résultat, on peut XOR les 16 bits de poids fort et les 16 de poids faible. Et ainsi de suite... L'algorithme est donc plus simple, vu que l'on a pas besoin d'utiliser des masques, mais que l'on peut se contenter de décalages. Le code est donc le suivant :

unsigned ParityBit (unsigned x)
{
    x ^= (x >> 32) ;
    x ^= (x >> 16) ;
    x ^= (x >> 8) ;   
    x ^= (x >> 4) ;
    x ^= (x >> 2) ;
    x ^= (x >> 1) ;

    return x & 1 ;
}

Mot de paritéModifier

Si on peut calculer le bit de parité d'un mot, il est aussi possible de calculer des octets de parité pour un ensemble de Byte/mots machine. Le résultat de cette opération est ce qu'on appelle un mot de parité, une extension du bit de parité pour plusieurs nombres. On peut le voir comme l'équivalent d'un bit de parité pour un paquet de nombre. Cela sert sur les bus de communication entre composants, sur lesquels on peut envoyer plusieurs nombres à la suite, ou dans les mémoires qui stockent plusieurs nombres les uns à côté des autres. Il faut noter que le bit de parité peut être vu comme une spécialisation de la technique du mot de parité, où les blocs font tous 1 bit. Le calcul du mot de parité se calcule en disposant chaque nombre/bloc l'un au-dessus des autres, le tout donnant un tableau dont les lignes sont des nombres Le mot de parité se calcul en calculant le bit de parité de chaque colonne du tableau, et en le plaçant en bas de la colonne. Le résultat obtenu sur la dernière ligne est un octet de parité. Pour comprendre le principe, supposons que nous disposions de 8 entiers de 8 bits. Voici comment effectuer le calcul du mot de parité :

  • 11000010 : nombre ;
  • 10001000 : nombre ;
  • 01001010 : nombre ;
  • 10010000 : nombre ;
  • 10001001 : nombre ;
  • 10010001 : nombre ;
  • 01000001 : nombre ;
  • 01100101 : nombre ;
  • ------------------------------------
  • 10101100 : mot de parité.

L'avantage de cette technique est qu'elle permet de reconstituer un octet manquant. C'est cette technique qui est utilisée sur les disques durs montés en RAID 3, 5 6, et autres : si un disque dur ne fonctionne plus, on peut quand même reconstituer les données du disque dur manquant. Retrouver la donnée manquante est assez simple : il faut calculer la parité des nombres restants, et de faire un XOR avec le mot de parité. Pour comprendre pourquoi cela fonctionne, il faut se souvenir que faire un XOR entre un nombre et lui-même donne 0. De plus, le mot de parité est égal au XOR de tous les nombres. Si on XOR un nombre avec le mot de parité, cela va annuler la présence de ce nombre (son XOR) dans le mot de parité : le résultat correspondra au mot de parité des nombres, nombre xoré exclu. Ce faisant, en faisant un XOR avec tous les nombres connus, ceux-ci disparaitrons du mot de parité, ne laissant que le nombre manquant.

Bit de parité multidimensionnelModifier

On a vu que le bit de parité ne permet pas de savoir quel bit d'un nombre a été modifié. Mais il existe une solution pour que cela devienne possible, dans le cas où plusieurs nombres sont envoyés. Si on suppose qu'un seul bit a été modifié lors de la transmission du paquet de nombre, on peut détecter quel bit exact a été modifié. Pour cela, il suffit de coupler un mot de parité avec plusieurs bits de parité, un par nombre. Détecter l bit modifié est simple. Pour comprendre comment, il faut se souvenir que les nombres sont organisés en tableau, avec un nombre par ligne. Le bit modifié est situé à l'intersection d'une ligne et d'une colonne. Sa modification entraînera la modification du bit de parité de la ligne et de la colonne qui correspondent, respectivement un bit de parité sur la verticale, et un bit de parité dans le mot de parité. Les deux bits fautifs indiquent alors respectivement la ligne et la colonne fautive, le bit erroné est situé à l'intersection. Cette technique peut s'adapter non pas avec une disposition en lignes et colonnes, mais aussi avec des dimensions en plus où les nombres sont disposés en cube, en hyper-cube, etc.


Manipulations sur les puissances de deux

Dans cette section, nous allons aborder les opérations qui font intervenir des nombres de la forme   et  . Nous allons commencer par une opération assez simple, qui permet de calculer la puissance de   qui est immédiatement supérieure à un nombre   donné. Cette opération est à la base de calculs arithmétiques ou logiques plus complexes, comme le calcul du logarithme d'un nombre entier.

Modulo par une puissance de deuxModifier

Après avoir vu la multiplication et la division, nous pouvons maintenant passer au modulo par une constante. Nous allons nous concentrer sur le cas du modulo par une puissance de 2, les autres cas n'ayant pas de solution algorithmique simple. On peut d'or et déjà dire que ce modulo par une puissance de deux a un lien très fort avec la division par une puissance de deux. Cette dernière se traduisant par un décalage de n rangs, on peut se douter que le modulo aura un lien avec ces décalages. Nous allons d'abord voir le cas des nombres positifs, puis les nombres signés.

Nombres positifsModifier

Le modulo par une puissance de deux se contente de garder les bits effacés par le décalage correspondant à la division. Pour comprendre comment faire ce calcul, nous allons reprendre, encore une fois, l'écriture en binaire d'un nombre :

 

Par définition, le modulo d'un nombre va prendre le reste de la division par un entier. Si calcule le reste modulo  , cela veut dire qu'on doit supprimer tous les multiples de   dans l'écriture binaire de notre nombre., en les mettant à zéro. En clair : pour obtenir le modulo, on doit mettre à zéro les n bits les plus à droite dans l'écriture binaire de notre nombre. Cette mise à zéro se fait en utilisant une opération ET, avec la constante égale à  .

 

 
Modulo et quotient d'une division par une puissance de deux en binaire.

Mais attention : pour ce qui est des nombres négatifs, le coup du AND ne marche pas. Mais on peut toujours prendre la valeur absolue de notre nombre, calculer le modulo avec un AND, et prendre l'opposé, cela marche tout aussi bien.

Nombres signésModifier

Pour les nombres signés, la méthode précédente ne peut pas être utilisée directement. On est obligé de passer par l'intermédiaire de la valeur absolue et d'en calculer le modulo. Puis, il faut corriger le résultat en fonction de son signe. Dans ce qui va suivre, nous allons noter le bit de signe  . Celui-ci sera mis dans un nombre, précisément dans son bit de poids faible.

Première méthodeModifier

Une première formule pour le calcul du modulo est la suivante :

 

Le calcul du modulo d'un nombre signé peut donc se réaliser avec l'équation suivante :

 

La seule exception est quand on souhaite calculer le modulo 2. Dans ce cas, le bit de poids faible donne directement le modulo, peu importe le signe du nombre testé. Le calcul est alors le suivant :

 

Seconde méthodeModifier

Une autre solution est d'utiliser la formule suivante :

 

Le calcul du modulo d'un nombre signé peut donc se réaliser avec l'équation suivante :

 

Arrondir vers un multiple de  Modifier

Dans cette section, nous allons voir comment arrondir un nombre au multiple de   immédiatement supérieur ou inférieur.

Arrondi au multiple inférieurModifier

Pour le multiple immédiatement supérieur, prenons un exemple. Je souhaite arrondir 46 au multiple de 8 immédiatement supérieur : 46 sera arrondi à 48 (8 * 6). Si j'avais voulu arrondir au multiple immédiatement inférieur, j'aurais obtenu 40 (8 * 5). Le plus simple, c'est arrondir au multiple de   immédiatement inférieur. Pour cela, il suffit de mettre les n bits les plus à droite à 0, en utilisant un masque. Exemple : je veux arrondir x au multiple de 8 inférieur. Dans ce cas, je dois faire :  . Si on regarde bien, cela revient à appliquer un AND entre le nombre à arrondir et une constante qui vaut :  . Effectuer l'arrondi demande donc de faire ce calcul :

 

Sur les ordinateurs qui utilisent le complètement à deux pour coder les nombres signés, cette expression se simplifie en :

 

Arrondi au multiple supérieurModifier

Pour arrondir au multiple de x immédiatement supérieur, on peut procéder de différentes façons. On peut arrondir au multiple inférieur, et ajouter  . Une autre solution consiste à mettre les n bits de poids faible à 1 dans le nombre à arrondir, avant d'ajouter 1. Ainsi, pour arrondir un nombre X, je dois effectuer le calcul suivant :

 

Ce qui est équivalent à :

 

 

Détection d'un débordement de puissance de deuxModifier

Comme vous le savez peut-être, certaines architectures demandent aux accès mémoire de respecter des contraintes d'alignement. Pour rappel, la mémoire est alors découpée en blocs dont la taille est égale à la largeur du bus de données. Quand on charge une donnée, il est préférable que celle-ci soit intégralement contenue dans un bloc : l'accès mémoire est alors dit aligné. Si une donnée est à cheval sur deux blocs, elle devra alors être chargée en deux fois, ou causera une exception matérielle. Certains processeurs ne gèrent que des accès mémoires alignés. Pour diverses raisons, il est possible pour un programmeur de détecter si un accès mémoire sera ou non aligné. Un problème similaire apparait lorsque l'on doit charger une donnée depuis la mémoire RAM, sur les systèmes à mémoire virtuelle. Cette fois-ci, la mémoire virtuelle divise la RAM en pages, les données pouvant être à cheval sur deux pages. Détecter de tels chevauchements est alors une nécessité pour le système d’exploitation. Il se trouve qu'aussi bien la taille des pages que la largeur des blocs de RAM alignés sont des puissances de deux. Détecter les débordements de page ou de bloc alignés demande alors détecter quand une donnée est à cheval entre deux blocs de taille égale à  . La donnée à charger commence à une adresse que nous noterons   et a une longueur  . Un débordement de page/bloc a lieu quand il existe un multiple de   entre   et   : cela traduit le fait que la donnée commence dans un premier bloc, atteint la limite du bloc (donc, une adresse multiple de  ) et se poursuit au-delà. Reste à voir comment les opérations bit à bit nous aident pour détecter une telle situation.

Méthode sans débordement d'entierModifier

Pour cela, il existe deux solutions différentes, la première étant plus simple à comprendre que l'autre. La première demande se base sur le fait que l'adresse   peut-être ou non un nombre divisible par la puissance de deux concernée. En clair, on sait que c'est un nombre de la forme  . Un débordement a lieu si, en ajoutant  , on passe au multiple suivant. En clair, un débordement a lieu si  . En faisant quelques manipulations algébriques (soustraire A des deux cotés), cette condition se traduit alors en :  . La logique est simple : si la longueur dépasse ce qu'il manque à l'adresse pour atteindre le prochain multiple de  , alors l'adresse dépassera cette puissance : c'est un débordement. On peut alors faire le calcul assez simplement, vu que le reste  . Le calcul total est le suivant :

 

On peut alors utiliser la méthode pour calculer le modulo par la puissance de deux :

 

Méthode avec débordement d'entierModifier

Une seconde méthode effectue un calcul similaire, si ce n'est qu'il arrive à remplacer la comparaison par un débordement d'entier. Le principe est très simple et se contente de remplacer l'adresse par le multiple de   le plus grand possible qui soit adressable. Prenons par exemple une mémoire de 2^32 adresses, adressée par des adresses de 32 bits, découpée en page de 4096 octets. On suppose aussi que la machine travaille sur les mots/registres de 32 bits, comme les adresses. L'adresse la plus élevée,  , n'est pas un multiple de 4096. L'adresse la plus grande multiple de 4096 est de 4294963200. Si à cette adresse on ajoute  , un débordement se produit si  . En clair, le débordement d'entier traduit un débordement de page. On détecte donc un débordement de page si :

 

Il se trouve que le calcul de   peut se réaliser sans faire l'addition. Tout ce qu'il faut faire est de remplacer les bits de poids forts de l'adresse par des 1, sans toucher aux bits sélectionnés par le modulo. L'application d'un masque est alors obligatoire, ce qui donne le code suivant :

 

Ou encore :

 

On peut bien sûr généraliser les résultats précédents à toute autre valeur. Pour des adresses de   bits et des pages/blocs de   octets, on a :

 

Puissance de deux immédiatement supérieureModifier

Supposons que je veuille arrondir un nombre à puissance de deux immédiatement supérieure. Par exemple, je veux arrondir 5 à 8. Ou 25 à 32. Ou encore 250 à 256. Effectuer ce calcul peut sembler compliqué, si on ne prend pas le problème par le bon bout. Mais il y a une méthode asse simple pour faire ce calcul : il suffit de calculer non pas la puissance de deux, mais le nombre qui précède et de l'incrémenter. Le calcul de cette valeur, à savoir le nombre de la forme   immédiatement supérieur, est en effet très simple à faire.

Pour cela, partons de l’exemple d'un nombre, que l'on va nommer N. Dans ce qui va suivre, ce N vaudra 0010 1101, pour l'exemple. Comme vous le voyez, ce nombre est de la forme 001X XXXX, avec X qui vaut zéro ou 1 selon le bit. Le nombre de la forme   immédiatement supérieur lui, vaut 0011 1111. On voit que pour obtenir ce nombre, il faut recopier le 1 le plus à gauche, dans tous les bits à sa droite. Pour cela, quelques décalages font l'affaire. Pour vous donner une idée, regardons ce que vaut N OU (N >> 1) : 001X XXXX OR 0001 XXXX = 0011 XXXX. On voit que le 1 le plus à gauche a été recopié dans le bit à sa droite. Ensuite, regardons ce que vaut N OU (N >> 1) OU (N >> 2) : 001X XXXX OR 0001 XXXX OR 0000 1XXX = 0011 1XXX. Vous commencez à comprendre ? Les bits qui sont à droite du 1 le plus à gauche se remplissent progressivement avec des 1, au fur et à mesure des décalages. Si on pousse le bouchon encore plus loin, on se retrouvera avec un nombre dont tous les bits à droite du 1 le plus à gauche seront tous des 1. Le résultat est un nombre de la forme  . Pour être plus précis, il s'agit du nombre de la forme  . Il n'y a plus qu'à l'incrémenter pour obtenir la puissance de deux immédiatement supérieure.

On doit donc effectuer suffisamment de décalages pour mettre à 1 tous les bits à droite. On peut croire que pour un nombre de n bits, il faut effectuer n décalages. Mai en réalité, on peut réduire ce nombre assez facilement. Prenons l'exemple du nombre de la forme 1XXX XXXX. On peut effectuer un premier décalage d'un rang vers la droite, ce qui donne : 11XX XXXX. Ensuite, on peut prendre les deux bits à 1 et les recopier dans les deux bits qui suivent. C'est plus rapide que de remplir les bits par un par un. Il faut alors faire un décalage de deux rangs, ce qui donne : 1111 XXXX. Enfin, on peut recopier les 4 bits à 1 dans les 4 bits suivants, ce qui demande un décalage par 4. Si le nombre était plus long, on pourrait réutiliser la même logique : à chaque étape, le nombre de rangs pour le décalage double. Et cela marche pour tous les nombres, peu importe leur écriture binaire. Le code correspondant, bien qu'un petit peu amélioré et spécifique aux nombres de 32 bits, est le suivant :

unsigned NextPowerOf2 (unsigned n)
{
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n++;
}

La décrémentation au début du code sert à gérer le cas où le nombre traité est lui-même une puissance de deux.


Manipulations sur les bits de poids faible/fort

Vu que nous travaillons sur des nombres codés en binaire, on ne peut pas s'étonner de la présence d'un chapitre spécialement dédié aux puissances de deux. Il parait naturellement que certains calculs les faisant intervenir soient nombreux dans le domaine de la manipulation de bits.

Manipuler les 1 et 0 de poids faible/fortModifier

Pour débuter cette section, il nous faut faire un rappel de deux faits importants. Premièrement, en binaire,   est un nombre dont le énième bit est à 1 et tous les autres à 0. Par contre,   est un nombre dont ce bit est à 0, de même que ceux à sa gauche : seuls les bits à sa droite sont à 1.

Nombre x Écriture binaire de   sur 8 bits Écriture binaire de   sur 8 bits
1 0000 0001 0000 0000
2 0000 0010 0000 0001
3 0000 0100 0000 0011
4 0000 1000 0000 0111
5 0001 0000 0000 1111
6 0010 0000 0001 1111
7 0100 0000 0011 1111
8 1000 0000 0111 1111

Mettre à 0 le 1 de poids faibleModifier

On peut aussi se demander ce que donne le calcul   quand il est appliqué à un nombre quelconque, pas forcément à une puissance de deux. Si vous faites quelques tests, vous allez remarquer que ce calcul met toujours un bit à 0 dans le nombre initial : pas un de plus, pas un de moins. De plus, ce bit est un bit qui est initialement à 1 : il s'agit même du 1 qui est le plus à droite dans l'écriture binaire, à savoir le 1 de poids faible. C'est pour cela que ce calcul permet de vérifier si un nombre est une puissance de deux : par définition, une puissance de deux n'a qu'un seul bit à 1. Si ce bit est mis à 0, alors on obtient bien un zéro.

   
1111 1111 1111 1110
1111 1110 1111 1100
1111 1000 1111 0000
0010 1000 0010 0000
0010 0000 0000 0000

Pour comprendre pourquoi cela fonctionne, reprenons l'écriture binaire du nombre x. Si celui-ci est non-nul, il y aura un 1 qui sera le plus à droite de tous les autres. Celui-ci codera une puissance de deux, peu importe laquelle. Il aura un ou plusieurs zéros à sa droite, potentiellement zéro. Dit autrement, on peut décomposer ce nombre en deux parties : une partie gauche contenant les bits à gauche du 1 de poids faible et une partie droite de la forme 10000, avec un nombre de zéro variable, potentiellement nul. En clair, le nombre est de la forme XXXXX...XXXX 100000...000.

On remarque que la partie droite est une puissance de deux : sa représentation binaire est celle d'une puissance de deux. Si on soustrait 1, la partie droite sera donc un nombre de la forme  . On obtiendra donc une partie droite de la forme 011111...11111, et donc un nombre de la forme XXXXX...XXXX 011111...11111. On remarque que   et   ont la même partie gauche. Si on fait un ET entre ces deux nombres, la partie la partie gauche sera intouchée. Par contre,   et   n'ont aucun bit en commun, ce qui fait que le ET va donner 0. Si on compare le résultat avec  , on remarque que le résultat est le même que le nombre   de départ, sauf que le 1 de poids faible est mis à 0.

Cette opération permet de vérifier qu'un nombre est une puissance de 2. On remarque que les nombres   et   n’ont pas de bit à 1 en commun. Dit autrement, si on effectue un ET logique entre ces deux nombres, on obtient 0 : les 0 dans un nombre vont annuler les 1 qui sont dans l'autre. Ce qui signifie que si x est une puissance de deux, alors  . Et la réciproque est vraie : si  , alors x est une puissance de deux. Attention toutefois : avec cette technique, zéro est considéré comme une puissance de deux. Faites donc attention.

Mettre à 0 les 1 de poids faibleModifier

Le code précédent peut s'adapter afin de mettre à 0 non pas le 1 de poids faible, mais tous les 1 de poids faibles consécutifs s'ils sont plusieurs. Par exemple, pour le nombre 0101011111, on peut vouloir mettre à 0 les 5 1 de poids faible. Pour cela, il faut utiliser la formule suivante :

 

Mettre à 1 le 0 de poids faibleModifier

On peut aussi vouloir inverser non pas le 1 de poids faible, mais le 0 de poids faible, le mettre à 1. Pour cela, il faut utiliser la formule suivante :

 

Mettre à 1 le ou les 0 de poids faibleModifier

On peut maintenant se demander ce qui se passe quand on effectue non pas un ET, mais un OU entre   et  . Dans ce cas, on remarque que les 0 de poids faibles sont mis à 1. Précisément, si on prend un nombre de la forme XXXXX...XXXX 100000...000, celui-ci devient de la forme XXXXX...XXXX 11111...1111. En clair, tous les bits qui se situe à droite du 1 de poids faible sont mis à 1. Par exemple, le nombre 0110 1010 0011 1000 deviendra 0110 1010 0011 1111. Pour résumer, voici la formule adéquate :

 

Il faut signaler que cette formule ne modifie pas les bits qui ne sont les 0 de poids faible. Mais il est possible d'isoler ceux-ci et de mettre tout autre bit à 0. Par exemple, le nombre 0110 1100 1111 0000 deviendra : 0000 0000 0000 1111. Ou encore, le nombre 0101 1000 deviendra 0000 0111. Pour cela, diverses formules peuvent être utilisées. Les voici :

  •   ;
  •   ;
  •  .

Isoler le 1 de poids faibleModifier

Isoler le 1 de poids faible signifie mettre à 0 tous les autres bits du nombre. Seul le 1 de poids faible restera à 1, les autres bits étant effacés. Cette opération est très simple : il s'agit d'un simple ET entre   et   :

 .

FFS, FFZ, CTO et CLOModifier

Dans cette section, nous allons aborder plusieurs opérations fortement liées entre elles. Dans toutes ces opérations, les bits sont numérotés, leur numéro étant appelé leur position ou leur indice. La première opération, Find First Set, donne la position du 1 de poids faible, celui le plus à droite du nombre. Cette opération est liée à l'opération Count Trailing Zeros, qui donne le nombre de zéros situés à droite de ce bit à 1. L'opération Find First Set est opposée au calcul du logarithme binaire, qui donne la position du 1 le plus à droite, celui de poids fort. Le nombre de zéros situés à gauche de ce bit à 1 est appelé le Count Leading Zeros.

Ces quatre opérations ont leur équivalents inverses. Par exemple, l'opération Find First Zero donne la position du 0 de poids faible (le plus à droite) et l'opération Find Highest Zero donne la position du 0 de poids fort (le plus à gauche). L'opération Count Trailing Ones donnent le nombre de 1 situés à gauche du 0 de poids fort, tandis que l'opération Count Leading Ones donne le nombre de 1 situés à droite du 0 de poids faible. Ceux-ci se calculent à partir des quatre opérations précédentes, en inversant l'opérande, aussi nous n'en parlerons pas plus que cela.

 
Opérations Find First Set ; Find First Zero ; Find Highest Set (le logarithme binaire) ; Find Highest Zero ; Count Leading Zeros ; Count Trailing Zeros ; Count Leading Ones et Count Trailing Ones.

Ces opérations varient selon la méthode utilisée pour numéroter les bits. On peut commencer à compter les bits à partir de 0, le 0 étant le numéro du bit de poids faible. Mais on peut aussi compter à partir de 1, le bit de poids faible étant celui de numéro 1. Ces deux conventions ne sont pas équivalentes. Par exemple, si on choisit la première convention, les opérations Count Trailing Zeros et Find First Set sont strictement équivalentes. Même chose pour les opérations Count Trailing Ones et Find First Zero. Avec l'autre convention, les deux différent de 1 systématiquement. Dans ce qui va suivre, nous allons utiliser la première convention : le bit de poids faible a comme numéro 0. Ce qui fait que nous n'aurons qu'à aborder deux calculs : Find First Set, abréviée FFS, et le calcul du logarithme binaire. Avec cette convention, pour un nombre codé sur   bits, on a :

 

 

Le logarithme binaireModifier

Maintenant, nous allons voir comment déterminer la position du 1 le plus significatif dans l'écriture binaire du nombre. En clair, la position du 1 le plus à gauche. Mine de rien, ce calcul a une interprétation arithmétique : il s'agit du logarithme en base 2 d'un entier non-signé. Dans tout ce qui va suivre, nous allons numéroter les bits à partir de zéro : le bit le plus à droite d'un nombre (son bit de poids faible) sera le 0-ème bit, le suivant le 1er bit, et ainsi de suite.

Nous allons commencer par voir un cas simple : le cas où notre nombre vaut  . Dans ce cas, un seul bit est à 1 dans notre nombre : le n-ième bit. On peut en faire une démonstration par récurrence. Déjà, on remarque que la propriété est vraie pour   : le 0-ème bit du nombre est mis à 1. Supposons maintenant que cette propriété soit vraie pour   et regardons ce qui se passe pour  . Dans ce cas,  . Donc, le bit suivant sera à un si on augmente l'exposant d'une unité : la propriété est respectée !

Maintenant, qu'en est-il pour n'importe quel nombre  , et pas seulement les puissances de deux ? Prenons n'importe quel nombre, écrit en binaire. Si celui-ci n'est pas une puissance de deux, alors il est compris entre deux puissances de deux :  . En prenant le logarithme de l'inégalité précédente, on a :  . Par définition du logarithme en base 2, on a :  . Dit autrement, le logarithme en base 2 d'un nombre est égal à  , qui est la position de son 1 de poids fort, celui le plus à droite. Plus précisément, il s'agit de la partie entière du logarithme.

Méthode itérativeModifier

Mais comment calculer cette position ? Pour cela, on peut utiliser le code suivant Celui-ci est composé d'une boucle qui décale le nombre d'un rang à chaque itération, et compte le nombre de décalage avant d'obtenir 0.

int log_2 (int a)
{
    unsigned int r = 0;
    while (a >>= 1)
    {
        r++;
    }
    return r ;
}

Méthode par dichotomieModifier

Une autre méthode se base sur un algorithme par dichotomie, à savoir qu'il vérifie si le logarithme est compris dans un intervalle qui se réduit progressivement. Pour illustrer le principe de cet algorithme, nous allons prendre un entier de 64 bits. L'algorithme utilise une variable accumulateur pour mémoriser le logarithme, qui est calculé au fil de l'eau. L'algorithme vérifie d'abord si le bit de poids fort est compris dans les 32 bits de poids fort. Si c'est le cas, on sait que le logarithme est d'au moins 32 (> ou = à 32). La variable accumulateur est alors incrémentée de 32 et le nombre est décalé de 32 rangs vers la droite. On poursuit alors l'algorithme, mais en vérifiant si le bit de poids fort est dans les 16 bits de poids fort. Et ainsi de suite avec les 8, 4, et 2 bits de poids fort. Pour vérifier si le bit de poids fort est dans les 32, 16, 8, 4, ou 2 bits de poids fort, une simple comparaison suffit. Il suffit de comparer si le nombre est supérieur respectivement à (1111 1111 1111 1111 1111 1111 1111 1111), (1111 1111 1111 1111), (1111 1111), (1111), (11). Le code est donc le suivant :

int log_2 (int x)
{
    unsigned log = 0 ;

    if (x > 0xFFFFFFFF)
    {
        log += 32 ;
        x = x >> 32 ;
    }
    if (x > 0xFFFF)
    {
        log += 16 ;
        x = x >> 16 ;
    }
    if (x > 0xFF)
    {
        log += 8 ;
        x = x >> 8 ;
    }
    if (x > 0xF)
    {
        log += 4 ;
        x = x >> 4 ;
    }
    if (x > 3)
    {
        log += 1 ;
        x = x >> 2 ;
    }
    log = x >> 1 ;

    return log ;
}


On peut généraliser cet exemple pour n'importe quel nombre de   bits. L'algorithme commence par vérifier si le bit de poids fort est dans les   bits de poids fort ou dans les   bits de poids faible. Si le bit de poids fort est dans les   bits de poids forts, alors on sait que le logarithme est d'au moins   et peut lui être supérieur ou égal. On mémorise donc   bits comme valeur temporaire du logarithme. On décale alors le nombre de   bits vers la droite pour le ramener dans l'autre intervalle. Et on continue, mais en vérifiant les   bits de poids fort, et ainsi de suite.

Méthode basée sur le poids de HammingModifier

Une autre solution se base sur le fait que le bit de poids faible est numéroté 0 ! Pour cela, on peut utiliser le code précédent, qui permet de trouver le nombre de la forme   immédiatement supérieur. Ce nombre, par définition, a tous les bits de rang   à 1 : il suffit de compter ses 1 pour obtenir le rang   ! On verra dans quelques chapitres qu'il existe des méthodes pour compter le nombre de 1 d'un nombre, celui-ci étant appelé le poids de Hamming.

int log_2 (int a)
{
    int n = NextPowerOf2 (a) ;
    return HammingWeight(n) ;
}

Count Leading ZerosModifier

Dans un ordinateur, les nombres sont de taille fixe. Un nombre est ainsi stocké sur 8, 16, 32, 64 bits. Si jamais un nombre peut être représenté en utilisant moins de bits que prévu, les bits qui restent sont mis à zéro. Par exemple, sur une architecture 8 bits, le nombre 5 ne sera pas stocké comme ceci : 101, mais comme ceci : 00000101. On voit donc que ce nombre contient un certain nombre de zéros non-significatifs. Ces zéros sont placés à gauche du nombre. Plus précisément, notre nombre aura certains de ses bits à 1. Parmi ceux-ci, il y aura un de ces bits qui sera plus à gauche que tous les autres 1. A gauche de ce 1, on peut éventuellement trouver un certain nombre de zéros non-significatifs. L'instruction Count leading zeros a pour objectif de compter ces zéros non-significatifs. Pour un nombre de N bits, le nombre de ces zéros à gauche peut varier entre 0 et N. Si on a 0 zéros non-significatif, dans ce cas, le bit de plus à gauche est un 1. Si jamais on a N de ces zéros, c'est que tous les bits du nombre sont à zéro. En matériel, cette opération est souvent utilisée dans certaines unités de calcul à virgule flottante, dans les opérations de normalisation et d'arrondis du résultat. Néanmoins, il faut préciser que seules les unités de calcul à faible performance ont besoin de déterminer le nombre de zéros les plus à gauche.

On peut calculer ce nombre de zéros à gauche simplement à partir de l'indice du 1 de poids fort, en utilisant l'équation  . On a vu plus haut comment trouver l'indice de ce 1 le plus à gauche. Le nombre de 0 à gauche est simplement égal au nombre de bits de notre nombre, auquel on soustrait la position de ce 1 :  .

Une autre méthode consiste à réutiliser le code qui calcule la puissance de 2 immédiatement supérieure. Pour rappel, la première étape de cet algorithme consiste à remplir les bits à droite du 1 de poids fort par des 1, avec des décalages successifs. Les seuls bits à rester à 0 sont les 0 de poids forts, qu'on souhaite compter. Une fois qu'on a appliqué l'algorithme, on n'a plus qu'à effectuer un calcul de population count et de soustraire le résultat de  .

unsigned NextPowerOf2 (unsigned n)
{
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;

    x = population_count( n ) ;

    return WORDBITS - x ;
}

Une autre solution consiste à effectuer la première étape, à inverser les bits et à calculer la population count. L'inversion des bits garanti que seuls les 0 de poids forts seront à 1, d'où le fait que la population count donne le bon résultat.

unsigned NextPowerOf2 (unsigned n)
{
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;

    return population_count( ! n ) ;
}

Find First SetModifier

Passons maintenant à l'opération Find First Set, qui donne la position du 1 de poids faible. On a vu plus haut que l'on peut isoler ce bit, faire en sorte de mettre tous les autres bits à 0 : il faut utiliser le calcul  . Une fois ce bit isolé, on peut trouver sa position en calculant son logarithme binaire. On a donc :

unsigned ffs (unsigned n)
{
    return log_2( x & -x ) ;
}


Manipulations intra-mots

Dans cette section, nous allons voir des manipulations qui modifient ou travaillent à l'intérieur d'un mot/d'une variable/d'un registre. Nous allons voir comment échanger deux portions à l'intérieur d'un mot, comment inverser les bits d'un mot, détecter les octets nuls, et bien d'autres.

Inverser l'ordre des bitsModifier

Inverser l'ordre des bits d'un nombre est une opération qui est assez peu courante. Cependant, elle peut être très utile dans certains algorithmes, comme ceux qui impliquent des transformées de Fourier. Pour inverser les bits d'un nombre, il suffit d'inverser les bits en position paire et impaire, puis inverser les groupes de deux bits adjacents, puis des groupes de 4 bits, et ainsi de suite jusqu’à obtenir le bon résultat. Pour cela, on peut réutiliser les masques du calcul de la population count pour sélectionner les bits/groupes de bits, et de faire quelques décalages. Le code obtenu devrait être celui-ci pour des entiers de 32 bits :

unsigned BitReverse (unsigned x)
{
    x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1 ;
    x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2 ;
    x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4 ;
    x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >> 8 ;
    x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16 ;

    return x ;
}

Les deux dernières lignes peuvent être remplacées par une seule ligne de code, qui fait l'échange entre quatre groupes de bits.

unsigned BitReverse (unsigned x)
{
    x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1 ;
    x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2 ;
    x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4 ;
    x = x << 24 | (x & FF00) << 8 | ( (x >> 8) & 0xFF00 ) | x >> 24 ;

    return x ;
}

Identification des octets nulsModifier

Dans cette section, nous allons voir comment détecter les octets nuls dans un mot/registre (pour rappel, un mot est un groupe de plusieurs octets et/ou bytes qui a la taille d'un registre). Cet algorithme est très utilisé dans des langages comme le C, notamment dans leur bibliothèque standard, pour utiliser les chaines de caractère. Les chaines de caractères du C sont stockées sous la forme d'un tableau d'octets, chaque octet codant un caractère et la fin de la chaine est indiquée par un octet nul. Si traiter la chaine octet par octet, les bibliothèques standard préfèrent traiter la chaine mot par mot, ce qui est plus rapide. Pour identifier correctement la fin de la chaine, les algorithmes utilisés doivent donc déterminer si un octet est nul dans un mot. Mais cet algorithme peut avoir d'autres utilisations, que nous ne détaillerons pas ici. Par exemple, ce code peut servir à savoir si un mot contient un octet égal à x (et non à 0). Pour cela, il suffit de faire un XOR entre chaque octet et la valeur x. Si les deux octets sont égaux et seulement si c'est le cas, l'octet sera mis à 0. On peut ensuite utiliser le code qui détermine si un octet est nul.

Version avec branchementsModifier

Dans ce qui va suivre, chaque octet sera noté de 0 à n-1 pour un mot de n octets, avec 0 l'octet de poids faible et n-1 l'octet de poids fort. L'algorithme que nous allons voir renvoie un nombre qui indique la position du premier octet nul. La valeur renvoyée est égale à n si aucun octet n'est nul dans le mot. Pour les exemples qui vont suivre, nous allons prendre un mot de 64 bits, qui a donc 8 octets numérotés de 0 à 7. Cet algorithme va commencer par calculer un booléen/bit pour chaque octet, qui indique s'il est nul ou non : il vaut 0 s'il est nul et 1 sinon. Il va ensuite combiner ces booléens/bits pour déterminer la valeur de retour.

La version qui utilise des branchements va masquer chaque mot et tester si celui-ci est nul :

unsigned FindFirstZeroByte (unsigned word)
{
    unsigned b0 = (word & 0xFF) == 0 ;
    unsigned b1 = (word >> 8 & 0xFF) == 0 ;
    unsigned b2 = (word >> 16 & 0xFF) == 0 ;
    unsigned b3 = (word >> 24 & 0xFF) == 0 ;
    unsigned b4 = (word >> 32 & 0xFF) == 0 ;
    unsigned b5 = (word >> 40 & 0xFF) == 0 ;
    unsigned b6 = (word >> 48 & 0xFF) == 0 ;
    unsigned b7 = (word >> 56 & 0xFF) == 0 ;

    if (b7)
    {
        return 7 ;
    }
    else if (b6)
    {
        return 6 ;
    }
    else if (b5)
    {
        return 5 ;
    }
    else if (b4)
    {
        return 4 ;
    }
    else if (b3)
    {
        return 3 ;
    }
    else if (b2)
    {
        return 2 ;
    }
    else if (b1)
    {
        return 1 ;
    }
    else if (b0)
    {
        return 0 ;
    }
    else
    {
        return 8 ;
    }
}

On peut remplacer les masques précédents par les suivants, qui économisent quelques opérations :

unsigned FindFirstZeroByte (unsigned word)
{
    unsigned b0 = (word & 0xFF) == 0 ;
    unsigned b1 = (word & 0xFF00) == 0 ;
    unsigned b2 = (word & 0xFF0000) == 0 ;
    unsigned b3 = (word & 0xFF000000) == 0 ;
    unsigned b4 = (word & 0xFF00000000) == 0 ;
    unsigned b5 = (word & 0xFF0000000000) == 0 ;
    unsigned b6 = (word & 0xFF000000000000) == 0 ;
    unsigned b7 = (word & 0xFF00000000000000) == 0 ;

    if (b7)
    {
        return 7 ;
    }
    else if (b6)
    {
        return 6 ;
    }
    else if (b5)
    {
        return 5 ;
    }
    else if (b4)
    {
        return 4 ;
    }
    else if (b3)
    {
        return 3 ;
    }
    else if (b2)
    {
        return 2 ;
    }
    else if (b1)
    {
        return 1 ;
    }
    else if (b0)
    {
        return 0 ;
    }
    else
    {
        return 8 ;
    }
}

Version avec prédicats et masquesModifier

Les conditions à la fin du code peuvent se remplacer par un calcul élémentaire. Pour cela, il suffit d'additionner les bits entre eux de manière à donner le résultat voulu. Si vous établissez la table de vérité du calcul, vous devriez trouver l'équation suivante :

 

Le code devient donc :

unsigned FindFirstZeroByte (unsigned word)
{
    unsigned b0 = (word & 0xFF) == 0 ;
    unsigned b1 = (word & 0xFF00) == 0 ;
    unsigned b2 = (word & 0xFF0000) == 0 ;
    unsigned b3 = (word & 0xFF000000) == 0 ;
    unsigned b4 = (word & 0xFF00000000) == 0 ;
    unsigned b5 = (word & 0xFF0000000000) == 0 ;
    unsigned b6 = (word & 0xFF000000000000) == 0 ;
    unsigned b7 = (word & 0xFF00000000000000) == 0 ;

    return b0 + (b0 & b1) + (b0 & b1 & b2) + (b0 & b1 & b2 & b3) ;
}

Ce code peut s'implémenter sans aucun branchement : il suffit que la comparaison avec zéro soit implémentée avec du code branch-free. Pour cela, il suffit d'utiliser le code pour le prédicat d'égalité, comme vu dans le chapitre précédent. Néanmoins, ce calcul est tout sauf optimal : il effectue chaque comparaison l'une après l'autre, alors que les calculs peuvent être faits en parallèle.

Calcul en parallèleModifier

Pour faire le calcul plus rapidement, il faut effectuer toutes les comparaisons en même temps, en utilisant des opérations bit à bit et des calculs arithmétiques. Le calcul que nous allons voir utilise ce principe. Il va placer les bits b0, b1, ..., b7, dans le bit de poids fort de chaque octet, comme le font les prédicats de comparaison. Ainsi, ce calcul va remplacer tous les octets nuls par 0xxx xxxx et tous les bytes non nuls par 1xxx xxx. Une solution qui marche pour les octets inférieurs à 1000 000 est d'additionner 0111 111 : en faisant cela, tous les octets nuls deviendront 0111 1111 alors que les octets non-nuls dépasseront 0111 1111. Ces derniers deviendront donc des octets de la forme 1xxx xxxx. Mais comme dit plus haut, cela ne fonctionne que pour les octets inférieurs à 1000 0000. Le problème avec ces octets est que le résultat déborde de l'octet, modifiant les résultats des autres octets. Pour faire l'addition correctement, il faut donc mettre à 0 le bit de poids fort de chaque octet pour éviter le débordement. Pour mettre le bit de poids fort à 0, il faut faire un masque avec 0x7F. Enfin, il faut additionner 0x7F (0111 1111). Le calcul effectué sur tous les octets en même temps est donc :

 

Pour prendre en compte les octets supérieurs à 1000 0000, il faut simplement faire un OU entre le résultat précédent et l'octet en question. Comme cela, si l'octet dépasse 1000 0000, le bit de poids fort du résultat sera mis à 1. Ce qui corrige le résultat précédent.

 

Le code devient donc :

unsigned FindFirstZeroByte (unsigned x)
{
    unsigned word = x = ( (x & 0x7F7F7F7F) + 0x7F7F7F7F ) | x ;

    unsigned b0 = word >> 7 ;
    unsigned b1 = word >> 15 ;
    unsigned b2 = word >> 23 ;
    unsigned b3 = word >> 31 ;
    unsigned b4 = word >> 39 ;
    unsigned b5 = word >> 47 ;
    unsigned b6 = word >> 55 ;
    unsigned b7 = word >> 63 ;

    return b0 + (b0 & b1) + (b0 & b1 & b2) + (b0 & b1 & b2 & b3) ;
}


Les prédicats de comparaison

Tous les langages de programmation gèrent les comparaisons et conditions, à l'exception de quelques langages très rares. Le résultat d'une comparaison est ce qu'on appelle un booléen, une variable qui ne peut prendre que les valeurs True et False. Au niveau du processeur, ce résultat peut être mémorisé de plusieurs manières. Les processeurs x86 mémorisent le résultat de la comparaison dans un registre d"état, dont les bits ont une interprétation prédéfinie. Ces bits sont accédés par des instructions de branchement, ce qui permet de programmer des structures de contrôles, comme des IF, WHILE, et autres. Mais il arrive que le programmeurs souhaite utiliser des booléens et faire des opérations dessus sans forcément les utiliser dans une structure de contrôle. Il est alors possible de les stocker un booléen dans une variable, certains langages ayant même un type booléen dédié. Pour donner un exemple, on pourrait citer de nombreux codes en C ou en C++. Dans le langage C, il n'existe pas de type booléen, le résultat des comparaisons pouvant cependant mémorisé dans une variable entière. Le standard stipule que cet entier code la valeur False par un 0 et la valeur True par la valeur 1. Des calculs du style x = (a < 15) * (b > 0) * d sont alors possible. Cependant, le processeur peut ne pas gérer de telles opérations nativement. Autant les processeurs sans registre d'état (les MIPS, ARM et quelques CPU RISC) le peuvent grâce à la présence de certaines instructions, ce n'est pas le cas sur les processeurs x86 ou quelques autres jeux d'instructions avec un registre d'état. Les résultats de comparaison doivent alors être calculés sans recourir à des instructions de comparaison et être calculées à grand coup d'opérations bit à bit. Voyons comment faire.

Les formules que nous allons voir placent le prédicat (le résultat de la comparaison) dans un entier, et précisément dans son bit de signe. Un simple décalage peut être utilisé pour respecter la convention 0 = False et 1 = True. Dans le cas où on doit traiter plusieurs prédicats avec des opérations logiques on peut parfaitement imaginer combiner les bits de signe avec des opérations logiques et ne faire le décalage qu'au moment où l'on doit effectivement respecter la convention. La raison qui fait que le résultat se situe dans le bit de signe tient à la manière dont on peut effectuer une comparaison. Dans la plupart des unités de calcul, les comparaisons sont implémentées avec des soustractions : on soustrait les opérandes à comparer et on effectue quelques tests sur le résultat pour déterminer les prédicats. Par exemple, un débordement de la soustraction indique que la première opérande est plus petite que celle soustraite. La logique des formules qui vont suivre est plus ou moins la même : on soustrait les deux opérandes, et on fait quelques bidouilles sur les signes ou bits de débordement.

Dans ce qui va suivre, abs(à désigne la valeur absolue, nabs son opposé, et nlz désigne l'opération Count Leading Zero et les opérandes à comparer seront notées A et B.

Le prédicat d'égalité/inégalitéModifier

Le prédicat d'inégalité, qui indique si les deux nombres comparés sont inégaux, se calcule avec les formules suivantes. La première formule est assez simple à comprendre. Il faut juste remarquer que B - A et A - B sont opposés et ont donc des signes différents : leur OU donnera un bit de signe à 1 dans le résultat. Par contre, si les deux opérandes sont égales, leur soustraction donnera 0 : le bit de signe vaudra 0 pour les deux soustractions et leur OU aussi. Ainsi, le résultat aura un bit de signe a 0 quand A = B, et à 1 sinon. La seconde formule est une reformulation de la seconde formule.

  •  
  •  

Pour le prédicat d'égalité, il suffit de prendre l'opposé des formules précédentes. Cela donne les formules suivantes :

  •  
  •  

Le prédicat d'infériorité/supérioritéModifier

Le prédicat d'infériorité et de supériorité sont deux faces d'une même pièce : il suffit de faire le calcul de l'un en inversant les opérandes pour calculer l'autre. Aussi, nous allons donc voir le prédicat d'infériorité A < B. Celui-ci existe en une version stricte : A < B, et une version non-stricte :  . Nous allons les voir dans cet ordre.

Le prédicat d'infériorité/supériorité stricteModifier

Celui-ci se calcule, comme le prédicat d'égalité, en calculant A - B et en testant les signes du résultat. Mais les opérations à réaliser sur les signes sont assez complexes à comprendre dans le détail. Pour mieux les comprendre, nous allons voir quel est le signe de A - B selon les signes de A et B, et quel est le résultat de la comparaison. Quatre cas peuvent se présenter : on soustrait un nombre positif à un autre positif, on soustrait un négatif à un positif, on soustrait un positif à un négatif et on soustrait un négatif à un négatif. Quand les opérandes sont de signes différents, on sait d'avance comment calculer le prédicat : un négatif est toujours inférieur à un positif.

Maintenant, regardons le cas où les opérandes sont de même signe. On se retrouve alors face à 4 cas différents, selon le signe de A - B. Le premier cas est celui où A et B sont positifs et A - B aussi. Dans ce cas, on sait que A > B : le prédicat est donc faux. Le second cas est celui où A et B sont positifs mais pas A - B. Dans ce cas, on sait que A < B : le prédicat est vrai. Le troisième cas est celui où les deux opérandes sont négatives : la soustraction donne donc  . Si leur soustraction donne un résultat négatif, cela signifie que B - A est positif et donc que A < B : le prédicat est vrai. Si le résultat est positif, on est dans la situation inverse : le prédicat est donc faux.

En traduisant les signes en bits de signe, on a alors :

Signe de A Signe de B Signe de A - B Prédicat A < B
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1

En utilisant la méthode des minterms, on trouve l'équation suivante :

 

Dans ce cas précis, l'équation précédente peut se simplifier en :

 

Il faut cependant faire une précision importante : les opérations précédentes doivent modifier directement l'écriture binaire des opérandes. Autant cela ne pose pas de problèmes pour les opérations logiques et bit à bit, autant la soustraction ne donnera pas le bon résultat sans conversion. En C, cela demande d'utiliser des opérandes qui sont de type unsigned, et non des int. La conversion se fait en passant par des conversions de pointeurs assez spéciales.

Le prédicat d'infériorité/supériorité non-stricteModifier

Les formules précédentes donnent un prédicat pour l'infériorité stricte A < B. Mais il est aussi possible de dériver un critère pour l'infériorité non-stricte A <= B. Pour cela, il faut simplement fusionner le critère d'égalité et celui d'infériorité : un simple OU entre les deux suffit ! L'équation obtenue peut naturellement se simplifier, avec beaucoup de labeur. La formule final obtenue est la suivante :

 

Enfin, ce prédicat peut se calculer avec une seule instruction sur certaines processeurs. La plupart des processeurs ont dans leur registre d'état un bit qui indique si une retenue a été générée par une addition/soustraction. Tout addition/soustraction modifie ce bit selon son résultat. Certains processeurs permettent, à la suite d'un calcul arithmétique, de déplacer cette retenue dans un registre en une seule instruction. Dans le cas d'une soustraction, ce bit est mis à 1 si  . En clair, l'instruction précédente permet de calculer ce prédicat en une fois, sans passer par des opérations compliquées.

Le prédicat de comparaisonModifier

Le prédicat de comparaison permet de connaitre le signe du nombre. Traditionnellement, il s'agit d'une fonction qui vaut :

 

En utilisant les prédicats de comparaison précédent, on peut calculer cette fonction signe avec les formules suivantes :

 

 

Le prédicat de signeModifier

Le prédicat de signe est une fonction qui vaut :

 

On peut remarquer que celui-ci se calcule en comparant le nombre avec 0 : il suffit d'utiliser la fonction précédente avec y = 0. On peut donc le calculer avec la fonction suivante :

 

 


Le branch-free code

De nombreuses opérations se calculent en faisant intervenir des branchements. Par exemple, si je vous demande de calculer la valeur absolue d'un entier, vous allez certainement m'écrire un code qui utilise des branchements. De nombreux calculs simples du même genre existent. Le calcul du minimum de deux nombres ou de leur maximum est l'un d'eux. Mais certains de ces calculs peuvent se faire sans utiliser de branchements ! Pour cela, il faut utiliser des techniques de manipulation de bit ou des opérations logiques. On obtient alors du branch-free code, du code sans branchements. Un tel code est très utile pour éliminer les branchements et gagner en performances. Il élimine les problèmes liés au branchements : mauvaises prédictions de branchement, meilleure utilisation du parallélisme d'instruction, etc. Le compilateur profite aussi de ces techniques, celui-ci se débrouillant mieux avec des blocs de code de grande taille. Certaines optimisations fonctionnent en effet nettement mieux quand il n'y a pas de branchements pour les gêner.

Le code branch-free est plus facile à écrire en assembleur que dans les langages de haut-niveau. La raison tient en l'utilisation des instructions à prédicat, qui rend très facile l'écriture des opérations suivantes. Le calcul du minimum ou maximum de deux nombres, qui sera vue plus loin, peut en effet s'écrire facilement avec des instructions CMOV. Les instructions à prédicats étant implémentées sur tous les jeux d'instruction grands public, les compilateurs peuvent, en théorie, les utiliser pour simplifier les opérations que nous allons voir. Mais le cout des opérations à prédicats est cependant assez élevé sur certaines architectures, ce qui rend les alternatives que nous allons présenter utiles, si ce n'est profitables. Ces techniques ont de plus le loisir d'être implémentables dans les langages de haut niveau. Voyons donc ces techniques dans le détail.

Différence avec zéroModifier

Pour le premier calcul branche-free, nous allons voir le calcul de la différence avec zéro, aussi appelée DOZ (difference of zero) par les anglo-saxons. Ce calcul très simple sera utilisé pour implémenter d'autres expressions branch-free, comme le calcul du minimum/maximum de deux nombres, ou la valeur absolue d'un nombre. Nous la voyons donc en premier, même si elle est de peu d'utilité pratique. Cette différence avec zéro se définit comme une soustraction qui donnerait 0 si son résultat est négatif.

 

Implémentation avec les prédicats de comparaisonModifier

Ce calcul s'implémente avec l'expression suivante, qui fonctionne avec des opérandes signées et non-signées :

 

int doz (int x, int y)
{
    return ( x - y ) && - ( x >= y ) ;
}

Valeur absolue et son inverseModifier

Passons maintenant à la valeur absolue et à son inverse. Si je vous demande de calculer la valeur absolue d'un entier, vous allez certainement m'écrire le code suivant :

int abs (int a)
{
    if (a > 0)
        return a ;
    else
        return - a ;
}

Mais il existe des méthodes sans branchements qui donnent le même résultat.

Valeur absolueModifier

Pour calculer la valeur absolue, il existe trois méthodes alternatives. Toutes ces méthodes nécessite d'isoler le bit de signe. Pour cela, il suffit d'utiliser un décalage logique pour déplacer ce bit et le mettre dans le bit de poids faible. Dans ce qui suit, ce bit de signe sera noté  . La valeur absolue d'un nombre x peut se calculer comme ceci :

  ;

  ;

 .

Les codes correspondant à chaque ligne est le suivant pour des entiers de 32 bits :

int abs (int x)
{
    int y = x >> 31 ;
    return (x ^ y) - y ;
}
int abs (int x)
{
    int y = x >> 31 ;
    return x - ( (x << 1) & y ) ;
}
int abs (int x)
{
    int y = x >> 31 ;
    return (x + y) ^ y ;
}

Valeur absolue inverseModifier

Pour obtenir l'inverse de la valeur absolue, il suffit de prendre l'opposée de celle-ci. En appliquant un simple - devant les expressions du dessus, on peut alors avoir diverses formules pour le calcul de l'inverse de la valeur absolue :

  ;

  ;

 .

Minimum et maximum d'un nombreModifier

Si je vous donne deux nombres et que je vous demande d'écrire un code qui renvoie le plus petit des deux, il y a de fortes chances que vous m'écriviez ceci :

int min (int a , int b)
{
    if (a > b)
        return b ;
    else
        return a ;
}

Une autre manière est d'utiliser la différence avec zéro. En effet, on sait que :

 

 

Minimum de deux nombresModifier

Si on remplace le doz par l'expression vue plus haut, on trouve :

 

Divers simplifications algébriques et booléennes donnent ensuite :

 

Voici le code qui correspond :

int min (int a , int b)
{
    return b ^ ( (a ^ b) & -(a < b) ) ;
}

L'idée derrière ce calcul est assez simple, bien que l'expression soit relativement compliquée. Pour la comprendre, il faut regarder ce qui se passe quand b < a et quand b >= a. Si b < a, alors la comparaison a < b renvoie un 0. Le terme complet (a ^ b) & -(a < b) donne alors 0 et l'expression se simplifie alors en b ^ 0, ce qui donne b. En clair, si b < a, alors le code renvoie b, ce qui est bien ce qu'on lui demande. Dans le cas où b >= a, alors la comparaison renvoie 1. Elle est alors inversée = le terme -(a < b) donne alors -1, ce qui est un nombre dont tous les bits sont à 1 en complément à 2. Le terme (a ^ b) & -(a < b) se simplifie donc en (a ^ b). L'expression totale est alors : b ^ (a ^ b). On sait que cela donne a. En clair, si a < b, le code renvoie a, ce qui lui est demandée.

Maximum de deux nombresModifier

On peut appliquer la même logique que précédemment, à savoir remplacer la doz par sa valeur calculée dans la première section. On trouve alors, après simplification, que le calcul du maximum est identique, si ce n'est qu'il faut inverser la comparaison. On doit alors calculer  

int max (int a , int b)
{
    return b ^ ( (a ^ b) & -(a > b) ) ;
}


Les opérations arithmétiques sur des entiers

Les opérations bit à bit permettent d'effectuer certains calculs arithmétiques assez simplement et souvent avec des performances très intéressantes. Dans ces conditions, effectuer des calculs arithmétiques avec des opérations bit à bit est un bon investissement. Dans ce qui va suivre, nous allons évidemment travailler avec des nombres en complément à deux.

MoyenneModifier

Calculer la moyenne de deux nombres peut sembler simple comme bonjour. Il suffit d'appliquer la formule  . Mais cette expression peut donner lieu à un débordement d'entier : le calcul de x + y peut dépasser la taille d'un registre, ce qui donnera un résultat totalement faux. Pour éviter cela, on peut ruser en utilisant des astuces mathématiques. Une première astuce consiste à reformuler l'équation   de manière à éviter d'additionner x et y. Si  , on sait que la moyenne se calcule comme suit :  . Mais cette expression peut encore être simplifiée en utilisant des opérations bit à bit, plus rapides.

Nombres non-signésModifier

Pour rappel, la somme de deux bits a et b donne un bit de résultat et une retenue. Le bit de résultat vaut  , tandis que la retenue vaut  . C'est exactement la même chose pour la somme de deux nombres A et B, si on prend en compte le fait que les retenues doivent être additionnés aux bits de résultats de la colonne suivante. On peut donc calculer la somme de deux nombres en calculant les bits de résultat (sans propager les retenues) et les retenues séparément : il suffit d'additionner ces deux termes pour obtenir le résultat. N'oublions pas que les retenues doivent être additionnées à la colonne suivante, ce qui fait que le terme pour les retenues doit être décalé d'un cran vers la gauche. Vu que les retenues se calculent en faisant   et les bits de résultat avec   , on a :

 

Maintenant, divisons le tout par deux pour obtenir la moyenne, ce qui revient à tout décaler d'un cran vers la droite. On obtient alors la formule pour calculer la moyenne :

 

Celle-ci peut être reformulée comme suit, en utilisant les identités sur l'addition et la soustraction du premier chapitre :

 

Voici le code source qui correspond à la première formule :

unsigned average (unsigned a , unsigned b)
{
    return ( a & b ) + ( a ^ b ) >> 1 ;
}

Nombres signésModifier

Le calcul de la moyenne pour les nombres signés peut se faire avec les formules précédentes, à condition de remplacer le décalage par un décalage arithmétique. Mais dans ce cas, il faut faire attention aux arrondis pour les nombres négatifs. Autant cela ne pose aucun problème pour les nombres positifs, autant l'arrondi des nombres négatifs est quelque peu erroné. Par exemple, la moyenne de -5 et -2 peut être arrondie de deux manières : soit vers 0, ce qui donne -2, soit vers   ce qui donne -3. Les calculs précédents vont causer un arrondi vers  . Pour les nombres positifs, ces deux arrondis sont identiques, mais donnent des résultats différents pour les négatifs. Pour obtenir un arrondi vers 0, les formules de la section précédente doivent être modifiées. Cette correction est simple : si x + y est négatif et impair, on l'incrémente. Pour cela, on peut prendre le bit de signe du résultat x + y ou celui de la moyenne, ces deux bits étant identiques. Pour un nombre de n bits, celui-ci se calcule avec la formule  . Une fois ce bit de signe obtenu, il faut l'additionner seulement si x + y est impair. Déterminer si la somme de deux nombres est impair est simple : le bit de poids faible doit être égal à 1. Il peut se calculer avec un XOR entre les deux opérandes à moyenner. Une fois qu'on a le bit de poids faible et le bit de signe localisés sur la même colonne, il suffit de faire un ET entre les deux : le résultat de l’opération donne un bit qui vaut 1 si la moyenne est impaire et négative, et 0 sinon. Il reste à additionner ce bit à la moyenne pour la corriger.

 

 

 

Multiplication par une constanteModifier

Les opérations de multiplication entière sont gourmandes en temps d’exécution et toute optimisation est bonne à prendre. Les compilateurs modernes sont capables d'optimiser un grand nombre de multiplications pour les remplacer par des opérations plus rapides. Cela arrive souvent lorsqu'on utilise des tableaux : les calculs d'adresses localisés dans des boucles peuvent parfois être optimisés et certaines multiplications sont alors remplacées par des additions. À ce petit jeu, la multiplication par une constante est une opportunité d'optimisation importante. On a vu précédemment qu'il est possible de remplacer la multiplication par une puissance de deux par un simple décalage. Ce qui va suivre se base sur ce principe, même si nous allons aborder la multiplication par autre chose qu'une puissance de deux. Aussi bizarre que cela puisse paraitre, il y a deux méthodes pour cela. Suivant la situation, l'une d'entre elle sera plus rapide que l'autre : tout dépend du nombre de bits à 1 dans la constante.

Décaler et additionnerModifier

Comme vous le savez, tout nombre entier est une somme de puissances de deux. C'est d'ailleurs le principe qui est derrière le binaire. Dans ce cas, multiplier par une puissance, c'est multiplier par une somme de puissances de deux. Avec quelques manipulations algébriques simples, cette multiplication peut se transformer en une somme de multiplications par une puissance de deux. Supposons que je veuille effectuer une multiplication entre un nombre A, et une constante B. Il est évident que B est une somme de puissances de deux. Dans ce cas, je peux remplacer B par la somme de puissances de deux qui correspond. Dans ce qui va suivre, nous allons prendre B = 13. Pour rappel,   :

 

En utilisant la distributivité de la multiplication, on trouve :

 

Dans cette expression, on a donc une somme, qui additionne quelques termes. Ces termes sont tous des multiplications par une puissance de deux. On peut les remplacer par un décalage vers la gauche.

 

Ainsi, la multiplication par 13 peut se remplacer en deux décalages et deux additions.

Le principe reste le même pour toute multiplication par une constante : en décomposant la constante en puissances de deux, et avec quelques calculs, on peut transformer une multiplication par une constante en série de décalages et d'additions. Le nombre de décalages effectué est égal au nombre de bits à 1 dans la constante. Le nombre d'additions est presque identique. Si la constante contient donc trop de bits à 1, il se peut que le nombre de décalages et d'additions soit trop important : une multiplication peut être plus rapide. Cette technique ne marche donc que pour les nombres ayant un nombre de bits à 1 faible : 2-3 bits, parfois plus sur les architectures ayant une multiplication particulièrement lente, mais pas plus.

Décaler et soustraireModifier

Dans le cas où un nombre contient beaucoup de bits à 1, il existe une seconde méthode. Elle se base sur un principe légèrement différent, mais assez similaire à celui utilisé dans la méthode précédente. Comme vous le savez, un nombre entier peut s'écrire sous la forme d'une somme de puissances de deux. Par exemple,  . Ceci dit, 5 peut aussi s'écrire sous une autre forme. Si on remarque bien,  . Dans cette expression, 8 est une puissance de 2, et 3 est un nombre comme un autre. Si on réfléchit bien, tout nombre entier peut s'écrire sous la forme  .

Prenons un exemple avec une multiplication par 5.

 

Dans cette expression, on peut remplacer chaque nombre par son expression en binaire. En clair, on le remplace par la somme de puissances de deux qui correspond.

 

 

Maintenant, supposons que l'on veuille multiplier un nombre A par 5. On peut alors remplacer 5 par l'expression avec décalages et soustractions :

 

En se rappelant que la multiplication est distributive, on obtient :

 

Dans cette expression, on peut alors remplacer les multiplications par des puissances de deux par des décalages à gauche :

 

Comme on le voit, cette expression ne contient que des décalages et des soustractions. Et le principe est le même pour tout entier. Il suffit d'écrire la constante comme une puissance de deux à laquelle on aurait soustrait ce qu'il faut. Pour cela, il suffit de prendre la puissance de deux immédiatement supérieure à notre constante : cela simplifie les calculs et diminue le nombre de soustractions. On a donc l'équation : constante + nombre à soustraire = puissance de deux choisie. Si on calcule sur n bits, la puissance de deux aura n+1 bits et vaudra donc zéro. En clair : constante + nombre à soustraire = 0. Ce qui signifie que constante = - nombre à soustraire : le nombre à soustraire est donc le complément à deux de la constante, codé sur n bits. Cela nous dit donc que plus un nombre à de bits à 1, plus son complément à deux aura de bits à 0 : le nombre de soustractions à effectuer sera donc plus faible. Cette technique marche donc nettement mieux pour les nombres remplis de 1.

Division par une constanteModifier

Après la multiplication par une constante, il faut savoir que la division par une constante peut aussi être améliorée. On sait déjà ce qu'il en est pour la division par une puissance de deux : il suffit de la remplacer par un décalage vers la droite, en prenant garde à bien choisir entre décalage arithmétique et logique. Pour ce qui est de la division par une constante arbitraire, il est possible d'utiliser une technique d'optimisation particulièrement efficace : la multiplication réciproque. Cette technique nous permet de remplacer la division par une constante en une multiplication. Les divisions étant des opérations nettement plus lentes que les multiplications, on peut facilement gagner quelques dizaines de cycles d'horloge.

Mais tout d'abord, nous devons préciser une chose. Lorsqu'on multiplie deux nombres de   bits, leur produit a une taille qui est de   bits. Dans le détail, on a besoin de deux fois plus de bits pour le résultat. D'ordinaire, on s'en moque, et on se contente de garder les   bits de poids faible. Mais dans ce qui va suivre, nous allons avoir besoin des   bits de poids fort. Heureusement, certains processeurs disposent d'instructions de multiplications qui calculent ces bits de poids fort, le résultat étant enregistré dans deux registres : un pour les bits de poids faible, un autre pour les registres de poids forts. D'autres processeurs disposent d'une instruction qui effectue la multiplication et ne conserve que les bits de poids forts dans un registre. Enfin, certains processeurs disposent d'instructions de multiplication configurables, qui permettent de choisir quels bits conserver : poids fort ou poids faible.

La multiplication réciproque est basée sur un principe simple : diviser par  , c'est multiplier par  . Si N est une constante, alors on peut pré-calculer   et éliminer ainsi la division. Et là, un premier problème semble se faire jour : cela marche peut-être pour les nombres flottants, mais ne peut pas fonctionner avec des nombres entiers. Mais on peut sauver le principe en remplaçant   par une constante judicieusement choisie, dont la multiplication donnera le résultat voulu. Si on multiplie par cette constante et que l'on garde les bits de poids forts, on obtiendra le même résultat qu'avec une multiplication par   (sur les bits de poids faible). Cette constante vaut, par définition :  . En effet, regardons ce que donne l’opération suivante, avec A le nombre qu'on cherche à diviser par N :

 

 

 

En clair, on obtient le résultat de la division de A par N, mais décalé de n rangs : on obtient bien le résultat de la division dans les bits de poids fort.

Cette méthode demande que le calcul de   tombe juste, qu'il n'y aie pas de part fractionnaire. Mais ce n'est pas le cas pour certaines constantes, notamment N = 10, 7, 11, et grosso-modo, tout ce qui n'est pas une puissance de deux. Dans ce cas, le mieux est de rechercher des constantes proches de la constante réciproque qui donnent de meilleurs résultats. Cependant, l'imprécision de la constante réciproque est alors à l'origine d'erreurs de calcul et le résultat doit être corrigé avant d'être utilisable. Cette correction est une simple addition, qui ajoute un paramètre déterminé, fixe, qui dépend de la constante.


Les opérations arithmétiques sur des flottants

Après avoir vu comment certains calculs entiers peuvent se réaliser via des opérations logiques, il est temps de voir des astuces de calcul sur des nombres flottants. Dans ce qui va suivre, nous allons travailler avec des nombres flottants au format IEEE754, le format le plus courant (pour ne pas dire le seul utilisé à l'heure actuelle).

Valeur absolueModifier

Nous allons poursuivre par une opération extrêmement simple : la valeur absolue. On sait que les flottants sont codés avec une représentation spéciale. Pour rappel, un nombre flottant encode est encodé avec un bit de signe, un champ pour l'exposant et un champ pour la mantisse. La valeur décimale du flottant se calcule comme suit :

Comme on le voit, le signe d'un flottant est indiqué par un bit de signe, localisé dans le bit de poids fort. Obtenir sa valeur absolue demande simplement de mettre ce bit de signe à 0. Un simple masque suffit ! Cependant, cela demande de travailler sur l'écriture binaire du flottant, chose qui n'est pas possible sans quelques tricks assez velus. En C et dans les autres langages de ce type, les opérations bit à bit ne fonctionnent pas sur les flottants, sans compter que le masque est obligatoirement un entier. Pour travailler sur l'écriture binaire, le mieux est de passer par des conversions de pointeurs : on prend un pointeur sur le flottant à traiter, on le convertit en pointeur vers un unsigned/int, et on déréférence : ob a alors l'écriture binaire du flottant directement dans un entier (si le flottant et l'entier ont des tailles identiques). Le code est donc le suivant :

(((int *) &x) + 1) &= 0x7fffffff ;

Comparaisons entre flottantsModifier

Chose peu connue, il est possible de comparer deux nombres flottants en utilisant les comparaisons pour nombres entiers. Du fait de leur encodage, les comparaisons entre flottants et entiers sont différentes sur le papier. Mais dans les faits, quelques propriétés de l'encodage des flottants fait que l'on peut comparer deux flottants comme s'ils s'agissait d'entiers sans problèmes. Ce que cela veut dire, c'est que si l'on prend l'écriture binaire de deux flottants, et que l'on compare ces écritures comme s'il s'agissait d'entiers, alors le résultat de la comparaison sera le bon. Cela vient du fait que deux flottants consécutifs auront un encodage consécutifs, chose qui est garantie par la norme IEEE754. Tout du moins, cela fonctionne dans la plupart des cas, bien que cela demande quand même quelques précisions. Premièrement, l'encodage du bit de signe pose quelques problèmes : les nombres négatifs suivent les positifs du point de vue de l'écriture binaire. La solution est alors d'utiliser une comparaison signée. Pour régler ce problème, il suffit d'inverser le bit de signe avec le masque adéquat.

LogarithmeModifier

Nous verrons dans quelques chapitres comment trouver le logarithme d'un entier, pour des raisons liée à la nature de ce calcul, mais la méthode que nous aborderons ne fonctionne évidemment pas sur les nombres flottants. Pour ceux-ci, il existe cependant une méthode assez simple, qui demande de passer par l'écriture binaire du flottant en question. La technique que l'on va voir donne un résultat entier, pas un flottant.

Calcul pour un flottant non-dénormalModifier

Pour un flottant positif, on a donc :

 

Si on prend le logarithme en base 2, on a :

 

Vu que le logarithme d'un produit est égal à la somme des logarithmes, on a :

 

 

Vu que la mantisse est comprise entre 0 et 1, on a :  . Le terme   est un terme qui sert à corriger le résultat final. En injectant dans l'expression précédente, on a la formule suivante. Dans celle-ci, la mantisse m et le terme de correction   sont des nombres fractionnaires, compris entre 0 et 1. Ce qui fait qu'on les éliminera dans les calculs qui vont suivre. Mais si on travaillait en virgule fixe, nous devrions les prendre en compte. Nous le ferons d'ailleurs dans la suite de ce cours.

 

Vu que l'on travaille avec des nombres entiers, le second et le troisième terme ne doivent pas être pris en compte, vu qu'ils sont fractionnaires, ce qui donne :

 

Pour faire ce calcul, il suffit de prendre l'écriture binaire du flottant, de faire quelques décalages. Il faut cependant se souvenir que l'exposant est encodé en représentation par excès, ce qui fait qu'il doit lui soustraire un biais pour obtenir sa valeur normale. Le code devrait être le suivant pour un flottant 32 bits (simple précision). La première ligne permet de traiter directement l'écriture binaire du flottant, afin de faire les décalages et autres. Il faut cependant signaler que ce code ne fonctionne pas avec les flottants dénormaux.

float rsqrt(float n)
{
    long i  = * ( long * ) &n ;
    unsigned e = (c >> 23) - 127 ;
    return e ;
}

Interprétation de l'écriture binaire d'un flottantModifier

 
L'écriture binaire d'un flottant est égale à une constante près, à un multiple de son logarithme en base 2.

Nous allons terminer cette section par une petite anecdote, qui sera utile dans la suite du cours. Nous allons voir que la représentation binaire d'un flottant a un lien très profond avec son logarithme. Pour faire simple, l'écriture binaire du flottant approxime très bien le logarithme binaire encodé en virgule fixe. Dit autrement, l'écriture binaire d'un flottant est égale à une constante près, à un multiple de son logarithme en base 2. La représentation binaire du flottant sera notée   dans ce qui suit. Elle est composée de l'exposant placé à gauche de la mantisse. Dit autrement, pour une mantisse de   bits, on a :

 

On voit que l'écriture binaire est égale au logarithme, mais multiplié par un facteur  . Le tout tenant dans un entier codé en binaire simple, on a donc bien un nombre encodé en virgule fixe. Cependant, l'exposant   est codé en représentation par excès sous la forme  , ce qui donne :

 

La mantisse   est de plus censée être comprise entre 0 et 1. La mantisse   contenue dans le nombre flottant est en réalité une version décalée par n rangs de la valeur encodée (vu que la mantisse est codée sur n bits. On a donc :

 

 

On peut alors égaliser cette formule avec l'équation vue plus haut :  .

 

Ce qui donne une approximation du logarithme binaire en virgule fixe, avec un facteur de conversion égal à L.

 

 

Racine carrée inverseModifier

Dans cette section nous allons nous intéresser au calcul de la racine carrée inverse, à savoir :  . L'algorithme utilisé pour la calculer s'appelle la méthode de Newton/Raphson, ou encore méthode de Newton. Sans rentrer dans des considérations mathématiques trop compliquée, celle-ci a besoin d'une approximation pas trop mauvaise du résultat, qui sera notée  . A partir de cette approximation, cette méthode applique un calcul de manière répétée, le résultat du calcul s'approchant de plus en plus du résultat réel. Cette méthode marche pour de nombreuses fonctions, tel le logarithme, l'exponentielle, et bien d'autres, et est naturellement utilisée pour la racine carrée inverse. Dans le cas de la racine carrée inverse, ce calcul est le suivant :

 

Reste à calculer l'approximation de base  . Pour cela, il existe diverses méthodes que nous allons maintenant aborder.

Passage par le logarithmeModifier

La première méthode se base sur l'identité mathématique suivante :

 

Pour simplifier les calculs pour un ordinateur, il est naturel de prendre le logarithme en base 2 de l'opérande.

 

La solution consiste donc à calculer le logarithme de l'opérande, multiplier par - 0.5, et prendre le logarithme inverse (l'exponentielle). On sait déjà comment calculer ce logarithme en base 2 pour un entier, la division ne pose pas de problèmes (c'est un simple décalage) et le calcul de l'exponentielle est trivial :  . Mais cette méthode ne fonctionne que pour des entiers : il faut donc convertir le nombre flottant voulu en entier et appliquer dessus les calculs. Ce qui pose de gros problèmes : il faudrait des entiers extrêmement longs, de plusieurs centaines de bits, pour pouvoir faire le calcul sans approximation extrême. La solution qui consiste à faire les calculs sur les flottants est encore pire, vu que le calcul du logarithme et de l'exponentielle se font alors par la méthode de Newton et sont donc aussi rapides/lents que le calcul de la racine carrée inverse. Mais comme nous allons le voir dans la suite, il existe un moyen de ruser !

Passage par la représentation entièreModifier

Pour cela, il faut juste réutiliser ce qu'on a vu dans la section sur le logarithme. On sait qu'on peut donner une approximation du logarithme à partir de la représentation entière   d'un flottant. On a, pour rappel :

 

En injectant dans l'équation  , on a :

 

On peut alors déduire la représentation entière du résultat en appliquant la formule  . On a donc, en notant   la représentation entière du résultat :

 

 

 

Pour un flottant 32 bits, le terme de droite vaut : : . On a donc :

 

Évidemment, il ne s'agit là que d'une approximation. Le code correspondant est le suivant :

float rsqrt(float number)
{
    long i  = * ( long * ) &y ; // Bidouille qui permet de traiter l'écriture binaire d'un flottant.
    i  = 0x5f3759df - ( i >> 1 ) ; // Utilisation du calcul précédent, en remplaçant la division par deux par un décalage.
    float y  = * ( float * ) &i; // Conversion du résultat en flottant, facultatif.

    return y;
}

Racine carrée inverse rapideModifier

 
Imprécision de la racine carré inverse.

Les raisonnements précédents sont à 'origine d'une bidouille vraiment intéressante, incorporée dans certains moteurs de jeux vidéo. Celle-ci se base sur le principe vu dans la section précédente. On ne sait pas qui l'a inventé, mais il est devenu célèbre lors de la publication du code source de Quake 3 arena, un vieux fast FPS comme on en fait plus, très sympa à jouer en LAN. Un vrai jeu, quoi ! Bref, dans les jeux vidéo, on a souvent besoin de calculer la racine carrée inverse. Ce calcul est évidemment effectué sur des nombres flottants. Mais à l'époque de la création de ce jeu vidéo, les opérations flottante étaient très lentes. Et elles le sont toujours un petit peu, d'ailleurs. Pour diminuer la lenteur du calcul de la racine carrée inverse, on a inventé la Fast Inverse SQRT, afin de calculer celle-ci en utilisant uniquement des opérations entières ! Cet algorithme prend un flottant 32 bits, et donne une approximation de la racine carrée inverse. La qualité de cette approximation est illustrée à droite. Cet algorithme est très simple, jugez plutôt :

float rsqrt(float number)
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;
    x2 = number * 0.5F;
    y  = number;

    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
    y  = * ( float * ) &i;

    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
    //y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

La version en C moderne, à laquelle on aurait omis quelques optimisations, donnerait ceci :

float rsqrt(float number)
{
    float y  = number;

    long i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
    y  = * ( float * ) &i;

    y  = y * ( 1.5F - ( y * y * number / 2 ) );   // 1st iteration
    //y  = y * ( 1.5F - ( y * y * number / 2 ) );   // 2nd iteration, this can be removed

    return y;
}

Les deux dernières lignes de code, dont celle mise en commentaire, correspondent chacune à une itération de la méthode de Newton. On peut remarquer que l'auteur de cette routine a appliqué quelques optimisations sur ce calcul : il a notamment remplacé la division par 2 par une multiplication par 0.5, les multiplications étant plus rapides que les divisions. Les lignes de code précédentes calculent une approximation assez précise de la racine carrée inverse, qui est ensuite utilisée telle quelle par la méthode de Newton. Le premier "bloc" de code contient de simples déclarations de variables utilisées dans le calcul, la plupart servant uniquement à rendre les calculs plus lisibles. Les lignes suivantes contiennent des conversions et déréférencements entre pointeurs qui permettent d’accéder directement à l'écriture binaire du flottant, afin de traiter celle-ci avec des opérations logiques comme s'il s'agissait d'un entier. Le calcul de l'approximation réutilise ce qu'on a vu dans la section précédente, par la ligne de code suivante :

i  = 0x5f3759df - ( i >> 1 ) ;


Les débordements d'entiers

Les instructions arithmétiques et quelques autres manipulent des entiers de taille fixe, qui ne peuvent prendre leurs valeurs que dans un intervalle. Si le résultat d'un calcul sort de cet intervalle, il ne peut pas être représenté par l'ordinateur : il se produit ce qu'on appelle un débordement d'entier. Dans la plupart des applications, ces débordements ne posent pas le moindre problème. Mais pour d'autres situations, ces débordements doivent être détectés avant ou juste après leur occurrence. Certains processeurs disposent d'instructions pour détecter de tels débordements. D'autres, comme les processeurs x86, utilisent le registre d'état pour mémoriser l’occurrence d'un débordement. Si une opération entraine un débordement, un bit dédié du registre d'état est mis à 1. Mais ce bit n'est pas accessible depuis les langages de programmation de haut niveau, et des solutions logicielles de détection des débordements doivent être utilisées si besoin. Dans ce qui va suivre, nous allons voir comment détecter ces débordements avec des opérations bit à bit et des comparaisons.

Taille des opérandesModifier

Tout d'abord, il faut considérer la taille des opérandes en nombre de bits. Quand les opérandes ne sont pas du même type, le compilateur convertira généralement tous les opérandes vers le type ayant le plus grand nombre de bits. Si certains langages n'ont pas ce comportement, il faudra explicitement ajouter cette conversion.

Les sections suivantes partent du principe que cette conversion a déjà eu lieu et que les opérandes ont tous le même nombre de bits. Le nombre de bits à considérer étant le plus grand parmi les opérandes, ou celui du type utilisé dans une conversion explicite.

Opérations non-signéesModifier

Les débordements peuvent avoir lieu autant avec des nombres signés que non-signés. Nous allons commencer par voir les opérations sur des nombres non-signés, qui sont nettement plus simples.

Addition et soustractionModifier

Quand la somme X + Y déborde, le processeur va conserver les bits de poids faible du résultat et ne calculera pas les bits de poids fort (ou alors, il les oubliera). Les conséquences sont différentes selon que les opérandes soient considérées comme signées ou non-signées. Dans le cas des nombres non-signés, un débordement fait que la somme X + Y n'est pas aussi grande que ce qu'elle devrait. On peut même dire que la somme X + Y est systématiquement inférieure à X et à Y. En effet, si la somme X + Y <= X, alors cela signifie que la valeur Y est plus grande que la valeur d'un registre, d'où paradoxe. On a donc :  . Le truc, c'est qu'une seule condition suffit, l'une entrainant naturellement l'autre, ce qui donne :  . En simplifiant, via les règles d'utilisation des opérations logiques lors des comparaisons, on trouve :

 

Les conditions précédentes peuvent s'adapter pour la soustraction, en tenant compte de l'équation  . Cette fois-ci, on sait qu'il y a débordement si :  . Ce qui donne :

 

MultiplicationModifier

Le cas de la multiplication et de la division sont assez différents de l'addition/soustraction. Le cas de la division est cependant le plus simple : le diviseur et le reste étant inférieurs par définition au diviseur, il ne peut pas y avoir de débordements d'entiers lors d'une division entière.

Mais c'est très loin d'être le cas pour la multiplication. En effet, la multiplication d'une opérande de m bits par une autre opérande de n bits donne un résultat codé sur m + n bits. Vu que tous les processeurs utilisent des opérandes de même taille, on sait que la multiplication donnera un résultat de   bits pour des registres de n bits. Le résultat va donc prendre deux registres.

Certains processeurs se contentent de garder les   bits de poids faible, ce qui fait que les débordements sont monnaie courante. Heureusement, certains processeurs disposent d'instructions de multiplications qui calculent ces bits de poids fort, le résultat étant enregistré dans deux registres : un pour les bits de poids faible, un autre pour les registres de poids forts. D'autres processeurs disposent d'une instruction qui effectue la multiplication et ne conserve que les bits de poids forts dans un registre. Enfin, certains processeurs disposent d'instructions de multiplication configurables, qui permettent de choisir quels bits conserver : poids fort ou poids faible. Ceux-ci permettent de détecter facilement un débordement. Pour le cas d'une multiplication non-signée, le débordement se détecte facilement : il suffit de regarder les bits de poids fort du résultat. Si le registre pour les bits de poids fort est nul, cela signifie qu'il n'y a pas eu débordement. Il y a eu débordement s'il n'est pas nul.

Si le processeur se contente de garder les bits de poids faible du résultat, on peut quand même détecter les débordements. Pour cela, il suffit de faire la multiplication   et de faire l'opération inverse : vérifier que l'on obtient bien   en divisant le résultat par  . Si on obtient le bon résultat, alors il n'y a pas eu débordement. Mais en cas de débordement, les bits perdus vont fausser le résultat de la division. En conséquence, la division ne redonnera pas l'opérande initiale. Cette méthode donne le bon résultat à une exception près : le cas où l'une des opérandes est nulle, qui pose des problèmes lors de la division. Il est possible de détecter le débordement sans faire la multiplication  , en utilisant la formule suivante. Dans cette formule,   est le plus grand entier codable en complément à deux.

 

Une autre solution se base sur un raisonnement plus simple. On a dit plus haut que le produit de deux nombres de a et b bits donne un résultat de a + b bits. Si les registres du processeur sont de n bits, alors on a un débordement si a + b > n. L'idée est alors de déterminer quel est le nombre de bits du nombre. Pour cela, on peut utiliser le nombre de zéros non-significatifs à gauche, obtenu avec l'opération Count Leading Zero. Celle-ci renvoie naturellement n - a et n - b quand on l'applique sur les opérandes. En additionnant ces deux valeurs, on a :  . On a alors :  . En couplant avec la condition a + b < n, on obtient l'inégalité suivante s'il n'y a pas de débordement :

 

Opérations signéesModifier

Passons maintenant aux opérations sur les nombres signés. Là encore, nous verrons les additions/soustractions, avant de passer aux multiplications et aux divisions. Vous noterez la présence des divisions dans cette section, les divisions signées pouvant déborder.

Addition et soustractionModifier

D'après les règles du complément à deux, on sait que le bit de poids fort (le plus à gauche) permet de déterminer si le nombre est positif ou négatif : il indique le signe du nombre. Tout se passe comme si les entiers en complément à deux étaient codés sur un bit de moins, et avaient leur longueur amputé du bit de poids fort. Si le résultat d'un calcul a besoin d'un bit de plus que cette longueur, amputée du bit de poids fort, le bit de poids fort sera écrasé; donnant un débordements d'entiers. Il existe une règle simple qui permet de détecter ces débordements d'entiers. L'addition (ou la multiplication) de deux nombres positifs ne peut pas être un nombre négatif : on additionne deux nombres dont le bit de signe est à 0 et que le bit de signe du résultat est à 1, on est certain d'être en face d'un débordements d'entiers. Même chose pour deux nombres négatif : le résultat de l'addition ne peut pas être positif. On peut résumer cela en une phrase : si deux nombres de même signe sont ajoutés, un débordement a lieu quand le bit du signe du résultat a le signe opposé. On peut préciser que cette règle s'applique aussi pour les nombres codés en complément à 1, pour les mêmes raisons que pour le codage en complément à deux. Cette règle est aussi valable pour d'autres opérations, comme les multiplications.

DivisionModifier

La première possibilité de débordement correspond à une division par zéro, quand  . Le second cas correspond au cas où l'on divise le plus petit entier par -1. Pour comprendre pourquoi, rappelons la règle suivante :  . Notons maintenant le plus petit et le plus grand entier codable en complèment à deux :   et  . On a alors :

 

 

 

 

Pour résumer, un débordement a lieu lors d'une divisions non-signée X / Y quand :

 

Cette expression peut se reformuler de plusieurs manières, qui sont listées ci-dessous.

 

 

  GFDL Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans texte de dernière page de couverture.