Opération au niveau du bit

Les décalages de bits sont parfois considérés comme des opérations au niveau du bit, car ils traitent une valeur comme une série de bits plutôt que comme une quantité numérique. Dans ces opérations, les chiffres sont déplacés, ou décalés, vers la gauche ou la droite. Les registres dans un processeur d’ordinateur ont une largeur fixe, de sorte que certains bits seront « décalés » du registre à une extrémité, tandis que le même nombre de bits sont « décalés » de l’autre extrémité; les différences entre les opérateurs de décalage de bits résident dans la façon dont ils déterminent les valeurs des bits décalés.

Adressage de bitedit

Si la largeur du registre (fréquemment 32 voire 64) est supérieure au nombre de bits (généralement 8) de la plus petite unité adressable (élément atomique), fréquemment appelée octet, les opérations de décalage induisent un schéma d’adressage sur les bits.Sans tenir compte des effets de limite aux deux extrémités du registre, les opérations de décalage arithmétique et logique se comportent de la même manière, et un décalage de 8 positions de bits transporte le motif de bits de 1 position d’octet de la manière suivante:

Décalage arithmétique

Décalage arithmétique à gauche

Décalage arithmétique à droite

Dans un décalage arithmétique, les bits décalés de chaque extrémité sont ignorés. Dans un décalage arithmétique à gauche, les zéros sont décalés à droite; dans un décalage arithmétique à droite, le bit de signe (le MSB dans le complément de deux) est décalé à gauche, préservant ainsi le signe de l’opérande.

Cet exemple utilise un registre 8 bits, interprété comme le complément de deux:

 00010111 (decimal +23) LEFT-SHIFT= 00101110 (decimal +46)

 10010111 (decimal −105) RIGHT-SHIFT= 11001011 (decimal −53)

Dans le premier cas, le chiffre le plus à gauche a été décalé au-delà de la fin du registre et un nouveau 0 a été déplacé dans la position la plus à droite. Dans le second cas, le 1 le plus à droite a été décalé (peut-être dans le drapeau de report), et un nouveau 1 a été copié dans la position la plus à gauche, préservant le signe du nombre. Plusieurs quarts de travail sont parfois raccourcis à un seul quart de travail d’un certain nombre de chiffres. Par exemple:

 00010111 (decimal +23) LEFT-SHIFT-BY-TWO= 01011100 (decimal +92)

Un décalage arithmétique gauche par n équivaut à multiplier par 2n (à condition que la valeur ne déborde pas), tandis qu’un décalage arithmétique droit par n de la valeur du complément d’un deux équivaut à diviser par 2n et à arrondir vers l’infini négatif. Si le nombre binaire est traité comme un complément, la même opération de décalage vers la droite entraîne une division par 2n et un arrondi vers zéro.

Changement logiquemodifier

Décalage logique à gauche

Décalage logique à droite

Dans un décalage logique, des zéros sont déplacés pour remplacer les bits rejetés. Par conséquent, les décalages à gauche logiques et arithmétiques sont exactement les mêmes.

Cependant, comme le décalage à droite logique insère la valeur 0 bits dans le bit le plus significatif, au lieu de copier le bit de signe, il est idéal pour les nombres binaires non signés, tandis que le décalage à droite arithmétique est idéal pour les nombres binaires complémentaires de deux signés.

Décalage circulairedit

Une autre forme de décalage est le décalage circulaire, la rotation au niveau du bit ou la rotation du bit.

Rotatifmodifier

Déplacement circulaire gauche ou rotation

Déplacement ou rotation circulaire à droite

Dans cette opération, parfois appelée rotation sans report, les bits sont « tournés » comme si les extrémités gauche et droite du registre étaient jointes. La valeur qui est décalée vers la droite pendant un décalage vers la gauche est la valeur qui a été décalée vers la gauche, et vice versa pour une opération de décalage vers la droite. Ceci est utile s’il est nécessaire de conserver tous les bits existants, et est fréquemment utilisé en cryptographie numérique.

Tourner à travers le portemodifier

Rotation à gauche par le portage

Rotation à droite à travers carry

Rotate through carry est une variante de l’opération de rotation, où le bit qui est décalé (à chaque extrémité) est l’ancienne valeur de l’indicateur de report, et le bit qui est décalé (à l’autre extrémité) devient la nouvelle valeur de l’indicateur de report.

Une seule rotation par report peut simuler un décalage logique ou arithmétique d’une position en configurant l’indicateur de report au préalable. Par exemple, si l’indicateur de report contient 0, alors x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE est un décalage logique vers la droite, et si l’indicateur de report contient une copie du bit de signe, alors x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE est un décalage arithmétique vers la droite. Pour cette raison, certains microcontrôleurs tels que les PICS bas de gamme ont juste une rotation et une rotation à travers carry, et ne se soucient pas des instructions de décalage arithmétique ou logique.

La rotation par report est particulièrement utile lors de l’exécution de décalages sur des nombres plus grands que la taille de mot native du processeur, car si un grand nombre est stocké dans deux registres, le bit décalé d’une extrémité du premier registre doit entrer à l’autre extrémité du second. Avec rotate-through-carry, ce bit est « enregistré » dans l’indicateur de report pendant le premier quart de travail, prêt à être déplacé pendant le deuxième quart de travail sans préparation supplémentaire.

En langues de haut niveaumodifier

C-familyEdit

Dans les langages de la famille C, les opérateurs de décalage logiques sont « << » pour le décalage à gauche et « >> » pour le décalage à droite. Le nombre de places à déplacer est donné comme deuxième argument à l’opérateur. Par exemple,

x = y << 2;

attribue à x le résultat du déplacement de y vers la gauche de deux bits, ce qui équivaut à une multiplication par quatre.Les changements

peuvent entraîner un comportement défini par l’implémentation ou un comportement indéfini, il faut donc faire attention lors de leur utilisation. Le résultat d’un décalage d’un nombre de bits supérieur ou égal à la taille du mot est un comportement indéfini en C et C ++. Le décalage vers la droite d’une valeur négative est défini par l’implémentation et n’est pas recommandé par les bonnes pratiques de codage; le résultat du décalage vers la gauche d’une valeur signée n’est pas défini si le résultat ne peut pas être représenté dans le type de résultat.

En C #, le décalage vers la droite est un décalage arithmétique lorsque le premier opérande est un int ou long. Si le premier opérande est de type uint ou ulong, le décalage vers la droite est un décalage logique.

Décalages circulairesmodifier

La famille de langages C n’a pas d’opérateur de rotation, mais on peut en synthétiser un à partir des opérateurs de décalage. Il faut veiller à ce que l’instruction soit bien formée pour éviter les attaques de comportement et de synchronisation non définies dans les logiciels avec des exigences de sécurité. Par exemple, une implémentation naïve qui fait pivoter à gauche une valeur non signée de 32 bits x par n positions est simplement:

uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (32 - n));

Cependant, un décalage de 0 bits entraîne un comportement indéfini dans l’expression de droite (x >> (32 - n)) car 32 - 0 vaut 32 et 32 est en dehors de la plage incluse. Un deuxième essai pourrait entraîner:

uint32_t x = ..., n = ...;uint32_t y = n ? (x << n) | (x >> (32 - n)) : x;

où la quantité de décalage est testée pour s’assurer qu’elle n’introduit pas de comportement indéfini. Cependant, la branche ajoute un chemin de code supplémentaire et offre une opportunité d’analyse de synchronisation et d’attaque, ce qui n’est souvent pas acceptable dans les logiciels à haute intégrité. De plus, le code compile plusieurs instructions machine, ce qui est souvent moins efficace que l’instruction native du processeur.

Pour éviter le comportement indéfini et les branches sous GCC et Clang, les éléments suivants sont recommandés. Le modèle est reconnu par de nombreux compilateurs et le compilateur émettra une seule instruction de rotation:

uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (-n & 31));

Il existe également des intrinsèques spécifiques au compilateur implémentant des décalages circulaires, comme _rotl8, _rotl16, _rotr8, _rotr16 dans Microsoft Visual C++. Clang fournit des intrinsèques de rotation pour la compatibilité Microsoft qui souffre des problèmes ci-dessus. GCC n’offre pas d’éléments intrinsèques rotatifs. Intel fournit également des intrinsèques x86.

JavaEdit

En Java, tous les types entiers sont signés, de sorte que les opérateurs « << » et « >> » effectuent des décalages arithmétiques. Java ajoute l’opérateur « >>> » pour effectuer des décalages logiques à droite, mais comme les opérations de décalage logique et arithmétique à gauche sont identiques pour un entier signé, il n’y a pas d’opérateur « <<< » en Java.

Plus de détails sur les opérateurs Java shift:

• Les opérateurs << (décalage vers la gauche), >> (décalage vers la droite signé) et >>> (décalage vers la droite non signé) sont appelés opérateurs de décalage.
• Le type de l’expression de décalage est le type promu de l’opérande de gauche. Par exemple, aByte >>> 2 est équivalent à ((int)aByte) >>> 2.
• Si le type promu de l’opérande de gauche est int, seuls les cinq bits d’ordre le plus bas de l’opérande de droite sont utilisés comme distance de décalage. C’est comme si l’opérande de droite était soumis à un opérateur ET logique au niveau du bit & avec la valeur de masque 0x1f (0b11111). La distance de décalage effectivement utilisée est donc toujours comprise entre 0 et 31 inclusivement.
• Si le type promu de l’opérande de gauche est long, seuls les six bits d’ordre le plus bas de l’opérande de droite sont utilisés comme distance de décalage. C’est comme si l’opérande de droite était soumis à un opérateur ET logique au niveau du bit & avec la valeur de masque 0x3f (0b111111). La distance de décalage effectivement utilisée est donc toujours comprise entre 0 et 63 inclus.
• La valeur de n > > > s est n positions de bits décalées à droite avec extension nulle.
• Dans les opérations de bits et de décalage, le type byte est implicitement converti en int. Si la valeur de l’octet est négative, le bit le plus élevé est un, alors ceux sont utilisés pour remplir les octets supplémentaires dans l’int. Donc octet b1 =-5; int i = b1/0x0200; entraînera i == -5 .

JavaScriptEdit

JavaScript utilise des opérations bit à bit pour évaluer chacune de deux unités ou plus placées à 1 ou 0.

PascalEdit

En Pascal, ainsi que dans tous ses dialectes (tels que le Pascal Objet et le Pascal Standard), les opérateurs logiques de décalage à gauche et à droite sont « shl » et « shr« , respectivement. Même pour les entiers signés, shr se comporte comme un décalage logique et ne copie pas le bit de signe. Le nombre de places à déplacer est donné comme deuxième argument. Par exemple, ce qui suit attribue à x le résultat du déplacement de y vers la gauche de deux bits:

x := y shl 2;