Que sont les opérateurs de décalage binaire (bit-shift) et comment fonctionnent-ils?
https://stackoverflow.com/questions/141525
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
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, c’est, au niveau fondamental, que fait le transfert de bits (<<, >>, >>>), quels problèmes peut-il aider à résoudre et quels pièges se cachent autour de la courbe? En d’autres termes, un guide du débutant absolu sur le transfert de bits dans toute sa qualité.
La solution
Les opérateurs à décalage de bits font exactement ce que leur nom implique. Ils décalent les bits. Voici une brève (ou pas si brève) introduction aux différents opérateurs de quart.
Les opérateurs
-
>>est l'opérateur de décalage à droite arithmétique (ou signé). -
>>>est l'opérateur de décalage à droite logique (ou non signé). -
<<est l'opérateur de décalage à gauche et répond aux besoins des décalages 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, appliquer les opérateurs de décalage à tout type de données inférieur à <<< redimensionne automatiquement l'opérande en tant que 6 << 1.
Notez que 6 * 2 n'est pas un opérateur, car il serait redondant. Notez également que C et C ++ ne font pas la distinction entre les opérateurs de décalage de droite. Ils fournissent uniquement l'opérateur 6 << 3 et le comportement de décalage à 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 nombre 6 stocké en tant que 32 bits 6 * 8 serait:
00000000 00000000 00000000 00000110
Si vous déplacez ce motif binaire vers la gauche (3,758,096,384 << 1), vous obtiendrez le nombre 12:
00000000 00000000 00000000 00001100
Comme vous pouvez le constater, les chiffres se sont décalés d'une position vers la gauche et le dernier chiffre à droite est rempli d'un zéro. Vous pouvez également noter que le déplacement à gauche est équivalent à la multiplication par des puissances de 2. Donc, 12 >>> 1 équivaut à 939,524,102 << 4, et (939,524,102 << 4) >>> 4 à <=>. Un compilateur optimisant remplacera les multiplications par des décalages lorsque cela est possible.
Décalage non circulaire
Veuillez noter que ce ne sont pas des décalages circulaires. Décaler cette valeur vers la gauche d'une position (<=>):
11100000 00000000 00000000 00000000
résulte en 3 221 225 472:
11000000 00000000 00000000 00000000
Le chiffre qui est décalé & "à la fin &"; est perdu. Cela ne s’enroule pas.
Décalage à droite logique (> > >)
Un changement logique à droite est l'inverse du changement à gauche. Plutôt que de déplacer les bits vers la gauche, ils se déplacent simplement vers la droite. Par exemple, en modifiant le numéro 12:
00111000 00000000 00000000 00000110
à droite d'une position (<=>) récupérera notre 6:
10000000 00000000 00000000 01100000
Nous voyons donc que le déplacement vers la droite équivaut à une division par deux.
Les bits perdus ont disparu
Cependant, une équipe ne peut pas récupérer & "perdu &"; morceaux. Par exemple, si nous décalons ce motif:
00001000 00000000 00000000 00000110
à gauche 4 positions (<=>), nous obtenons 2 147 483 744:
11111000 00000000 00000000 00000110
puis en arrière (<=>), nous obtenons 134 217 734:
<*>Nous ne pouvons pas récupérer notre valeur initiale une fois que nous avons perdu des bits.
Décalage à droite arithmétique (> >)
Le décalage arithmétique à droite est identique au décalage logique à droite, sauf qu'au lieu de remplir avec zéro, il remplit avec le bit le plus significatif. En effet, le bit le plus significatif est le bit signe , ou le bit qui distingue les nombres positifs et négatifs. En remplissant avec le bit le plus significatif, le décalage arithmétique à droite préserve les signes.
Par exemple, si nous interprétons ce modèle de bits comme un nombre négatif:
<*>nous avons le numéro -2 147 483 552. Déplacer cette position vers la droite 4 positions avec le décalage arithmétique (-2,147,483,552 & Gt; & Gt; 4) nous donnerait:
<*>ou le nombre -134,217,722.
Nous voyons donc que nous avons conservé le signe de nos nombres négatifs en utilisant le décalage arithmétique à droite, plutôt que le décalage logique à droite. Et encore une fois, nous voyons que nous procédons à une division par deux.
Autres conseils
Disons que nous avons un seul octet:
0110110
En appliquant un seul décalage binaire gauche, nous obtenons:
1101100
Le zéro le plus à gauche a été décalé de l'octet et un nouveau zéro a été ajouté à l'extrémité droite de l'octet.
Les bits ne basculent pas; ils sont jetés. Cela signifie que si vous quittez le poste 1101100 puis que vous le déplacez à droite, vous n'obtiendrez pas le même résultat.
Décaler la gauche de N équivaut à multiplier par 2 N .
Déplacer à droite de N est (si vous utilisez le complément de uns ) est le équivalent de diviser par 2 N et d’arrondir à 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 était disposée séquentiellement par pixel. Pour calculer l’emplacement d’un pixel, utilisez les calculs suivants:
memoryOffset = (row * 320) + column
Maintenant, à cette époque, la vitesse était critique, nous utilisions donc des transferts de bits pour effectuer cette opération.
Cependant, 320 n’est pas une puissance de deux, donc, pour contourner ce problème, nous devons déterminer quelle est une puissance de deux qui s’additionne fait 320:
(row * 320) = (row * 256) + (row * 64)
Nous pouvons maintenant convertir cela en équipes à 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 depuis toujours que j'ai assemblé note: corrigé quelques erreurs et ajouté un exemple 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, quel que soit le processeur utilisé par le passé
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 processeur ancien.
Oui, nous travaillerons si dur pour économiser 16 cycles de processeur.
En mode 32 ou 64 bits, les deux versions deviennent beaucoup plus courtes et rapides. Processeurs d'exécution modernes tels que Intel Skylake (voir http://agner.org/optimize/ ). multiplier le matériel très rapidement (faible temps de latence et débit élevé), le gain est donc beaucoup plus petit. La famille de bulldozers AMD est un peu plus lente, en particulier pour la multiplication 64 bits. Sur les processeurs Intel et AMD Ryzen, deux décalages correspondent à une latence légèrement inférieure, mais plus d'instructions qu'une multiplication (ce qui peut entraîner 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.
Les compilateurs le feront pour vous: voyez comment gcc, clang et MSVC utilisent tous shift et lea pour optimiser return 320*row + col; .
La chose la plus intéressante à noter ici est que x86 a commeinstruction hift-and-add (LEA) pouvant effectuer de petits décalages à gauche et ajouter en même temps, avec les performances comme et add. ARM est encore plus puissant: un opérande de n'importe quelle instruction peut être déplacé à gauche ou à droite gratuitement. Donc, le redimensionnement par une constante de compilation qui est connue pour être une puissance de 2 peut être encore plus efficace qu'une multiplication.
Bien, à l’époque des temps modernes, il serait plus utile d’utiliser le décalage de bits 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 8 bits, mais dans la pratique, ne le faites pas toujours.
Les opérations sur les bits, y compris le décalage des bits, sont fondamentales pour la programmation matérielle de bas niveau ou 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-mots, divisés en champs de bits alignés non-octet, qui contiennent diverses valeurs intéressantes. L'accès à ces champs de bits pour la lecture / écriture est l'utilisation la plus courante.
Un exemple réel simple en 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, procédez comme suit:
#define GREEN_MASK 0x7E0
#define GREEN_OFFSET 5
// Read green
uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;
Explication
Pour obtenir la valeur du vert UNIQUEMENT, qui commence au décalage 5 et se termine au 10 (c'est-à-dire une longueur de 6 bits), vous devez utiliser un masque (bit) qui, lorsqu'il est appliqué à la totalité du pixel de 16 bits , ne donnera que 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 (& amp;).
uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;
Après avoir appliqué le masque, vous obtiendrez un nombre de 16 bits qui n’est en réalité qu’un nombre de 11 bits puisque son poids le plus significatif est situé dans le onzième bit. Le vert ne fait en réalité que 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 décalage (#define GREEN_OFFSET 5).
Il est également courant d'utiliser des décalages de bits pour une multiplication et une division rapides par des puissances de 2:
i <<= x; // i *= 2^x;
i >>= y; // i /= 2^y;
Bit Masking & amp; Déplacement
Le décalage des 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 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 en masquant et décalant .
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 & garantit 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écalant tous ces bits vers la droite de 16 places (décalage logique à droite) .
green_value = masked_color >>> 16
Et voil & # 225 ;, nous avons le nombre 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 tels que jpg, png, ....
L’un des piètres problèmes est que ce qui suit dépend de la mise en oeuvre (selon la norme ANSI):
char x = -1;
x >> 1;
x peut maintenant être 127 (01111111) ou encore -1 (11111111).
En pratique, il s’agit généralement de ce dernier.
Je n’écris que des conseils et des astuces que je pourrais trouver utiles lors des tests / examens.
-
n = n*2:n = n<<1 -
n = n/2:n = n>>1 - Vérifier si n est la puissance de 2 (1,2,4,8, ...): vérifier
!(n & (n-1)) - Obtention du x e bit de
n:n |= (1 << x) - Vérifier si x est pair ou impair:
x&1 == 0(pair) - Activez le n e bit de x:
x ^ (1<<n)
Notez que dans l'implémentation Java, le nombre de bits à déplacer est modifié en fonction de la taille de la source.
Par exemple:
(long) 4 >> 65
est égal à 2. Vous pouvez vous attendre à ce que le décalage des bits vers la droite 65 fois remette tout à zéro, mais cela équivaut en réalité à:
(long) 4 >> (65 % 64)
Ceci est vrai pour < < ;, > > ;, et > > > ;. Je ne l'ai pas essayé dans d'autres langues.
Quelques opérations / manipulations de bits utiles en Python. Réponses @Ravi Prakash mises en œuvre en python.
# basic bit operations
# int to bin
print(bin(10))
# bin to int
print(int('1010',2))
# multiplying x with 2 .... x**2== x << 1
print(200<<1)
# dividing x with 2 .... x /2 == x >> 1
print(200>>1)
# modulo x with 2 .... x%2 == x&1
if 20&1==0:
print("20 is a even number")
# check if n is power of 2 : check !(n & (n-1))
print(not(33 &(33-1)))
# getting xth bit of n : (n>>x)&1
print((10>>2)&1) # bin of 10==1010 and 2nd bit is 0
# toggle nth bit of x : x^(1<<n)
# take bin(10)==1010 and toggling 2nd bit in bin(10) we get 1110 === bin(14)
print(10^(1<<2))
Sachez que seule la version 32 bits de PHP est disponible sur la plate-forme Windows.
Ensuite, si vous déplacez par exemple < < ou > > plus de 31 bits, les résultats sont inattendus. Habituellement, le numéro original au lieu de zéros sera renvoyé, ce qui peut être un bug vraiment compliqué.
Bien sûr, si vous utilisez une version 64 bits de PHP (unix), vous devez éviter les décalages supérieurs à 63 bits. Cependant, par exemple, MySQL utilise le BIGINT 64 bits, il ne devrait donc pas y avoir de problèmes de compatibilité.
UPDATE: À partir de PHP7 Windows, les versions de PHP sont enfin capables d'utiliser des entiers complets de 64 bits: La taille d'un entier dépend de la plate-forme, bien qu'une valeur maximale d'environ deux milliards soit la valeur habituelle (32 bits signés). Les plates-formes 64 bits ont généralement une valeur maximale d'environ 9E18, sauf sur Windows antérieure à PHP 7, où elle était toujours en 32 bits.
