Ouvrir le menu principal

Les opérations bit à bit/Les prédicats de comparaison

< Les opérations bit à bit

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.

Sections

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 :