« Les opérations bit à bit/Manipulations sur les bits de poids faible/fort » : différence entre les versions

Navigation interactive dans l’historique

← Modification précédente Modification suivante →

Contenu supprimé Contenu ajouté

Intégrés

Version du 20 octobre 2021 à 20:56

Dans cette section, nous allons voir comment effectuer certaines opérations qui manipulent certains bits de poids fort ou certains bits de poids faible. Mais avant de commencer, un petit point sur la terminologie de ce chapitre. Nous aurons à utiliser des expressions du type "le 1 de poids faible", "les 0 de poids faible" et quelques autres du même genre. Quand nous parlerons du 0 de poids faible, nous voudrons parler du premier 0 que l'on croise dans un nombre en partant de sa droite. Par exemple, dans le nombre 0011 1011, le 0 de poids faible est le troisième bit en partant de la droite. Quand nous parlerons du 1 de poids faible, c'est la même chose, mais pour le premier bit à 1. Par exemple, dans le nombre 0110 1000, le 1 de poids faible est le quatrième bit. Quant aux expressions "le 1 de poids fort" et "les 0 de poids fort" elles sont identiques aux précédentes, sauf qu'on parcourt le nombre à partir de sa gauche.

Par contre, les expressions "les 1 de poids faible" ou "les 0 de poids faible" ne parlent pas de la même chose. Quand nous voudrons parler des 1 de poids faible, au pluriel, nous voulons dire : tous les bits situés avant le 0 de poids faible. Par exemple, prenons le nombre 0011 0011 : les 1 de poids faible correspondent ici aux deux premiers bits en partant de la gauche. Même chose quand on parle des zéros de poids faible au pluriel. Quant aux expressions "les 1 de poids fort" ou "les 0 de poids fort" elles sont identiques aux précédentes, sauf qu'on parcourt le nombre à partir de sa gauche.

Manipuler les bits de poids fort/faible avec un masque

Il y a quelques chapitres, nous avons vu que les masques permettent de remplacer certains bits d'un nombre soit par des 0, soit par des 1. Dans ce qui va suivre, nous allons voir ce qui se passe quand on fait cela soit pour les bits de poids fort, soit pour ceux de poids faible. Par bits de poids fort/faible, nous ne voulons pas parler d'un bit précis, mais des $n$ bits de poids faible/fort, le nombre $n$ pouvant être choisit arbitrairement. En tout, cela fait quatre possibilités :

remplacer les bits de poids faible par des zéros ;
remplacer les bits de poids faible par des 1;
remplacer les bits de poids fort par des zéros;
remplacer les bits de poids fort par des 1.

La dernière possibilité ne nous intéressera pas, parce qu'elle ne correspond pas à une opération utile. Par contre, les trois autres possibilités correspondent à des opérations utiles, surtout la troisième. Pour faire ces opérations, nous aurons besoin d'utiliser des masques pour sélectionner les $n$ bits de poids faible/fort. Pour cela, il faut utiliser un masque, comme nous l'avons vu dans les chapitres précédents. Le masque qui permet de sélectionner les $n$ bits de poids faible a ses $n$ bits de poids faible à 1 et les autres à zéro, ce qui fait qu'il est égal à $2^{n}-1$ . Celui pour les sélectionner les bits de poids fort est l'inverse de ce masque. Par inverse du masque, on veut dire que les bits à 0 passent à 1 et réciproquement. Sous forme mathématique, cela donne :

Pour sélectionner les n bits de poids faible et mettre les autres à zéro, l'opération est un ET entre le masque et le nombre.

x.(2^{n}-1)

, le + étant ici un OU logique.

Pour mettre les n bits de poids faible à 1, l'opération à effectuer est un OU entre le masque et le nombre à masquer. Sous forme mathématique, cela donne :

x+(2^{n}-1)

, le + étant ici un OU logique.

Pour mettre les n bits de poids faible à 0, il faut faire un ET avec l'inverse du masque.

x.({\overline {2^{n}-1}})

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

x.(-2^{n})

Les trois opérations donnent des résultats très différents, mais qui peuvent se comprendre assez facilement quand on connait les rudiments de la division. Et pour mieux comprendre, le mieux est de regarder ce qui se passe quand on effectue les opérations équivalentes en décimal. Les opérations équivalentes consistent à remplacer certains chiffres par des 0 ou par des 9. Par exemple, mettre à zéro les bits de poids faible revient en décimal à mettre à zéro les N derniers chiffres. Mettre à 1 les $n$ bits de poids faible revient en décimal à remplacer les n derniers chiffres par des 9. Et idem pour les bits de poids fort.

Manipuler les bits de poids fort : le calcul du modulo

Comme dit plus haut, les puissances de 10 ont en décimal le même rôle que les puissances de deux en binaire. Une division décimale par 10, 100, 1000, est en quelque sorte la même chose qu'une division binaire par 2, 4, 8. Or, la division décimale et le modulo décimal sont très simples avec les puissances de 10. Diviser par 10 demande juste d'éliminer le dernier chiffre, diviser par 100 demande d'éliminer les deux derniers chiffres, diviser par 1000 demande d'éliminer les trois derniers chiffres, etc. De manière générale, diviser par $10^{n}$ demande d'éliminer les $n$ derniers chiffres. Pour le modulo, c'est la même chose. Le reste d'une division par 10 demande de conserver le dernier chiffre, à savoir le chiffre qui serait effacé par la division par 10. De même, le modulo par 100 demande de conserver juste les deux derniers chiffres, le modulo par 1000 demande de conserver les trois derniers chiffres, le modulo par 10000 les quatre derniers chiffres, etc.

En binaire, c'est la même chose, sauf que les chiffres sont ici les bits. En clair, il faut éliminer les n derniers bits pour obtenir le quotient, les conserver pour trouver le modulo. Le résultat d'une division binaire par $2^{n}$ est composé des bits de poids forts, ceux au-delà du rang $n$ . Le résultat du modulo par $2^{n}$ , quant à lui, est composé des $n$ bits de poids faible. Le tout est illustré dans le schéma ci-dessous.

On retrouve le fait qu'une division par $2^{n}$ se calcule en faisant un décalage vers la droite de n rangs. Et à l'opposé, on comprend ce qui se passe quand on masque les bits de poids fort, en les remplaçant par des zéros : on calcule le modulo par $2^{n}$ . Calculer le modulo par $2^{n}$ demande juste de garder les $n$ bits de poids faible. Pour comprendre pourquoi cela fonctionne, partons de l'écriture en binaire d'un nombre :

2^{x}+2^{x-1}+2^{x-2}+...+2^{2}+2^{1}+2^{0}

Par définition, le modulo d'un nombre prend le reste de la division par un entier, c’est-à-dire ce qu'il reste une fois qu'on a éliminé tous les multiples du quotient. Sachant que dans notre cas, le quotient est égal à $2^{n}$ , cela veut dire qu'on doit supprimer tous les multiples de $2^{n}$ dans l'écriture binaire de notre nombre, en les mettant à zéro. Et cela revient en fait à ne conserver que les n bits les plus à droite dans l'écriture binaire de notre nombre.

Manipuler les bits de poids faible : des arrondis liés à des multiples de $2^{n}$

Maintenant, nous allons voir ce qui se passe quand on met les n bits de poids faible d'un nombre à 0 ou à 1. Ces bits correspondent au modulo par $2^{n}$ , ce qui fait que nous les appellerons tout bonnement : le modulo, sous-entendu le modulo à $2^{n}$ . Quand il sera fait mention de "mettre le modulo à 0", cela vaudra dire que tous les n bits de poids faible seront mis à 0. Et pour l'expression "mettre le modulo à sa valeur maximale", cela vaudra dire que tous les n bits de poids faible seront mis à 1.

Les deux opérations, à savoir mettre le modulo à zéro ou à 1, sont liés à des arrondis particuliers. Les arrondis en question arrondissent au multiple de $2^{n}$ immédiatement supérieur ou inférieur. Pour comprendre à quoi correspondent ces arrondis, prenons l'exemple du nombre 46, qu'on souhaite arrondir au multiple de 8 immédiatement supérieur/inférieur. Le fait est que 46 n'est pas un multiple de 8, mais est situé entre deux multiples de 8 : 48 (8*6) et 40 (8*5). Arrondir 46 au multiple de 8 immédiatement supérieur donne 46, alors qu'arrondir au multiple de $2^{n}$ immédiatement inférieur donne 40. La même logique peut s'appliquer pour les multiples de 4, 16, 32 et autres. Par exemple, reprenons le nombre 46 et arrondissons-le au multiple de 16 immédiatement supérieur/inférieur. Arrondir au multiple de 16 immédiatement inférieur donne 32 (16*2), alors qu'arrondir au multiple de 16 immédiatement supérieur 48 (16*3).

Dans ce qui va suivre, nous allons noter $N$ le nombre à arrondir. Le multiple de $2^{n}$ immédiatement inférieur sera noté $M_{inf}$ , alors que le multiple immédiatement supérieur sera noté $M_{sup}$ . On a alors :

M_{inf}\leq N<M_{sup}

Par définition, $M_{inf}$ et $M_{sup}$ sont des multiples de $2^{n}$ , et qui plus est deux multiples consécutifs. On a donc :

k\times 2^{n}\leq N<(k+1)\times 2^{n}

Cette inégalité sera très importante pour comprendre comment calculer les arrondis en question.

Mettre les bits de poids faible à zéro

Pour commencer, regardons ce qui se passe quand on met les bits de poids faible à zéro et essayons de donner un sens au résultat. L'idéal est de comparer avec ce qui se passe avec l'opération équivalente en décimal. Celle-ci revient, dans un nombre décimal, à remplacer les N derniers chiffres par des zéros. Par exemple, mettre le dernier chiffre à 0 revient à arrondir à la dizaine la plus proche, mettre les deux derniers chiffres à 0 revient à arrondir à la centaine la plus proche, mettre les trois derniers chiffres à 0 revient à arrondir au millier le plus proche, etc. En clair : remplacer les N derniers chiffres par des 0 revient à arrondir au multiple de $10^{N}$ immédiatement inférieur. En binaire, c'est la même chose, mais avec les bits et des puissances de 2.

Pour comprendre le sens du résultat, il faut revenir sur la division euclidienne de N par $2^{n}$ . Par définition de la division euclidienne, on a :

N=q\times 2^{n}+r

, avec r le reste, qui est une constante inférieure à

2^{n}

.

Rappelons que les n bits de poids faible d'un nombre sont le modulo par $2^{n}$ . Si l'on met le modulo par $2^{n}$ à zéro, cela revient à tout simplement soustraire le reste, le modulo proprement dit. On trouve :

N-r=q\times 2^{n}

Par définition, le terme de droite est le multiple de $2^{n}$ le plus proche de N, mais qui lui est immédiatement inférieur. Vous comprenez donc pourquoi je parle de ces arrondis particuliers juste après la section sur la division et le modulo par $2^{n}$ ! Tout cela pour dire que :

M_{inf}=q\times 2^{n}

M_{sup}=(q+1)\times 2^{n}

Mettre les bits de poids faible à 1

Maintenant, regardons ce qui se passe quand on met tous les bits du modulo non pas à zéro, mais à 1. En clair, le modulo est remplacé par la plus grande valeur qu'il peut prendre. Pour comprendre le sens du résultat de cette opération, repartons encore une fois de N écrit comme suit :

N=q\times 2^{n}+r

L'opération met le reste à sa valeur maximale, qui est composée de n bits tous à 1, qui est par définition égale à $2^{n}-1$ . Le remplacement donne donc un nombre $R$ tel que :

R=q\times 2^{n}+(2^{n}-1)

Pour comprendre le résultat, rappelons que l'on a : $M_{inf}=q\times 2^{n}$ . En faisant le remplacement, on a :

R=M_{inf}+(2^{n}-1)

En identifiant avec : $M_{sup}=(q+1)\times 2^{n}$ , on trouve que le résultat est de :

R=M_{sup}-1

En clair, mettre tous les n bits de poids fort d'un nombre à 1 donne le nombre qui est juste avant le multiple de $2^{n}$ immédiatement supérieur. Dit autrement, calculer le multiple de $2^{n}$ immédiatement supérieur demande de mettre les n bits de poids faible à 1 et d'incrémenter.

Manipuler les bits de poids faible, grâce à un incrément

Dans la section précédente, nous avons vu ce qu'il se passe quand on masque un nombre avec un nombre de la forme $2^{n}-1$ . Mais ce n'est pas la seule possibilité et d'autres masques peuvent être utilisés. Le cas le plus intéressant est d'utiliser un masque qui se calcule en incrémentant/décrémentant le nombre à masquer. Pour le dire plus clairement, nous allons étudier des calculs comme $x.(x-1)$ , $x.(x+1)$ , $x|(x-1)$ , etc. Pour comprendre comment ces formules fonctionnent, il faut voir en quoi un nombre et son suivant différent en binaire. Et pour cela, on doit parler de comment incrémenter un nombre en binaire avec seulement des opérations bit à bit.

Pour comprendre comment cela fonctionne, commençons d'abord par faire un rappel sur l'addition en binaire. La table d'addition est très simple en binaire. Jugez plutôt :

0 + 0 = 0, retenue = 0 ;
0 + 1 = 1, retenue = 0 ;
1 + 0 = 1, retenue = 0 ;
1 + 1 = 0, retenue = 1.

Évidemment, la retenue se propage au bit suivant, exactement comme en décimal.

Incrémenter un nombre revient à lui ajouter le nombre 000 ... 001, à savoir un nombre dont seul le bit de poids faible est à 1. En clair, incrémenter un nombre consiste juste à incrémenter le bit de poids faible et à propager les retenues. Regardons ce qui se passe quand on incrémente le bit de poids faible. S'il vaut 0, il passe alors à 1 et il n'y a pas de retenue à propager. Mais s'il vaut 1, il passe à 0 et une retenue est propagée sur la colonne suivante. Et si une retenue est propagée, la même chose se reproduit à la colonne suivante, et ainsi de suite... Au final, on voit que la propagation de la retenue s'arrête au premier bit à 0 rencontré, mais se propage tant que les bits de poids faible sont à 1.

Pour clarifier les choses, prenons un nombre de la forme suivante : XXXX ... XXXX 0111 ... 1111. Dans ce cas, l'incrémentation fait passer ce nombre de XXXX ... XXXX 0111 ... 1111 à XXXX ... XXXX 1000 ... 1111. Le premier zéro rencontré passe à 1, et tous les bits précédents passent à 0.

Notons que cette logique marche aussi s'il n'y a pas de 1 de poids faible : le bit de poids faible passe alors juste de 0 à 1.

Le seul cas un peu trompeur est celui où il n'y a pas de bit à zéro, dont l'incrémentation donne un débordement d'"entier. Mais dans ce cas, la gestion traditionnelle des débordement fait que le résultat est tout bonnement zéro.

Nombre à incrémenter	Résultat de l'incrémentation
XXXX ... XXXX ... XXX0	XXXX ... XXXX ... XXX1
XXXX ... X011 ... 1111	XXXX ... X100 ... 0000
1111 ... 1111 ... 1111	0000 ... 0000 ... 0000

Concrètement, les bits qui changent après incrémentation sont le 0 de poids faible et les bits précédents (les trailing ones).

En sachant ceci, vous pouvez facilement déterminer ce que donne le résultat de calculs comme $x.(x+1)$ , ${\overline {x}}|(x+1)$ ou encore $x|(x+1)$ . Ces opérations vont donc modifier le 0 de poids faible et/ou les trailing ones.

Mettre à 0 les 1 de poids faible

Fort de ce qui vient d'être dit, regardons ce que fait l'opération suivante :

x.(x+1)

Reprenons le tableau précédent et regardons quel est le résultat de l’opération :

$x$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111 ... 1111 ... 1111
$x+1$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000 ... 0000 ... 0000
$x.(x+1)$	XXXX ... XXXX ... XXX0	XXXX ... X000 ... 000	0000 ... 0000 ... 0000

Si on analyse le résultat du tableau, on voit que la seule différence entre $x$ et $x+1$ est dans les bits de poids faible. Tous les bits de poids faible à 1, ceux situés avant le premier bit à 0, sont mis à 0.

Mettre à 1 le 0 de poids faible

Maintenant, regardons ce qui se passe si on remplace le ET par un OU.

x|(x+1)

Reprenons le tableau de l'incrémentation et regardons quel est le résultat de l’opération :

$x$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111 ... 1111 ... 1111
$x+1$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000 ... 0000 ... 0000
$x.(x+1)$	XXXX ... XXXX ... XXX1	XXXX ... X111 ... 1111	1111 ... 1111 ... 1111

On voit que cette opération permet de mettre à 1 le zéro de poids faible, à savoir le premier bit à 0 en partant des bits de poids faible.

Mettre à 0 les bits situés à gauche du 0 de poids faible

Maintenant, étudions le résultat de cette opération :

x.\left({\overline {x+1}}\right)

Ce calcul ressemble aux précédents, sauf que cette fois-ci, on a pris de NOT du résultat de l'incrémentation.

Reprenons le tableau des cas possibles. Précisons que pour un bit quelconque, noté X, son NOT sera noté Y.

$x$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111 ... 1111 ... 1111
$x+1$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000 ... 0000 ... 0000
${\overline {x+1}}$	YYYY ... YYYY ... YYY0	YYYY ... Y011 ... 1111	0000 ... 0000 ... 0001
$x.\left({\overline {x+1}}\right)$	0000 ... 0000 ... 0000	0000 ... 0011 ... 1111	0000 ... 0000 ... 0001

Le tableau montre que ce calcul isole les 1 de poids faible. En clair, tous les bits situés à gauche du 0 de poids faible sont mis à 0.

Isoler le 0 de poids faible

Maintenant, étudions le résultat de cette opération, qui n'est autre que l'opération précédente dans laquelle on a remplacé le ET par un OU :

x|\left({\overline {x+1}}\right)

Reprenons le tableau des cas possibles. Précisons que pour un bit quelconque, noté X, son NOT sera noté Y.

$x$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111 ... 1111 ... 1111
${\overline {x+1}}$	YYYY ... YYYY ... YYY0	YYYY ... Y011 ... 1111	0000 ... 0000 ... 0001
$x.\left({\overline {x+1}}\right)$	1111 ... 1111 ... 1110	1111 ... 1011 ... 1111	1111 ... 1111 ... 1111

On voit que tous les bits sont mis à 1, sauf un : le zéro le plus à droite, le zéro de poids faible. On dit que ce calcul isole le 0 de poids faible.

Isoler le 0 de poids faible et l'inverser

Maintenant, regardons ce que fait l'opération suivante :

{\overline {x}}.(x+1)

Reprenons le tableau précédent et regardons quel est le résultat de l’opération :

$x$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111 ... 1111 ... 1111
$x+1$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000 ... 0000 ... 0000
${\overline {x}}$	YYYY ... YYYY ... YYY1	YYYY ... Y100 ... 0000	0000 ... 0000 ... 0000
${\overline {x}}.(x+1)$	0000 ... 0000 ... 0001	0000 ... 0100 ... 000	0000 ... 0000 ... 0000

On voit que l'opération a pour un résultat un nombre dont le seul bit à 1 est situé à la position du zéro de poids faible de l'opérande.

Isoler les 1 de poids faible et inverser

Maintenant, regardons ce que fait l'opération suivante :

{\overline {x}}|(x+1)

Reprenons le tableau précédent et regardons quel est le résultat de l’opération :

$x$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111 ... 1111 ... 1111
$x+1$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000 ... 0000 ... 0000
${\overline {x}}$	YYYY ... YYYY ... YYY1	YYYY ... Y100 ... 0000	0000 ... 0000 ... 0000
${\overline {x}}.(x+1)$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 000	0000 ... 0000 ... 0000

On voit que cette opération isole les 1 de poids faible ceux situés avant le zéro de poids faible, mais inverse le résultat.

Manipuler les bits de poids faible/fort, grâce à un décrément

Maintenant, étudions ce qui se passe quand on décrémente un nombre. Il se passe alors la même chose qu'avec l'incrémentation, si ce n'est qu'on doit remplacer la table d'addition par la table de soustraction. Il y a toujours une retenue à propager d'une colonne vers la suivante, en partant du bit de poids faible. Par contre, la retenue est soustraite.

La table de soustraction est la suivante :

0 - 0 = 0, retenue = 0 ;
0 - 1 = 1, retenue = 1 ;
1 - 0 = 1, retenue = 0 ;
1 - 1 = 0, retenue = 0.

Décrémenter un nombre revient à lui soustraire le nombre 000 ... 001, à savoir un nombre dont seul le bit de poids faible est à 1. En clair, on soustrait 1 au bit de poids faible et on propage les retenues s'il y en a. La propagation de la retenue ne s'arrête cependant pas au même moment que la retenue d'une incrémentation. La raison est que la table de soustraction et d'addition sont différentes et que les cas où une retenue se propage ne sont pas les mêmes. Avec la décrémentation, la propagation de la retenue s'arrête au premier bit à 1 rencontré. Les bits avant ce premier 1 sont inversés et passent de 0 à 1. Si on reprend le tableau des trois cas possibles, voici ce que cela donne.

Nombre à décrémenter	Résultat de la décrémentation
XXXX ... XXXX ... XXX1	XXXX ... XXXX ... XXX0
XXXX ... X100 ... 0000	XXXX ... X011 ... 1111
0000 ... 0000 ... 0000	1111 ... 1111 ... 1111

Les bits qui changent après décrémentation sont le 1 de poids faible et les 0 précédents.

En sachant ceci, vous pouvez facilement déterminer ce que donne le résultat de calculs comme $x.(x-1)$ ou encore $x|(x-1)$

Mettre à 0 le 1 de poids faible

Commençons par voir ce que donne ce calcul :

x.(x-1)

Le tableau des cas possibles donne ceci :

$x$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000... 0000... 0000
$x-1$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111... 1111... 1111
$x.(x-1)$	XXXX ... XXXX ... XXX0	XXXX ... X000 ... 0000	0000... 0000 ... 0000

On remarque que ce calcul ne change qu'un seul bit du nombre initial, pas un de plus, pas un de moins. Et ce bit, qui passe de 1 à 0, est le 1 le plus à droite dans l'écriture binaire, à savoir le 1 de poids faible.

$x$	$x.(x-1)$
1111 1111	1111 1110
1111 1110	1111 1100
1111 1000	1111 0000
0010 1000	0010 0000
0010 0000	0000 0000

Notons que ce calcul permet de vérifier si un nombre est une puissance de deux. Si ce calcul donne pour résultat zéro, alors le nombre $x$ est une puissance de deux. En effet, 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.

Mettre à 1 le ou les 0 de poids faible

On peut maintenant se demander ce qui se passe quand on effectue non pas un ET, mais un OU, soit l'opération suivante :

x|(x-1)

Le tableau des cas possibles donne ceci :

$x$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000... 0000... 0000
$x-1$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111... 1111... 1111
$x.(x-1)$	XXXX ... XXXX ... XXX1	XXXX ... X111 ... 1111	1111... 1111... 1111

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.

Isoler le 1 de poids faible

A votre avis, que donne le résultat de cette opération :

x.(-x)

Cela semble n'avoir aucun rapport avec les opérations précédentes, mais rappelez-vous des règles du complément à deux. Celles-ci disent que $-x={\overline {x}}+1={\overline {x-1}}$ . En clair, ce calcul est équivalent au suivant :

x.\left({\overline {x-1}}\right)

On prend le tableau des différentes possibilités :

$x$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000 ... 0000 ... 0000
$x-1$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111 ... 1111 ... 1111
${\overline {x-1}}$	YYYY ... YYYY ... YYY1	YYYY ... Y100 ... 0000	0000 ... 0000 ... 0000
$x.\left({\overline {x-1}}\right)$	0000 ... 0000... 0001	0000 ... 0100 ... 0000	0000 ... 0000 ... 0000

On voit que cette opération isole le 1 de poids faible, c'est à dire que le 1 de poids faible est conservé, tandis que tous les autres bits sont mis à zéro.

Isoler les 0 de poids faible

Reprenons l'opération précédente et remplacons le ET par un OU :

x|\left({\overline {x-1}}\right)

On prend le tableau des différentes possibilités :

$x$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000 ... 0000 ... 0000
${\overline {x-1}}$	YYYY ... YYYY ... YYY1	YYYY ... Y100 ... 0000	0000 ... 0000 ... 0000
$x\|\left({\overline {x-1}}\right)$	1111 ... 1111 ... 1111	1111 ... 1100 ... 0000	0000 ... 0000 ... 0000

On voit que cette opération isole les 0 de poids faible, c'est à dire les bits situés avant le 1 de poids faible. Tous les autres bits sont mis à 1.

Isoler les 0 de poids faible et inverser

Étudions maintenant ce calcul :

{\overline {x}}.(x-1)

;

Le tableau des cas possibles donne ceci :

$x$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000... 0000... 0000
${\overline {x}}$	YYYY ... YYYY ... YYY0	YYYY ... Y011 ... 1111	1111 ... 1111 ... 1111
$x-1$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111... 1111... 1111
$x.(x-1)$	0000... 0000... 0000	0000 ... 0011 ... 1111	1111... 1111... 1111

On voit que cette formule isole les 0 de poids faible, ceux situés avant le premier bit à 0, et inverse le tout. Par exemple, le nombre 0110 1100 1111 0000 deviendra : 0000 0000 0000 1111. Ou encore, le nombre 0101 1000 deviendra 0000 0111.

D'autres formules équivalentes peuvent être utilisées. Les voici :

${\overline {x+(-x)}}$ ;
$(x.-x)-1$ .

Isoler le 1 de poids faible et inverser

Étudions maintenant ce calcul :

{\overline {x}}|(x-1)

;

Le tableau des cas possibles donne ceci :

$x$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000... 0000... 0000
${\overline {x}}$	YYYY ... YYYY ... YYY0	YYYY ... Y011 ... 1111	1111 ... 1111 ... 1111
$x-1$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111... 1111... 1111
$x.(x-1)$	1111... 1111... 1110	1111 ... 1011 ... 1111	1111... 1111... 1111

On voit que cette formule isole le 1 de poids faible et inverse le tout. En clair, le résultat est un nombre dont tous les bits sont à 1, sauf à la position du 1 de poids faible dans l'opérande.

Manipuler le ou les bits de poids fort

Les opérations précédentes, basées sur un incrément ou un décrément, permettent d'isoler ou de manipuler les 0/1 de poids faible. Mais ils ne peuvent pas toucher aux 0/1 de poids fort. La raison est que la retenue se propage soit jusqu’au zéro de poids faible (incrémentation), soit jusqu'au 1 de poids faible (décrémentation). Manipuler le 1 ou le 0 de poids fort est plus compliqué. Dans ce qui va suivre, nous allons donner un code qui permet d'agir sur les bits qui précédent le 1 de poids fort.

Mettre à 1 les bits situés avant le 1 de poids fort

Pour commencer, nous allons voir comment mettre à 1 tous les bits situés avant le 1 de poids fort. Pour donner un exemple, cela permet de transformer 0010 1101 en 0011 1111. Ou encore, cela transforme 0001 0010 en 0001 1111. L'utilité de cette manipulation ne vous parait pas évidente, mais sachez que nous l'utiliserons dans la suite du chapitre.

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 $2^{n}-1$ 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 $2^{n}-1$ . Pour être plus précis, il s'agit du nombre de la forme $2^{n}-1$ . 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. Mais 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 que spécifique aux nombres de 32 bits, est le suivant :

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

Une interprétation mathématique de ce calcul est qu'il donne le nombre de la forme $2^{n}-1$ immédiatement supérieur. Par exemple, 5 donnera 7 (8-1), 25 donnera 31 (32-1), 250 donnera 255 (256-1), etc.

Le calcul de la puissance de deux immédiatement supérieure

Maintenant que l'on sait calculer le nombre de la forme $2^{n}-1$ immédiatement supérieur, on peut facilement deviner comment calculer la puissance de deux immédiatement supérieure à un nombre. Avec un tel calcul, 5 aurait pour résultat 8, 25 donnerait 32, 250 donnerait 256, etc. On pourrait croire qu'il suffirait de prendre le code précédent et d'y ajouter une incrémentation. Dans les faits, ce code ainsi modifié marcherait, mais échouerait dans le cas où le nombre considéré serait lui-même une puissance de deux. Pour éviter cela, il suffit d'ajouter une décrémentation en première instruction.

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

FFS, FFZ, CTO et CLO

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. Cette opération est liée à l'opération Count Trailing Zeros, qui donne le nombre de zéros situés à droite de ce 1 de poids faible. L'opération Find First Set est opposée au calcul du Find highest set, qui donne la position du 1 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 en remplaçant les 0 par des 1 et réciproquement. 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.

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.

Si on choisit la première convention, certaines opérations sont équivalente. Par exemple, les opérations Count Trailing Zeros et Find First Set donnent toutes les deux le même résultat.
Avec l'autre convention, les deux différent de 1 systématiquement.

Dans ce qui va suivre, nous allons utiliser la première convention, ce qui fait que nous n'aurons qu'à aborder quatre calculs :

le Find First Set, abréviée FFS ;
le Find highest set, abrévié FHS ;
le Find First Zero, abréviée FFZ ;
le Find highest Zero, abrévié FHZ.

Avec cette convention, pour un nombre codé sur $n$ bits, on a :

fhs+clz(n)=n-1

fhz+clo(n)=n-1

ffs=ctz(n)

ffz=cto(n)

Find highest set : le logarithme binaire

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 $2^{n}$ . 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 $2^{0}$ : le 0-ème bit du nombre est mis à 1. Supposons maintenant que cette propriété soit vraie pour $n$ et regardons ce qui se passe pour $n+1$ . Dans ce cas, $2^{n+1}=2\times 2^{n}=2^{n}<<1$ . 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 $x$ , 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 : $2^{n}\leq x<2^{n+1}$ . En prenant le logarithme de l'inégalité précédente, on a : $\log _{2}{2^{n}}\leq \log _{2}{x}<\log _{2}{2^{n+1}}$ . Par définition du logarithme en base 2, on a : $n\leq \log _{2}{x}<n+1$ . Dit autrement, le logarithme en base 2 d'un nombre est égal à $n$ , 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érative

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 dichotomie

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 $n$ bits. L'algorithme commence par vérifier si le bit de poids fort est dans les $n \over 2$ bits de poids fort ou dans les $n$ bits de poids faible. Si le bit de poids fort est dans les $n$ bits de poids forts, alors on sait que le logarithme est d'au moins $n \over 2$ et peut lui être supérieur ou égal. On mémorise donc $n \over 2$ bits comme valeur temporaire du logarithme. On décale alors le nombre de $n \over 2$ bits vers la droite pour le ramener dans l'autre intervalle. Et on continue, mais en vérifiant les $n \over 4$ bits de poids fort, et ainsi de suite.

Méthode basée sur le poids de Hamming

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 $2^{n}-1$ immédiatement supérieur. Ce nombre, par définition, a tous les bits de rang $\leq n$ à 1 : il suffit de compter ses 1 pour obtenir le rang $n$ ! 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 Zeros

L'instruction Count leading zeros a pour objectif de compter les zéros situés après le 1 de poids fort. Ce nombre de leading zéros peut varier entre 0 et N. S'il vaut zéro, le bit de plus à gauche est un 1. S'il vaut N, 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 :

fhs(n)+clz(n)=n-1

Il existe deux autres méthodes qui commencent toutes deux par mettre à 1 tous les bits situés à droite du 1 de poids fort. Une fois cela fait, il y a deux possibilités.

La première est d'effectuer un calcul de population count et de soustraire le résultat de $n$ .

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

    x = population_count( n ) ;

    return WORDBITS - x ;
}

L'autre solution est d'inverser les bits et de 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 countLeadingZeros (unsigned n)
{
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;

    return population_count( ~ n ) ;
}

Find First Set

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, avec le calcul $x.(-x)$ . 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 ) ;
}

◄ Retour vers « Les masques »

Sommaire du livre

Continuer vers « Manipulations intra-mots » ►

Version du 20 octobre 2021 à 20:56

Manipuler les bits de poids fort/faible avec un masque

Manipuler les bits de poids fort : le calcul du modulo

Manipuler les bits de poids faible : des arrondis liés à des multiples de 2 n {\displaystyle 2^{n}}

Mettre les bits de poids faible à zéro

Mettre les bits de poids faible à 1

Manipuler les bits de poids faible, grâce à un incrément

Mettre à 0 les 1 de poids faible

Mettre à 1 le 0 de poids faible

Mettre à 0 les bits situés à gauche du 0 de poids faible

Isoler le 0 de poids faible

Isoler le 0 de poids faible et l'inverser

Isoler les 1 de poids faible et inverser

Manipuler les bits de poids faible/fort, grâce à un décrément

Mettre à 0 le 1 de poids faible

Mettre à 1 le ou les 0 de poids faible

Isoler le 1 de poids faible

Isoler les 0 de poids faible

Isoler les 0 de poids faible et inverser

Isoler le 1 de poids faible et inverser

Manipuler le ou les bits de poids fort

Mettre à 1 les bits situés avant le 1 de poids fort

Le calcul de la puissance de deux immédiatement supérieure

FFS, FFZ, CTO et CLO

Find highest set : le logarithme binaire

Méthode itérative

Méthode par dichotomie

Méthode basée sur le poids de Hamming

Count Leading Zeros

Find First Set

Manipuler les bits de poids faible : des arrondis liés à des multiples de $2^{n}$