Fonctionnement au niveau du bit - Bitwise operation

En programmation informatique , une opération au niveau du bit opère sur une chaîne de bits , un tableau de bits ou un nombre binaire (considéré comme une chaîne de bits) au niveau de ses bits individuels . Il s'agit d'une action simple et rapide, de base aux opérations arithmétiques de niveau supérieur et directement prise en charge par le processeur . La plupart des opérations au niveau du bit sont présentées sous forme d'instructions à deux opérandes où le résultat remplace l'un des opérandes d'entrée.

Sur les processeurs simples à faible coût, les opérations au niveau du bit sont généralement sensiblement plus rapides que la division, plusieurs fois plus rapides que la multiplication et parfois nettement plus rapides que l'addition. Alors que les processeurs modernes effectuent généralement des additions et des multiplications aussi rapidement que les opérations au niveau du bit en raison de leurs pipelines d'instructions plus longs et d'autres choix de conception architecturale , les opérations au niveau du bit utilisent généralement moins d'énergie en raison de l'utilisation réduite des ressources.

Opérateurs au niveau du bit

Dans les explications ci-dessous, toute indication de la position d'un bit est comptée du côté droit (le moins significatif), en avançant vers la gauche. Par exemple, la valeur binaire 0001 (décimal 1) a des zéros à chaque position sauf la première (c'est-à-dire la plus à droite).

NE PAS

Le NOT au niveau du bit , ou complément , est une opération unaire qui effectue une négation logique sur chaque bit, formant le complément à un de la valeur binaire donnée. Les bits qui sont à 0 deviennent 1, et ceux qui sont à 1 deviennent 0. Par exemple :

NOT 0111  (decimal 7)
  = 1000  (decimal 8)
NOT 10101011  (decimal 171)
  = 01010100  (decimal 84)

Le complément au niveau du bit est égal au complément à deux de la valeur moins un. Si l'arithmétique du complément à deux est utilisée, alors NOT x = -x − 1.

Pour les entiers non signés , le complément au niveau du bit d'un nombre est le "reflet miroir" du nombre à mi-chemin de la plage de l'entier non signé. Par exemple, pour les entiers non signés de 8 bits, NOT x = 255 - x, qui peut être visualisé sur un graphique sous la forme d'une ligne descendante qui "inverse" efficacement une plage croissante de 0 à 255, à une plage décroissante de 255 à 0. Un exemple simple mais illustratif utilise consiste à inverser une image en niveaux de gris où chaque pixel est stocké sous la forme d'un entier non signé.

ET

ET au niveau du bit d' entiers de 4 bits

Un ET au niveau du bit est une opération binaire qui prend deux représentations binaires de longueur égale et effectue l' opération ET logique sur chaque paire de bits correspondants, ce qui équivaut à les multiplier. Ainsi, si les deux bits dans la position comparée sont 1, le bit dans la représentation binaire résultante est 1 (1 × 1 = 1); sinon, le résultat est 0 (1 × 0 = 0 et 0 × 0 = 0). Par exemple:

    0101 (decimal 5)
AND 0011 (decimal 3)
  = 0001 (decimal 1)

L'opération peut être utilisée pour déterminer si un bit particulier est défini (1) ou supprimé (0). Par exemple, étant donné un modèle binaire 0011 (décimal 3), pour déterminer si le deuxième bit est défini, nous utilisons un AND au niveau du bit avec un modèle binaire contenant 1 uniquement dans le deuxième bit :

    0011 (decimal 3)
AND 0010 (decimal 2)
  = 0010 (decimal 2)

Comme le résultat 0010 n'est pas nul, nous savons que le deuxième bit du modèle d'origine a été défini. C'est ce qu'on appelle souvent le masquage de bits . (Par analogie, l'utilisation de bandes de masquage , ou masques , des portions qui ne doivent pas être modifiées ou des portions qui ne présentent pas d'intérêt. Dans ce cas, les valeurs 0 masquent les bits qui ne présentent pas d'intérêt.)

L'ET au niveau du bit peut être utilisé pour effacer des bits sélectionnés (ou drapeaux ) d'un registre dans lequel chaque bit représente un état booléen individuel . Cette technique est un moyen efficace de stocker un certain nombre de valeurs booléennes en utilisant le moins de mémoire possible.

Par exemple, 0110 (décimal 6) peut être considéré comme un ensemble de quatre drapeaux, où les premier et quatrième drapeaux sont vides (0), et les deuxième et troisième drapeaux sont définis (1). Le troisième indicateur peut être effacé en utilisant un AND au niveau du bit avec le modèle qui a un zéro uniquement dans le troisième bit :

    0110 (decimal 6)
AND 1011 (decimal 11)
  = 0010 (decimal 2)

En raison de cette propriété, il devient facile de vérifier la parité d'un nombre binaire en vérifiant la valeur du bit de plus faible valeur. En utilisant l'exemple ci-dessus :

    0110 (decimal 6)
AND 0001 (decimal 1)
  = 0000 (decimal 0)

Parce que 6 ET 1 est zéro, 6 est divisible par deux et donc pair.

OU

OU au niveau du bit d'entiers de 4 bits

Un OU au niveau du bit est une opération binaire qui prend deux modèles de bits de longueur égale et effectue l' opération OU inclusif logique sur chaque paire de bits correspondants. Le résultat à chaque position est 0 si les deux bits sont à 0, sinon le résultat est 1. Par exemple :

   0101 (decimal 5)
OR 0011 (decimal 3)
 = 0111 (decimal 7)

Le OU au niveau du bit peut être utilisé pour mettre à 1 les bits sélectionnés du registre décrit ci-dessus. Par exemple, le quatrième bit de 0010 (décimal 2) peut être défini en effectuant un OU au niveau du bit avec le modèle avec uniquement le quatrième bit défini :

   0010 (decimal 2)
OR 1000 (decimal 8)
 = 1010 (decimal 10)

OU exclusif

XOR au niveau du bit d'entiers de 4 bits

Un XOR au niveau du bit est une opération binaire qui prend deux modèles de bits de longueur égale et effectue l' opération logique OU exclusif sur chaque paire de bits correspondants. Le résultat dans chaque position est 1 si un seul des bits est 1, mais sera 0 si les deux sont 0 ou les deux sont 1. Dans ce cas, nous effectuons la comparaison de deux bits, étant 1 si les deux bits sont différents, et 0 s'ils sont identiques. Par exemple:

    0101 (decimal 5)
XOR 0011 (decimal 3)
  = 0110 (decimal 6)

Le XOR bit à bit peut être utilisé pour inverser des bits sélectionnés dans un registre (également appelé bascule ou bascule). N'importe quel bit peut être basculé en le XOR avec 1. Par exemple, étant donné le modèle de bits 0010 (décimal 2), les deuxième et quatrième bits peuvent être basculés par un XOR au niveau du bit avec un modèle de bits contenant 1 dans les deuxième et quatrième positions :

    0010 (decimal 2)
XOR 1010 (decimal 10)
  = 1000 (decimal 8)

Cette technique peut être utilisée pour manipuler des motifs binaires représentant des ensembles d'états booléens.

Les programmeurs en langage assembleur et les compilateurs d' optimisation utilisent parfois XOR comme raccourci pour définir la valeur d'un registre à zéro. Effectuer XOR sur une valeur contre elle-même donne toujours zéro, et sur de nombreuses architectures, cette opération nécessite moins de cycles d'horloge et de mémoire que de charger une valeur zéro et de la sauvegarder dans le registre.

Si l'ensemble des chaînes de bits de longueur fixe n (c'est-à - dire des mots machine ) est considéré comme un espace vectoriel à n dimensions sur le champ , alors l'addition vectorielle correspond au XOR au niveau du bit.

Équivalents mathématiques

En supposant que , pour les entiers non négatifs, les opérations au niveau du bit peuvent être écrites comme suit :

Table de vérité pour tous les opérateurs logiques binaires

Il y a 16 fonctions de vérité possibles de deux variables binaires ; cela définit une table de vérité .

Voici les opérations équivalentes au niveau du bit de deux bits P et Q :

p q F 0 NI 1 Xq 2 p 3 4 q 5 OU EXCLUSIF 6 NAND 7 ET 8 XNOR 9 q 10 Si/alors 11 page 12 Alors/si 13 OU 14 T 15
1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Équivalents au niveau du bit
0 NON
(p OU q)
(PAS p)
ET q
PAS
p
p ET
(PAS q)
PAS
q
p XOR q NON
(p ET q)
p ET q NON
(p XOR q)
q (PAS p)
OU q
p p OU
(PAS q)
p OU q 1

Décalages de bits

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 d'un processeur d'ordinateur ont une largeur fixe, de sorte que certains bits seront "déplacés" du registre à une extrémité, tandis que le même nombre de bits est "déplacé" à 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 des bits

Si la largeur du registre (souvent 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 des octets vers les morceaux. Ainsi, les orientations "gauche" et "droite" sont tirées de l'écriture standard des nombres dans une notation de valeur de position , de sorte qu'un décalage vers la gauche augmente et un décalage vers la droite diminue la valeur du nombre si les chiffres de gauche sont lus en premier cette constitue une orientation big-endian . Sans tenir compte des effets de frontière 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 :

un décalage vers la gauche de 8 positions augmente l'adresse d'octet de 1
  • Commande petit-boutiste :
un décalage vers la droite de 8 positions diminue l'adresse d'octet de 1
un décalage vers la gauche de 8 positions diminue l'adresse d'octet de 1
  • Commande big-endian :
un décalage vers la droite de 8 positions augmente l'adresse d'octet de 1

Décalage arithmétique

Décalage arithmétique à gauche
Décalage arithmétique à droite

Dans un décalage arithmétique , les bits qui sont décalés de chaque extrémité sont rejetés. Dans un décalage arithmétique vers la gauche, les zéros sont décalés vers la droite ; dans un décalage arithmétique à droite, 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é comme un 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éplacé (peut-être dans le drapeau de retenue ), et un nouveau 1 a été copié dans la position la plus à gauche, en préservant le signe du nombre. Les équipes multiples sont parfois raccourcies à une seule équipe d'un certain nombre de chiffres. Par exemple:

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

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

Changement logique

Décalage logique à gauche
Décalage logique à droite

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

Cependant, comme le décalage logique à droite 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 arithmétique à droite est idéal pour les nombres binaires en complément à deux signés .

Décalage circulaire

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

Tourner

Décalage ou rotation circulaire à gauche
Décalage ou rotation circulaire à droite

Dans cette opération, parfois appelée rotation sans retenue , 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 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 à travers le transport

Rotation à gauche par portage
Rotation à droite par portage

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 du drapeau de retenue, et le bit qui est décalé (à l'autre extrémité) devient la nouvelle valeur de le drapeau de portage.

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

Rotate through carry est particulièrement utile lors de l'exécution de décalages sur des nombres plus grands que la taille de mot natif du processeur , car si un grand nombre est stocké dans deux registres, le bit qui est décalé d'une extrémité du premier registre doit entrer à l'autre extrémité de la deuxième. Avec la rotation de report, ce bit est « enregistré » dans le drapeau de report pendant le premier quart de travail, prêt à être transféré au cours du deuxième quart de travail sans aucune préparation supplémentaire.

Dans les langages de haut niveau

famille C

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 à l'opérateur. Par exemple,

x = y << 2;

attribue xle résultat du décalage yvers 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 non défini , il faut donc être prudent lors de leur utilisation. Le résultat du 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 la mise en œuvre 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 est indé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 entier ou un 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 circulaires

La famille des langages C n'a pas d' opérateur de rotation (bien que C++20 fournisse std::rotlet std::rotr), mais on peut en synthétiser un à partir des opérateurs de décalage. Des précautions doivent être prises pour s'assurer que la déclaration est bien formée pour éviter les attaques de comportement et de synchronisation indéfinies dans les logiciels avec des exigences de sécurité. Par exemple, une implémentation naïve qui laisse tourner une valeur non signée de 32 bits xpar npositions est simplement :

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

Cependant, un décalage par 0bits entraîne un comportement indéfini dans l'expression de droite (x >> (32 - n))car 32 - 0est 32, et 32est en dehors de la plage [0 - 31]inclusive. Un deuxième essai peut donner :

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 présente une opportunité d'analyse et d'attaque de synchronisation, ce qui n'est souvent pas acceptable dans un logiciel à haute intégrité. De plus, le code se compile en plusieurs instructions machine, ce qui est souvent moins efficace que l'instruction native du processeur.

Pour éviter le comportement et les branches indéfinis sous GCC et Clang, ce qui suit est recommandé. 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 éléments intrinsèques de rotation pour la compatibilité Microsoft qui souffre des problèmes ci-dessus. GCC n'offre pas d'intrinsèques de rotation. Intel fournit également x86 Intrinsics .

Java

En Java , tous les types 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 logiques et arithmétiques de décalage vers la gauche sont identiques pour les entiers signés, il n'y a 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 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équivaut à .((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 ET logique au niveau du 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, 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 ET logique au niveau du bit & avec la valeur de masque 0x3f (0b111111). La distance de décalage réellement utilisée est donc toujours comprise entre 0 et 63 inclus.
  • La valeur de n >>> sest n positions de bit s décalées vers la droite avec extension nulle.
  • Dans les opérations de bit et de décalage, le type byteest 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'entier. Ainsi se traduira .byte b1 = -5; int i = b1 | 0x0200;i == -5

JavaScript

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

Pascal

En Pascal, ainsi que dans tous ses dialectes (tels que Pascal Objet et Pascal Standard ), les opérateurs logiques de décalage vers la gauche et vers la droite sont " shl" et " shr", respectivement. Même pour les entiers signés, shrse 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;

Autre

Applications

Les opérations au niveau des bits sont nécessaires en particulier dans la programmation de bas niveau telle que les pilotes de périphérique, les graphiques de bas niveau, l'assemblage de paquets de protocole de communication et le décodage.

Bien que les machines aient souvent des instructions intégrées efficaces pour effectuer des opérations arithmétiques et logiques, toutes ces opérations peuvent être effectuées en combinant les opérateurs au niveau du bit et le test zéro de diverses manières. Par exemple, voici une implémentation de pseudocode de la multiplication égyptienne ancienne montrant comment multiplier deux entiers arbitraires aet b( asupérieur à b) en utilisant uniquement des décalages de bits et des additions :

c  0
while b  0
    if (b and 1)  0
        c  c + a
    left shift a by 1
    right shift b by 1
return c

Un autre exemple est une implémentation de pseudocode de l'addition, montrant comment calculer une somme de deux entiers aet en butilisant des opérateurs au niveau du bit et des tests de zéro :

while a  0
    c  b and a
    b  b xor a
    left shift c by 1
    a  c
return b

Algèbre de Boole

Parfois, il est utile de simplifier des expressions complexes constituées d'opérations au niveau du bit. Par exemple, lors de l'écriture de compilateurs. L'objectif d'un compilateur est de traduire un langage de programmation de haut niveau en un code machine le plus efficace possible. L'algèbre booléenne est utilisée pour simplifier des expressions complexes au niveau du bit.

ET

  • x & y = y & x
  • x & (y & z) = (x & y) & z
  • x & 0xFFFF = x
  • x & 0 = 0
  • x & x = x

OU

  • x | y = y | x
  • x | (y | z) = (x | y) | z
  • x | 0 = x
  • x | 0xFFFF = 0xFFFF
  • x | x = x

NE PAS

  • ~(~x) = x

OU exclusif

  • x ^ y = y ^ x
  • x ^ (y ^ z) = (x ^ y) ^ z
  • x ^ 0 = x
  • x ^ y ^ y = x
  • x ^ x = 0
  • x ^ 0xFFFF = ~x

De plus, XOR peut être composé en utilisant les 3 opérations de base (AND, OR, NOT)

  • a ^ b = (a | b) & (~a | ~b)
  • a ^ b = (a & ~b) | (~a & b)

Autres

  • x | (x & y) = x
  • x & (x | y) = x
  • ~(x | y) = ~x & ~y
  • ~(x & y) = ~x | ~y
  • x | (y & z) = (x | y) & (x | z)
  • x & (y | z) = (x & y) | (x & z)
  • x & (y ^ z) = (x & y) ^ (x & z)
  • x + y = (x ^ y) + ((x & y) << 1)
  • x - y = ~(~x + y)

Inverses et résolution d'équations

Il peut être difficile à résoudre pour les variables en algèbre booléenne, car contrairement à l'algèbre régulière, plusieurs opérations n'ont pas d'inverse. Les opérations sans inverses perdent certains des bits de données d'origine lorsqu'elles sont exécutées, et il n'est pas possible de récupérer ces informations manquantes.

  • A l'inverse
    • NE PAS
    • OU exclusif
    • Tourne à gauche
    • Tourner à droite
  • Pas d'inverse
    • ET
    • OU
    • Décaler à gauche
    • Décaler à droite

Ordre des opérations

Les opérations en haut de cette liste sont exécutées en premier. Voir l'article principal pour une liste plus complète.

  • ( )
  • ~ -
  • * / %
  • + -
  • << >>
  • &
  • ^
  • |

Voir également

Les références

Liens externes