Barrel shifter

Il existe deux grands types de décalages : les décalages logiques, et les décalages arithmétiques.

Décalage logique

Le décalage logique, aussi appelé logical shift, consiste à décaler tous les chiffres d'un ou plusieurs crans vers la gauche ou la droite. Lors du décalage, des vides apparaissent dans la représentation binaire du nombre : ceux-ci sont alors remplis avec des zéros.

Grâce à ce remplissage par des zéros, un décalage vers la gauche de n rangs est équivalent à une multiplication par ${\displaystyle 2^{n}}$ pour des entiers non-signés ou pour des entiers signés positifs. Même chose pour le décalage vers la droite qui revient à diviser un nombre entier par ${\displaystyle 2^{n}}$. Avec des nombres signés, ce n'est pas le cas : on obtient un résultat qui n'a pas grand sens mathématiquement.

Cette propriété est souvent utilisée par certains compilateurs, qui préfèrent utiliser des instructions de décalages (qui sont des instructions très rapides) à la place d'instructions de multiplication ou de division qui ont une vitesse qui va de moyenne (multiplication) à particulièrement lente (division).

Il faut remarquer un petit détail : lorsqu'on effectue un décalage à droite -, certains bits de notre nombre vont sortir du résultat et être perdus. Cela a une conséquence : le résultat est tronqué ou arrondi. Plus précisément, le résultat d'un décalage à droite de n rangs sera égal à la partie entière du résultat de la division par ${\displaystyle 2^{n}}$.

Décalage arithmétique

Les décalages arithmétiques sont similaires aux décalages logiques, à un détail près : pour les décalages à droite, le bit de signe de notre nombre n'est pas modifié, et on remplit les vides laissés par le décalage avec le bit de signe.

Ces instructions sont équivalentes à une multiplication/division par ${\displaystyle 2^{n}}$, que le nombre soit signé ou non, à un détail près : l'arrondi n'est pas fait de la même façon pour les nombres positifs et négatifs. Pour donner un exemple, ${\displaystyle {\frac {9}{2}}}$ sera arrondi en 4, tandis que ${\displaystyle {\frac {-9}{2}}}$ sera arrondi en -5.

Rotation de bits

Les rotations sont similaires aux décalages, à ceci près que chaque bit sortant est réinjecté à la place libérée par le décalage.

Ces opérations sont très utiles en cryptographie, notamment dans certains algorithmes de chiffrement. Les rotations sont aussi très utiles dans certains cas particuliers dans lesquels on doit manipuler des données bit par bit. Par exemple, un calcul du nombre de bits à 1 dans un nombre peut s'implémenter de façon naïve avec des instructions de rotation.

Décaleur logique - principe

Un circuit capable d'effectuer des décalages logiques est conçu sur un principe très simple. Par exemple, décaler un nombre de 7 rangs vers la droite, c'est le décaler de 4 rangs, puis le décaler de 2, puis le décaler de 1. On voit que notre décalage par 7 peut être décomposé en plusieurs sous-décalages par 4, 2 et 1. Et bien c'est la même chose pour tous les autres décalages : ceux-ci peuvent être décomposés en décalages de n rangs, avec n une puissance de 2.

On peut ensuite profiter du fait que l'écriture binaire de notre nombre nous permet de connaitre exactement quelles sont ces puissances de 2. Pour chaque bit à 1 dans la représentation binaire de notre nombre de rangs, on doit effectuer un décalage égal à ${\displaystyle 2^{P}}$, avec P le poids du bit en question. Il ne reste plus qu'à construire des décaleurs par 1, 2, 4, 8, 16, etc.