Différences entre les versions de « Les opérations bit à bit/Manipulations sur les bits de poids faible/fort »

m
Dans un ordinateur, les nombres sont de taille fixe. Un nombre est ainsi stocké sur 8, 16, 32, 64 bits. Si jamais un nombre peut être représenté en utilisant moins de bits que prévu, les bits qui restent sont mis à zéro. Par exemple, sur une architecture 8 bits, le nombre 5 ne sera pas stocké comme ceci : 101, mais comme ceci : 00000101. On voit donc que ce nombre contient un certain nombre de zéros non-significatifs. Ces zéros sont placés à gauche du nombre. Plus précisément, notre nombre aura certains de ses bits à 1. Parmi ceux-ci, il y aura un de ces bits qui sera plus à gauche que tous les autres 1. A gauche de ce 1, on peut éventuellement trouver un certain nombre de zéros non-significatifs. L'instruction '''Count leading zeros''' a pour objectif de compter ces zéros non-significatifs. Pour un nombre de N bits, le nombre de ces zéros à gauche peut varier entre 0 et N. Si on a 0 zéros non-significatif, dans ce cas, le bit de plus à gauche est un 1. Si jamais on a N de ces zéros, 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 <math>\log_2{fhs(n)} + clz(n) = n - 1</math>. On a vu plus haut comment trouver l'indice de ce 1 le plus à gauche. Le nombre de 0 à gauche est simplement égal au nombre de bits de notre nombre, auquel on soustrait la position de ce 1 : <math>clz(n) = n - \log_2{fhs(n)} - 1</math>.
 
Une autre méthode consiste à réutiliser le code qui calcule la puissance de 2 immédiatement supérieure. Pour rappel, la première étape de cet algorithme consiste à remplir les bits à droite du 1 de poids fort par des 1, avec des décalages successifs. Les seuls bits à rester à 0 sont les 0 de poids forts, qu'on souhaite compter. Une fois qu'on a appliqué l'algorithme, on n'a plus qu'à effectuer un calcul de population count et de soustraire le résultat de <math>n</math>.
38 065

modifications