Qu'est-ce qu'un opérateur de changement de bit (bit-shift) et comment fonctionne-t-il?

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

ce que je me demande est, à un niveau de base, ce qui ne bit-shifting (<<, >>, >>>) do, quels problèmes cela peut-il aider à résoudre, et qu'est-ce que gotchas rôder autour du virage? En d'autres termes, un guide débutant absolu à bit shifting dans toute sa bonté.

1211
demandé sur Alexis King 2008-09-26 23:47:15
la source

8 ответов

les opérateurs de bit shifting font exactement ce que leur nom implique. Ils changent de morceaux. Voici une brève (ou moins brève) introduction aux différents opérateurs de postes.

Les Opérateurs

  • >> est l'opérateur de poste de droite arithmétique (ou signé).
  • >>> est l'opérateur de poste de droite logique (ou non signé).
  • << est l'opérateur de poste 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 , éventuellement short et byte ou char ). Dans certaines langues, l'application des opérateurs shift à tout type de données inférieur à int redimensionne automatiquement l'opérande pour qu'elle soit une int .

notez que <<< n'est pas un opérateur, car il serait redondant. Notez également que C et C++ ne font pas de distinction entre les opérateurs de quart de travail de droite. Ils ne fournissent que l'opérateur >> , et le comportement de déplacement à droite est une implémentation définie pour les types signés.


poste de gauche ( < < )

entiers sont stockés, en mémoire, comme une série de bits. Par exemple, le nombre 6 stocké comme un 32-bit int serait:

00000000 00000000 00000000 00000110

l'évolution de cette bit pattern à la gauche une position ( 6 << 1 ) donnerait le numéro 12:

00000000 00000000 00000000 00001100

Comme vous pouvez le voir, les chiffres ont décalé vers la gauche par une position, et le dernier chiffre à droite est rempli avec un zéro. Vous pouvez également noter que le déplacement à gauche est équivalent à une 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 des multiplications avec des équipes lorsque c'est possible.

Non-circulaire shifting

veuillez noter qu'il s'agit de et non de . Déplacement de cette valeur vers la gauche d'une position ( 3,758,096,384 << 1 ):

11100000 00000000 00000000 00000000

résultats dans 3,221,225,472:

11000000 00000000 00000000 00000000

Le chiffre qui obtient décalé "à la fin" est perdu. Il n'est pas autour.


Logique de décalage à droite (>>>)

un décalage logique vers la droite est l'inverse du décalage vers la 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 nombre 12:

00000000 00000000 00000000 00001100

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

00000000 00000000 00000000 00000110

ainsi nous voyons que se déplacer vers la droite est équivalent à la division par des pouvoirs de 2.

Perdu bits sont allés

cependant, un décalage ne peut pas récupérer les bits "perdus". Par exemple, si nous modifions ce modèle:

00111000 00000000 00000000 00000110

à gauche 4 positions ( 939,524,102 << 4 ), nous obtenons 2.147.483.744:

10000000 00000000 00000000 01100000

et puis en se déplaçant 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 originale une fois que nous avons perdu des bits.


déplacement arithmétique à droite ( > > )

le décalage arithmétique à droite est exactement comme le décalage logique à droite, sauf qu'au lieu de rembourrer avec zéro, il rembourre 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 remplaçant par le bit le plus significatif, le décalage arithmétique à droite préserve les signes.

par exemple, si nous interprétons ce patron de bits comme un nombre négatif:

10000000 00000000 00000000 01100000

nous avons le nombre -2,147,483,552. Le déplacement de cette position vers les 4 positions de droite avec le décalage arithmétique (-2.147.483.552 >> 4) nous donnerait:

11111000 00000000 00000000 00000110

ou le nombre -134,217,722.

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

1529
répondu Derek Park 2017-06-07 10:24:54
la source

disons que nous avons un seul octet:

0110110

L'application d'un bitshift gauche simple nous obtient:

1101100

La plus à gauche du zéro 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 roulent pas; ils sont jetés. Cela signifie que si vous maj gauche 1101100, puis à droite passer, vous n'obtiendrez pas le même résultat.

Changer à gauche par N équivaut à multiplier par 2 N .

"1519150920 un" Déplacement de la droite de N est (si vous utilisez un " complément ) est l'équivalent de la division par 2 N et arrondi à zéro.

Bitshifting peut être utilisé pour la multiplication et la division insanely rapide, à condition que vous travaillez avec une puissance de 2. Presque toutes les routines graphiques de bas niveau utilisent bitshifting.

par exemple, il y a longtemps, nous avons utilisé le mode 13h (320x200 256 couleurs) pour les jeux. En Mode 13h, la mémoire vidéo est présentée séquentiellement par pixel. Cela signifiait pour calculer l'emplacement pour un pixel, vous utiliseriez les mathématiques suivantes:

memoryOffset = (row * 320) + column

maintenant, à cette époque, la vitesse était critique, donc nous utilisions bitshifts pour faire cette opération.

cependant, 320 n'est pas un pouvoir de deux, donc pour contourner cela, nous devons découvrez ce qu'est une puissance de deux qui additionné fait 320:

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

maintenant nous pouvons transformer cela en postes 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 offset qu'avant, sauf qu'au lieu d'une opération de multiplication onéreuse, nous utilisons les deux bitshifts...EN x86 ce serait quelque chose comme ça (note, ça fait une éternité que je n'ai pas fait d'assemblage) (note de l'éditeur: corrigé un quelques erreurs et ajout d'un 32-bit exemple)):

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 ancien CPU avait ces chronométrages.

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 CPU.

Oui, nous travaillerions dur pour raser 16 cycles CPU.

en mode 32 ou 64 bits, les deux versions sont beaucoup plus courtes et plus rapides. Des processeurs modernes d'exécution hors-ordre comme Intel Skylake (voir http://agner.org/optimize / ) ont très rapide Matériel multiplier (faible latence et haut débit), de sorte que le gain est beaucoup plus faible. AMD Bulldozer-famille est un peu plus lent, surtout pour 64-bit multiplier. Sur les processeurs Intel, et AMD Ryzen, deux temps de latence sont légèrement plus bas, mais plus d'instructions qu'une multiplication (ce qui peut conduire à un débit plus faible):

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.

vs.

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.

compilateurs le feront pour vous: Voir comment gcc, clang, et MSVC tous utilisent 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 quarts de travail à gauche et ajouter en même temps, avec la performance et l'instruction add . Bras est encore plus puissant: un opérande de n'importe quelle instruction peut être décalé à gauche ou à droite gratuitement. Donc, à l'échelle par un la constante de temps de compilation qui est connue pour être 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, dans C#:

// Byte1: 11110000
// Byte2: 00001111

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

// value = 000011111110000;

en C++, Les compilateurs devraient le faire pour vous si vous avez utilisé un struct avec deux membres 8-bit, mais dans la pratique ne le font pas toujours.

173
répondu FlySwat 2017-06-09 07:56:39
la source

les opérations sur 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 dwords, divisés en bitfields Non-byte alignés, qui contiennent diverses valeurs d'intérêt. L'accès à ces champs de bits pour lire/écrire est l'usage le plus courant.

un exemple réel simple dans la programmation graphique est qu'un pixel 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 vert seulement, qui commence à l'offset 5 et se termine à 10 (i.e. 6-bits long), vous devez utiliser un masque (bit), qui lorsqu'il est appliqué contre le pixel 16-bits entier, 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, vous utilisez L'opérateur et (&).

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

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

aussi commun est en utilisant des déplacements de bits pour la multiplication rapide et la division par des puissances de 2:

 i <<= x;  // i *= 2^x;
 i >>= y;  // i /= 2^y;
86
répondu robottobor 2015-08-08 21:11:10
la source

Bit De Masquage Et Le Décalage 1519100920"

bit shifting 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 marquée avec quelles sections représente quelle partie de 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 masquage et décalage .

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

l'opérateur logique & assure que seules les valeurs où le masque est 1 sont conservées. La dernière chose que nous devons maintenant faire, est d'obtenir la valeur entière correcte en déplaçant tous ces bits à droite par 16 places (déplacement logique à droite) .

 green_value = masked_color >>> 16

et voilà, nous avons le 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

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

39
répondu Basti Funck 2015-12-28 02:25:24
la source

un gotcha est que la mise en œuvre dépend (selon la norme ANSI):

char x = -1;
x >> 1;

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

dans la pratique, c'est généralement ce dernier.

26
répondu AShelly 2008-09-27 04:56:51
la source

notez que dans L'implémentation Java, le nombre de bits à décaler est modifié par la taille de la source.

par exemple:

(long) 4 >> 65

égale 2. On pourrait s'attendre à ce que le déplacement des bits vers la droite 65 fois zéroterait tout, mais c'est en fait l'équivalent de:

(long) 4 >> (65 % 64)

ceci est vrai pour <<, >>, et >>>. Je n'ai pas essayé dans d'autres langues.

8
répondu Patrick Monkelban 2015-08-28 16:16:33
la source

je suis en train d'écrire 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. contrôle si n est une puissance de 2 (1,2,4,8,...): cochez !(n & (n-1))
  4. Arriver x th peu de n : n |= (1 << x)
  5. vérification si x est pair ou impair: x&1 == 0 (Pair)
  6. Bascule n th bits de x: x ^ (1<<n)
8
répondu Ravi Prakash 2018-06-10 21:17:22
la source

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

alors si par exemple vous décalez << ou >> de plus de 31 bits, les résultats sont imprévisibles. Habituellement le nombre original au lieu des zéros sera retourné, et cela peut être un bogue très délicat.

bien sûr, si vous utilisez la version 64 bits de PHP (unix), vous devez éviter de changer de plus de 63 bits. Cependant, par exemple, MySQL utilise le BIGINT 64-bit, ne devrait pas être un problème de compatibilité.

mise à jour: à partir de Windows PHP7, les constructions php sont enfin capables d'utiliser des entiers 64bit complets: la taille d'un entier dépend de la plate-forme, 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ù elle était toujours 32 bits.

-2
répondu lukyer 2017-09-26 23:42:49
la source