Quels sont les opérateurs de décalage binary (bit-shift) et comment fonctionnent-ils?

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

Qu’est-ce que je me demande, au niveau fondamental, qu’est-ce que le bit-shifting (<>, >>>) fait, quels problèmes peut-il aider à résoudre, et ce qui se cache autour du virage? En d’autres termes, un guide de débutant absolu pour peu de changements dans ses qualités.

    Les opérateurs de transfert de bits font exactement ce que leur nom implique. Ils décalent des bits. Voici une brève introduction (ou pas si brève) aux différents opérateurs de quarts.

    Les opérateurs

    • >> est l’opérateur de calcul arithmétique (ou signé) à droite.
    • >>> est l’opérateur de décalage à droite logique (ou non signé).
    • << est l'opérateur 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 de décalage à tout type de données plus petit que int redimensionne automatiquement l'opérande pour devenir un int .

    Notez que <<< 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 droit. Ils fournissent uniquement l'opérateur >> , et le comportement de décalage à droite est défini 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é sous la forme d'un int 32 bits serait:

     00000000 00000000 00000000 00000110 

    En déplaçant ce modèle de bits vers la gauche ( 6 << 1 ), le nombre 12 serait le suivant:

     00000000 00000000 00000000 00001100 

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

    Déplacement non circulaire

    S'il vous plaît noter que ce ne sont pas des changements circulaires. En déplaçant cette valeur vers la gauche d'une position (3 3,758,096,384 << 1 ):

     11100000 00000000 00000000 00000000 

    donne 3221.225.472:

     11000000 00000000 00000000 00000000 

    Le chiffre qui est décalé "de la fin" est perdu. Il ne s'enveloppe pas.


    Décalage logique à droite (>>>)

    Un décalage logique 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, déplacer le nombre 12:

     00000000 00000000 00000000 00001100 

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

     00000000 00000000 00000000 00000110 

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

    Les morceaux perdus sont partis

    Cependant, un décalage ne peut pas récupérer les bits "perdus". Par exemple, si nous décalons ce motif:

     00111000 00000000 00000000 00000110 

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

     10000000 00000000 00000000 01100000 

    puis en reculant ( (939,524,102 << 4) >>> 4 ), nous obtenons 134,217,734:

     00001000 00000000 00000000 00000110 

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


    Décalage arithmétique à droite (>>)

    Le décalage arithmétique à droite est exactement comme le décalage logique à droite, sauf qu'au lieu de remplir avec zéro, il ajoute le bit le plus significatif. En effet, le bit le plus significatif est le bit de 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 est préservé des signes.

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

     10000000 00000000 00000000 01100000 

    nous avons le numéro -2 147 483 552. En le déplaçant vers la droite 4 positions avec le décalage arithmétique (-2,147,483,552 >> 4) nous donnerions:

     11111000 00000000 00000000 00000110 

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

    Nous voyons donc que nous avons préservé le signe de nos nombres négatifs en utilisant le décalage arithmétique à droite, plutôt que le décalage logique logique. Et encore une fois, nous constatons que nous effectuons une division par pouvoirs de 2.

    Disons que nous avons un seul octet:

     0110110 

    En appliquant un seul bit de gauche, on obtient:

     1101100 

    Le zéro le plus à gauche a été retiré de l’octet et un nouveau zéro a été ajouté à l’extrémité droite de l’octet.

    Les bits ne retournent pas; ils sont jetés. Cela signifie que si vous quittez le poste 1101100 et que vous le déplacez ensuite à droite, vous ne retrouverez pas le même résultat.

    Le décalage laissé par N équivaut à multiplier par 2 N.

    Décaler à droite par N est (si vous utilisez le complément de ), l’équivalent de la division par 2 N et l’arrondi à zéro.

    Le 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, dans les temps anciens, nous utilisions le mode 13h (320×200 256 couleurs) pour les jeux. En mode 13h, la mémoire vidéo était disposée séquentiellement par pixel. Cela pour calculer l’emplacement d’un pixel, vous utiliseriez les maths suivantes:

     memoryOffset = (row * 320) + column 

    Maintenant, à cette époque, la vitesse était critique, alors nous utilisions des bitshifts pour effectuer 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 additionnée 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 que précédemment, sauf qu'au lieu d'une opération de multiplication coûteuse, nous utilisons les deux bitshifts ... dans x86, ce serait quelque chose comme ça (remarque, ça fait éternellement que j'ai fait l'assemblage) quelques erreurs et 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 sur n'importe quelle ancienne CPU ayant ces temps.

    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 la même ancienne CPU.

    Oui, nous travaillerions dur pour supprimer 16 cycles de CPU.

    En mode 32 ou 64 bits, les deux versions deviennent beaucoup plus courtes et plus rapides. Les processeurs modernes hors d’ordre tels que Intel Skylake (voir http://agner.org/optimize/ ) se multiplient très rapidement (faible latence et haut débit), le gain est donc bien moindre. La famille d'AMD Bulldozer est un peu plus lente, en particulier pour la multiplication 64 bits. Sur les processeurs Intel et AMD Ryzen, deux temps de latence sont légèrement inférieurs mais plus d'instructions qu'un multiplication (ce qui peut réduire le 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 pour optimiser le 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 append en même temps, avec les performances et add instructions. ARM est encore plus puissant: un opérande de n'importe quelle instruction peut être déplacé vers la gauche ou la droite gratuitement. La mise à l'échelle par une constante de compilation connue pour être une puissance de 2 peut être encore plus efficace qu'une multiplication.


    OK, à l'époque moderne ... quelque chose de plus utile maintenant serait d'utiliser le transfert 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 struct une struct avec deux membres 8 bits, mais en pratique pas toujours.

    Les opérations binarys, 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 binarys, vous verrez des octets, des mots et des mots, divisés en champs de bits non alignés, qui contiennent diverses valeurs d’intérêt. L’access à ces champs 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 ONLY, qui commence au décalage 5 et se termine à 10 (soit 6 bits de long), vous devez utiliser un masque (bit) qui, appliqué à l’ensemble du pixel de 16 bits, donnera seulement les bits qui nous intéressent

     #define GREEN_MASK 0x7E0 

    Le masque approprié est 0x7E0 qui en binary 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 vous retrouverez avec un nombre de 16 bits qui est vraiment un nombre de 11 bits puisque son MSB est dans le 11ème bit. Le vert n’est en fait que de 6 bits, nous devons donc le réduire en utilisant un décalage vers la 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 rapide et une division par puissances de 2:

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

    Bit Masking & Shifting

    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 binary étiquetée avec quelles sections représentent 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 en masquant et en déplaçant .

    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 correspondant au masque 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 positions (décalage logique à droite) .

      green_value = masked_color >>> 16 

    Et voilá, 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 tels que jpg , png , ...

    Un piège 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 ce dernier.

    Notez que dans l’implémentation Java, le nombre de bits à décaler 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 élimine tout, 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.

    Je n’écris que des trucs et astuces, peut être 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, ...): cochez !(n & (n-1))
    4. Obtenir x ème bit de n : n |= (1 << x)
    5. Vérifier si x est pair ou impair: x&1 == 0 (pair)
    6. Basculer le n ème bit de x: x ^ (1<

    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 d’origine au lieu de zéros sera renvoyé, et il peut s’agir d’un bug très délicat.

    Bien sûr, si vous utilisez la 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é.

    MISE À JOUR: À partir de PHP7 Windows, les builds PHP peuvent enfin utiliser des entiers 64 bits 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 (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.