Les opérations bit à bit/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 vrai et faux (True et False). Un bit suffit pour stocker cette valeur : en général 0 représente faux et 1 représente vrai.

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 stocker un booléen dans une variable, certains langages ayant même un type booléen dédié.

Dans le langage Java, le type boolean permet d'utiliser les valeurs booléennes false et true.

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 C ANSI 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 possibles. 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é

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 égaux, 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 à 0 quand A = B, et à 1 sinon. La seconde formule est une reformulation de la seconde formule.

• $(B-A)|(A-B)$

• $nabs(A-B)$

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

• ${\overline {(B-A)|(A-B)}}$

• $abs(A-B)-1$

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

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 : $A\leq B$. Nous allons les voir dans cet ordre.

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

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égatifs : la soustraction donne donc $-A-(-B)=B-A$. 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 :

$(a.{\overline {b}})|\left[(a-b).{\overline {a\oplus b}}\right]$

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

$(a.{\overline {b}})|\left[(a-b).(a|{\overline {b}})\right]$

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-stricte

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 :

$({\overline {a}}|b).\left[(a\oplus b)|({\overline {b-a}})\right]$

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 $A\leq B$. 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 comparaison

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

$signe(x,y)=\left\{{\begin{array}{r c l}1,x>y\\0,x=y\\-1,x<y\\\end{array}}\right.$

En utilisant les prédicats de comparaison précédent, on peut calculer cette fonction signe avec la formule suivante :

$(x>y)-(x<y)$

Pour comprendre cette formule, le mieux est de regarder d'étudier tous les cas possibles pour les comparaisons $x>y$ et $x<y$ et d'en déduire le résultat du calcul complet.

$x>y$	$x<y$		$(x>y)-(x<y)$
0	0		0
0	1		-1
1	0		1
1	1		Impossible

Une autre formule possible est la suivante :

$(x\geq y)-(x\leq y)$

Là encore, étudions tous les cas possibles pour voir ce que fait ce calcul.

$x\geq y$	$x\leq y$		$(x\geq y)-(x\leq y)$
0	0		Impossible
0	1		-1
1	0		1
1	1		0

Le prédicat de signe

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

$signe(n)=\left\{{\begin{array}{r c l}1,n>0\\0,n=0\\-1,n<0\\\end{array}}\right.$

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 :

$(x>0)-(x<0)$

$(x\geq 0)-(x\leq 0)$

Le prédicat d'inégalité des signes

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 );
}

Ou bien avec 3 comparaisons :

int SignUnequals (int a , int b)
{
    return ( a < 0 ) != ( b < 0 ); // Ou encore  ( 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 ;
}