« Les opérations bit à bit/Manipulations sur les bits de poids faible/fort » : différence entre les versions
Contenu supprimé Contenu ajouté
Ligne 569 :
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 indirectement sur les bits de poids fort. Ce code permet de 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 <math>2^n - 1</math> 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 <math>2^n - 1</math>. Pour être plus précis, il s'agit du nombre de la forme <math>2^n - 1</math>. 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 :
<syntaxhighlight lang="c">
unsigned SetBitsAfterHighestOne(unsigned n)
{
n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
}
</syntaxhighlight>
==FFS, FFZ, CTO et CLO==
| |||