|
==Le calcul du nombre de la forme <math>2^n - 1</math> immédiatement supérieur==
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 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 <math>2^n - 1</math> immédiatement supérieur, est en effet très simple à faire. Nous avions vu comment calculer ce nombre dans le chapitre sur la manipulation des bits de poids fort/faible. En fait, calculer ce nombre consiste juste à mettre à 1 tous les bits situés après le 1 de poids fort. En adaptant le code pour ce faire, on trouve :
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 qu'un petit peu amélioré et spécifique aux nombres de 32 bits, est le suivant :
<syntaxhighlight lang="c">
|
