Opération par bit

Les décalages de bits sont parfois considérés comme des opérations par 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 d’un processeur d’ordinateur ont une largeur fixe, de sorte que certains bits seront  » décalés hors  » du registre à une extrémité, tandis que le même nombre de bits sont  » décalés vers l’intérieur  » depuis 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 vers l’intérieur.

Adressage par bit

Si la largeur du registre (fréquemment 32 ou même 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 frontière aux deux extrémités du registre, les opérations de décalage arithmétiques et logiques se comportent de la même manière, et un décalage de 8 positions binaires transporte le schéma binaire d’une position d’octet de la manière suivante :

Décalage arithmétiqueEdit

Décalage arithmétique gauche

.

Décalage arithmétique droit

Dans un décalage arithmétique, les bits qui sont décalés de chaque côté sont rejetés. Dans un décalage arithmétique gauche, les zéros sont décalés vers la droite ; dans un décalage arithmétique droit, le bit de signe (le MSB en complément à deux) est décalé vers la gauche, préservant ainsi le signe de l’opérande.

Cet exemple utilise un registre de 8 bits, interprété en complément à 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écalé 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. Les décalages multiples sont parfois raccourcis en un seul décalage par 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 à une multiplication par 2n (à condition que la valeur ne déborde pas), tandis qu’un décalage arithmétique droit par n d’une valeur de complément à deux équivaut à une division par 2n et à un arrondi vers l’infini négatif. Si le nombre binaire est traité comme un complément à un, alors la même opération de décalage à droite entraîne une division par 2n et un arrondi vers zéro.

Décalage logique

.

. Décalage logique à gauche

Décalage logique à droite .

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

Cependant, comme le décalage logique à droite insère des bits de valeur 0 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 arithmétique à droite est idéal pour les nombres binaires à complément à deux signés.

Décalage circulaireModification

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

RotationEdit

.

. Décalage ou rotation circulaire gauche

Décalage circulaire à droite ou rotation

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 lors d’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.

Rotation par carryEdit

.

Rotation gauche par le portage

Rotation droite à travers un carry

La rotation par la retenue est une variante de l’opération de rotation, où le bit qui est décalé en entrée (à l’une ou l’autre extrémité) est l’ancienne valeur du drapeau de report, et le bit qui est décalé en sortie (à l’autre extrémité) devient la nouvelle valeur du drapeau de report.

Une seule rotation par carry peut simuler un décalage logique ou arithmétique d’une position en paramétrant le drapeau de carry au préalable. Par exemple, si le drapeau de report contient 0, alors x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE est un décalage logique à droite, et si le drapeau de report contient une copie du bit de signe, alors x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE est un décalage arithmétique à droite. C’est pour cette raison que certains microcontrôleurs, comme les PIC bas de gamme, n’ont que les instructions rotate et rotate through carry, et ne s’embarrassent pas d’instructions de décalage arithmétique ou logique.

La rotate through carry est particulièrement utile pour effectuer des décalages sur des nombres plus grands que la taille native du mot du processeur, car si un grand nombre est stocké dans deux registres, le bit décalé à une extrémité du premier registre doit arriver à l’autre extrémité du second. Avec le rotate-through-carry, ce bit est « sauvegardé » dans le drapeau de report pendant le premier décalage, prêt à être décalé lors du second décalage sans préparation supplémentaire.

Dans les langages de haut niveauEdit

C-familyEdit

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

x = y << 2;

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

Les décalages peuvent entraîner un comportement défini par l’implémentation ou un comportement non défini, il faut donc faire attention lorsqu’on les utilise. Le résultat du décalage par un nombre de bits supérieur ou égal à la taille du mot est un comportement non défini en C et C++. Le décalage à 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 à gauche d’une valeur signée est indéfini si le résultat ne peut pas être représenté dans le type de résultat.

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

Décalages circulairesModification

La famille des langages C ne possède 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 un comportement indéfini et des attaques de synchronisation dans les logiciels ayant des exigences de sécurité. Par exemple, une implémentation naïve qui fait tourner à 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 est 32, et 32 est en dehors de l’intervalle inclus. Un deuxième essai pourrait aboutir à :

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

où le montant du décalage est testé pour s’assurer qu’il n’introduit pas de comportement non défini. Cependant, la branche ajoute un chemin de code supplémentaire et présente une opportunité d’analyse et d’attaque de timing, ce qui n’est souvent pas acceptable dans un logiciel à haute intégrité. En outre, le code se compile en 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, il est recommandé de procéder comme suit. 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 quelques intrinsèques de rotation pour la compatibilité Microsoft qui souffrent des problèmes ci-dessus. GCC ne propose pas de rotate intrinsics. Intel fournit également des intrinsèques x86.

JavaEdit

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

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

• Les opérateurs << (décalage à gauche), >> (décalage à droite signé) et >>> (décalage à droite non signé) sont appelés les 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 de poids faible 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 logique ET bit à bit & avec la valeur de masque 0x1f (0b11111). La distance de décalage réellement utilisée est donc toujours comprise entre 0 et 31, inclus.
• Si le type promu de l’opérande de gauche est long, alors seuls les six bits de poids faible 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 logique ET bit à 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 binaires décalées à droite de s positions binaires avec extension nulle.
• Dans les opérations de bit 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 les uns sont utilisés pour remplir les octets supplémentaires dans l’int. Ainsi, byte b1 = -5 ; int i = b1 | 0x0200; résultera en i == -5.

JavaScriptEdit

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

PascalEdit

En Pascal, ainsi que dans tous ses dialectes (comme Object Pascal et Standard Pascal), les opérateurs logiques de décalage à gauche et à droite sont respectivement « shl » et « shr« . 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écaler est donné comme deuxième argument. Par exemple, ce qui suit attribue à x le résultat du décalage de y vers la gauche de deux bits:

x := y shl 2;

.