Question Qu'est-ce que les opérateurs de décalage bit à bit (bit-shift) et comment fonctionnent-ils?


J'ai essayé d'apprendre le C pendant mon temps libre, et d'autres langages (C #, Java, etc.) ont le même concept (et souvent les mêmes opérateurs) ...

Ce que je me demande, à un niveau de base, ce que font les changements de bits (<<, >>, >>>), quels problèmes peuvent-ils aider à résoudre, et qu'est-ce qui se cache autour du virage? En d'autres termes, un guide absolu du débutant pour changer le bit dans toute sa bonté.


1189
2017-09-26 19:47


origine


Réponses:


Les opérateurs bit-shift font exactement ce que leur nom implique. Ils changent des bits. Voici une brève introduction (ou pas si brève) aux différents opérateurs de changement de vitesse.

Les opérateurs

  • >> est l'opérateur de décalage de droite arithmétique (ou signé).
  • >>> est l'opérateur de décalage de droite logique (ou non signé).
  • << est l'opérateur de décalage de gauche et répond aux besoins des changements logiques et arithmétiques.

Tous ces opérateurs peuvent être appliqués à des valeurs entières (int, long, peut-être short et byte ou char). Dans certaines langues, l'application des opérateurs de décalage à tout type de données inférieur à int redimensionne automatiquement l'opérande pour être un int.

Notez que <<< n'est pas un opérateur, car il serait redondant. Notez également que C et C ++ ne distinguent pas les opérateurs de décalage de droite. Ils fournissent seulement le >> opérateur, et le comportement de décalage vers la droite est défini par l'implémentation pour les types signés.


Décalage gauche (<<)

Les entiers sont stockés, en mémoire, sous la forme d'une série de bits. Par exemple, le numéro 6 stocké en tant que 32 bits int serait:

00000000 00000000 00000000 00000110

Déplacement de ce motif de bits vers la gauche une position (6 << 1) se traduirait par le nombre 12:

00000000 00000000 00000000 00001100

Comme vous pouvez le voir, les chiffres ont été décalés vers la gauche d'une position, et le dernier chiffre à droite est rempli d'un zéro. Vous pourriez également noter que le déplacement à gauche est équivalent à la multiplication par des puissances de 2. Donc 6 << 1 est équivalent à 6 * 2, et 6 << 3 est équivalent à 6 * 8. Un bon compilateur d'optimisation remplacera les multiplications par des changements si possible.

Déplacement non circulaire

S'il vous plaît noter que ceux-ci sont ne pas quarts de travail circulaires. Déplacer cette valeur vers la gauche d'une position (3,758,096,384 << 1):

11100000 00000000 00000000 00000000

résultats en 3.221.225.472:

11000000 00000000 00000000 00000000

Le chiffre qui est décalé "hors de la fin" est perdu. Ça ne s'enroule pas.


Décalage droit logique (>>>)

Un décalage droit logique est l'inverse du quart gauche. Plutôt que de déplacer des bits vers la gauche, ils se déplacent simplement vers la droite. Par exemple, en déplaçant le numéro 12:

00000000 00000000 00000000 00001100

à droite par une position (12 >>> 1) récupèrera notre 6 original:

00000000 00000000 00000000 00000110

Nous voyons donc que le déplacement vers la droite équivaut à une division par des puissances de 2.

Les bits perdus sont partis

Cependant, un changement ne peut pas récupérer des bits "perdus". Par exemple, si nous changeons ce motif:

00111000 00000000 00000000 00000110

à gauche 4 positions (939,524,102 << 4), nous obtenons 2 147 483 744:

10000000 00000000 00000000 01100000

puis en arrière ((939,524,102 << 4) >>> 4) nous obtenons 134.217.734:

00001000 00000000 00000000 00000110

Nous ne pouvons pas récupérer notre valeur d'origine une fois que nous avons perdu des bits.


Arithmétique droite (>>)

Le décalage arithmétique à droite est exactement comme le décalage logique à droite, sauf que, au lieu de remplir avec zéro, il se bloque avec le bit le plus significatif. C'est parce que le bit le plus significatif est le signe bit, ou le bit qui distingue les nombres positifs et négatifs. En capitonnant avec le bit le plus significatif, le décalage arithmétique de droite préserve le signe.

Par exemple, si nous interprétons ce modèle de bits comme un nombre négatif:

10000000 00000000 00000000 01100000

nous avons le numéro -2 147 483 552. Déplacer ceci vers les 4 positions droites avec le décalage arithmétique (-2,147,483,552 >> 4) nous donnerait:

11111000 00000000 00000000 00000110

ou le numéro -134,217,722.

Nous voyons donc que nous avons conservé le signe de nos nombres négatifs en utilisant le décalage arithmétique de droite, plutôt que le décalage droit logique. Et encore une fois, nous voyons que nous effectuons la division par des puissances de 2.


1508
2017-09-26 20:46



Disons que nous avons un seul octet:

0110110

L'application d'un seul bitshift gauche nous permet:

1101100

Le zéro le plus à gauche a été déplacé hors de l'octet et un nouveau zéro a été ajouté à l'extrémité droite de l'octet.

Les bits ne se renversent pas; ils sont jetés. Cela signifie que si vous quittez le poste 1101100 et que vous le déplacez à droite, vous n'obtiendrez pas le même résultat.

Déplacer à gauche par N équivaut à multiplier par 2N.

Passer à droite par N est (si vous utilisez le complément des uns) est l'équivalent de diviser par 2N et arrondi à zéro.

Bitshifting peut être utilisé pour une multiplication et une division incroyablement rapides, à condition que vous travailliez avec une puissance de 2. Presque toutes les routines graphiques de bas niveau utilisent le transfert de bits.

Par exemple, il y a bien longtemps, nous utilisions le mode 13h (320x200 256 couleurs) pour les jeux. En mode 13h, la mémoire vidéo a été disposée séquentiellement par pixel. Cela signifiait pour calculer l'emplacement pour un pixel, vous utiliseriez les maths suivantes:

memoryOffset = (row * 320) + column

Maintenant, à cette époque, la vitesse était critique, nous utiliserions donc des bitshifts pour faire cette opération.

Cependant, 320 n'est pas une puissance de deux, donc pour contourner cela, nous devons trouver ce qui est une puissance de deux qui, ajouté ensemble, fait 320:

(row * 320) = (row * 256) + (row * 64)

Maintenant, nous pouvons convertir cela en quarts de gauche:

(row * 320) = (row << 8) + (row << 6)

Pour un résultat final de:

memoryOffset = ((row << 8) + (row << 6)) + column

Maintenant, nous obtenons le même décalage qu'auparavant, sauf qu'au lieu d'une opération de multiplication coûteuse, nous utilisons les deux bitshifts ... en x86 ce serait quelque chose comme ça (note, ça fait longtemps que j'ai fait l'assemblage (NDLR: corrigé quelques erreurs et ajouté un exemple de 32 bits)):

mov ax, 320; 2 cycles
mul word [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
; di = [row]*320 + [column]

; 16-bit addressing mode limitations:
; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last mov

Total: 28 cycles sur n'importe quel CPU ancien avait ces timings.

Vrs

mov ax, [row]; 2 cycles
mov di, ax; 2
shl ax, 6;  2
shl di, 8;  2
add di, ax; 2    (320 = 256+64)
add di, [column]; 2
; di = [row]*(256+64) + [column]

12 cycles sur le même ancien processeur.

Oui, nous travaillons dur pour raser 16 cycles de CPU.

En mode 32 ou 64 bits, les deux versions sont beaucoup plus courtes et plus rapides. Des processeurs d'exécution modernes et hors d'usage comme Intel Skylake (voir http://agner.org/optimize/) ont une multiplication matérielle très rapide (faible latence et haut débit), le gain est donc beaucoup plus faible. AMD Bulldozer-famille est un peu plus lent, surtout pour multiplier 64 bits. Sur les processeurs Intel et AMD Ryzen, deux décalages sont une latence légèrement inférieure mais plus d'instructions qu'une multiplication (ce qui peut entraîner une baisse du débit):

imul edi, [row], 320    ; 3 cycle latency from [row] being ready
add  edi, [column]      ; 1 cycle latency (from [column] and edi being ready).
; edi = [row]*(256+64) + [column],  in 4 cycles from [row] being ready.

contre.

mov edi, [row]
shl edi, 6               ; row*64.   1 cycle latency
lea edi, [edi + edi*4]   ; row*(64 + 64*4).  1 cycle latency
add edi, [column]        ; 1 cycle latency from edi and [column] both being ready
; edi = [row]*(256+64) + [column],  in 3 cycles from [row] being ready.

Les compilateurs le feront pour vous: voyez comment gcc, clang et MSVC utilisent tous shift + lea lors de l'optimisation return 320*row + col;.

La chose la plus intéressante à noter ici est que x86 a une instruction shift-and-add (LEA) qui peut faire de petits décalages à gauche et ajouter en même temps, avec la performance en tant que et add instruction. ARM est encore plus puissant: un opérande de n'importe quelle instruction peut être déplacé vers la gauche ou vers la droite gratuitement. Ainsi, la mise à l'échelle par une constante de temps de compilation connue comme étant une puissance de 2 peut être encore plus efficace qu'une multiplication.


OK, de retour dans les temps modernes ... quelque chose de plus utile maintenant serait d'utiliser bitshifting pour stocker deux valeurs de 8 bits dans un entier de 16 bits. Par exemple, en C #:

// Byte1: 11110000
// Byte2: 00001111

Int16 value = ((byte)(Byte1 >> 8) | Byte2));

// value = 000011111110000;

En C ++, les compilateurs devraient le faire pour vous si vous utilisiez un struct avec deux membres de 8 bits, mais dans la pratique ne pas toujours.


169
2017-09-26 19:55



Les opérations sur les bits, y compris le décalage de bits, sont fondamentales pour le matériel de bas niveau ou la programmation intégrée. Si vous lisez une spécification pour un périphérique ou même certains formats de fichiers binaires, vous verrez des octets, des mots et des mots, divisés en champs de bits alignés non-octets, qui contiennent diverses valeurs d'intérêt. L'accès à ces champs de bits pour la lecture / écriture est l'utilisation la plus courante.

Un exemple réel simple dans la programmation graphique est qu'un pixel de 16 bits est représenté comme suit:

  bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1  | 0 |
      |       Blue        |         Green         |       Red          |

Pour obtenir la valeur verte, vous feriez ceci:

 #define GREEN_MASK  0x7E0
 #define GREEN_OFFSET  5

 // Read green
 uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

Explication

Pour obtenir la valeur de green ONLY, qui commence au offset 5 et se termine à 10 (c'est-à-dire 6 bits), vous devez utiliser un masque (bit) qui, appliqué à l'ensemble du pixel 16 bits, donnera seulement les bits qui nous intéressent.

#define GREEN_MASK  0x7E0

Le masque approprié est 0x7E0 qui en binaire est 0000011111100000 (qui est 2016 en décimal).

uint16_t green = (pixel & GREEN_MASK) ...;

Pour appliquer un masque, utilisez l'opérateur AND (&).

uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

Après avoir appliqué le masque, vous obtiendrez un nombre de 16 bits, ce qui est juste un nombre de 11 bits, puisque son MSB est dans le 11ème bit. Le vert est en fait seulement long de 6 bits, nous devons donc le réduire en utilisant un décalage de droite (11 - 6 = 5), d'où l'utilisation de 5 comme décalage (#define GREEN_OFFSET 5).

Il est également courant d'utiliser des changements de bits pour multiplier et diviser rapidement par des puissances de 2:

 i <<= x;  // i *= 2^x;
 i >>= y;  // i /= 2^y;

83
2017-09-26 22:22



Masquage des bits et décalage

Le décalage de bits est souvent utilisé dans la programmation graphique de bas niveau. Par exemple une valeur de couleur de pixel donnée codée dans un mot de 32 bits.

 Pixel-Color Value in Hex:    B9B9B900
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

Pour une meilleure compréhension, la même valeur binaire étiquetée avec quelles sections représente quelle partie de la couleur.

                                 Red     Green     Blue       Alpha
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

Disons par exemple que nous voulons obtenir la valeur verte de cette couleur de pixels. Nous pouvons facilement obtenir cette valeur par masquer et déplacement.

Notre masque:

                  Red      Green      Blue      Alpha
 color :        10111001  10111001  10111001  00000000
 green_mask  :  00000000  11111111  00000000  00000000

 masked_color = color & green_mask

 masked_color:  00000000  10111001  00000000  00000000

La logique & L'opérateur s'assure que seules les valeurs où le masque est 1 sont conservées. La dernière chose que nous devons faire maintenant est d'obtenir la valeur entière correcte en déplaçant tous ces bits vers la droite de 16 endroits (décalage droit logique).

 green_value = masked_color >>> 16

Et voila, nous avons l'entier représentant la quantité de vert dans la couleur des pixels:

 Pixels-Green Value in Hex:     000000B9
 Pixels-Green Value in Binary:  00000000 00000000 00000000 10111001 
 Pixels-Green Value in Decimal: 185

Ceci est souvent utilisé pour encoder ou décoder des formats d'image comme jpg,png,....


39
2018-03-31 10:49



Un gotcha est que ce qui suit dépend de l'implémentation (selon la norme ANSI):

char x = -1;
x >> 1;

x peut maintenant être 127 (01111111) ou encore -1 (11111111).

En pratique, c'est généralement le dernier.


26
2017-09-26 20:07



Notez que dans l'implémentation Java, le nombre de bits à décaler est modulé par la taille de la source.

Par exemple:

(long) 4 >> 65

est égal à 2. Vous pourriez vous attendre à déplacer les bits vers la droite 65 fois pour tout remettre à zéro, mais c'est en fait l'équivalent de:

(long) 4 >> (65 % 64)

Cela est vrai pour <<, >> et >>>. Je ne l'ai pas essayé dans d'autres langues.


8
2017-08-28 13:16



J'écris des trucs et astuces seulement, peut trouver utile dans les tests / examens.

  1. n = n*2: n = n<<1
  2. n = n/2: n = n>>1
  3. Vérifier si n est la puissance de 2 (1,2,4,8, ...): vérifier !(n & (n-1))
  4. Obtenir Xth un peu de n: n |= (1 << x)
  5. Vérifier si x est pair ou impair: x&1 == 0 (même)
  6. Basculer le nth peu de x: x ^ (1<<n)

6
2017-10-11 22:43



Sachez que seule la version 32 bits de PHP est disponible sur la plate-forme Windows.

Ensuite, si vous changez par exemple << ou >> plus de 31 bits, les résultats sont inattendus. Habituellement, le nombre original au lieu de zéros sera retourné, et cela peut être un bug très difficile.

Bien sûr, si vous utilisez une version 64 bits de PHP (unix), vous devriez éviter de déplacer plus de 63 bits. Cependant, par exemple, MySQL utilise le BIGINT 64 bits, il ne devrait donc pas y avoir de problèmes de compatibilité.

UPDATE: A partir de PHP7 Windows, les builds php sont enfin capables d'utiliser des entiers 64 bits: La taille d'un nombre entier dépend de la plateforme, bien qu'une valeur maximale d'environ deux milliards soit la valeur habituelle (c'est-à-dire 32 bits signés). Les plates-formes 64 bits ont généralement une valeur maximale d'environ 9E18, sauf sur Windows avant PHP 7, où il était toujours de 32 bits.


-2
2017-10-23 14:28