Binary shifts and bit manipulation · Décalages binaires et manipulation de bits
| English | Français |
|---|---|
| bit/bɪt/ | bit |
| mask/mæsk/ | masque |
| logical shift/ˈlɒdʒɪkl ʃɪft/ | décalage logique |
| sign bit/saɪn bɪt/ | bit de signe |
| arithmetic right shift/ˌærɪθˈmetɪk raɪt ʃɪft/ | décalage arithmétique à droite |
| cyclic shift/ˈsaɪklɪk ʃɪft/ | décalage cyclique |
Multiplying on a chip that cannot multiply
- The processor in the 1989 Game Boy had no multiply instruction at all. Every score, every coordinate that needed doubling was doubled by sliding its bits one place to the left.
- A shift takes one clock tick. Multiplication built from shifts and additions is how those games ran on a few kilobytes and a handful of milliwatts.
- The same tricks control single wires in an embedded device: one bit of a register per sensor or actuator, tested and set with a mask 掩码.
- This lesson is the three kinds of shift and the four mask operations, in the exam's own instructions.
Multiplier sur une puce qui ne peut pas multiplier
- Le processeur du Game Boy de 1989 n'avait aucune instruction de multiplication. Chaque score, chaque coordonnée nécessitant un doublement était doublé en décalant ses bits d'une position vers la gauche.
- Un décalage prend une seule impulsion d'horloge. La multiplication construite à partir de décalages et d'additions est ainsi que ces jeux fonctionnaient sur quelques kiloctets et quelques milliwatts.
- Les mêmes astuces contrôlent des fils individuels dans un appareil embarqué : un bit de registre par capteur ou actionneur, testés et définis avec un masque 掩码.
- Cette leçon porte sur les trois types de décalage et les quatre opérations de masquage, selon les instructions de l'examen.
Logical shifts
- A logical shift 逻辑移位 moves every bit left or right by some places and fills the vacated positions with 0.
LSL #1moves the bits left and a 0 enters on the right: for an unsigned number that is × 2.LSR #1moves them right and a 0 enters on the left: integer ÷ 2.- Shifting by $n$ places multiplies or divides by $2^{n}$.
00001011(11) afterLSL #1is00010110(22); afterLSR #1it is00000101(5, the remainder lost).
Logical left (× 2), logical right (÷ 2) and arithmetic right (keeps the sign bit)
Décalages logiques
- Un décalage logique 逻辑移位 déplace tous les bits vers la gauche ou la droite d'un certain nombre de places et remplit les positions libérées par des 0.
LSL #1décale les bits vers la gauche et un 0 entre à droite : pour un nombre non signé, cela équivaut à × 2.LSR #1les décale vers la droite et un 0 entre à gauche : integer ÷ 2.- Décaler de $n$ places multiplie ou divise par $2^{n}$.
00001011(11) aprèsLSL #1devient00010110(22) ; aprèsLSR #1c'est00000101(5, le reste est perdu).
Décalage logique gauche (× 2), logique droit (÷ 2) et arithmétique droit (conserve le bit de signe)
Shift and mask the bits of a byte · Décalez et masquez les bits d'un octet
Pick an operator and watch each result bit. A left shift (<<) moves every bit up one place (×2); a right shift (>>) moves them down (÷2); AND with a mask clears the bits you don't want. · Choisissez un opérateur et observez chaque bit de résultat. Un décalage gauche (<<) moves every bit up one place (×2); a right shift (>>) les déplace vers la droite (÷2) ; AND avec un masque efface les bits que vous ne voulez pas.
The 8-bit value 00001011 (11) is shifted left by 1 (LSL #1). What is the new denary value? · La valeur 8 bits 00001011 (11) est décalée à gauche de 1 (LSL #1). Quelle est la nouvelle valeur décimale ?
A left shift by 1 multiplies by 2: $11 \times 2 = 22$ (00010110). · Un décalage gauche de 1 multiplie par 2 : $11 \times 2 = 22$ (00010110).
Shifting an unsigned number left by 3 places multiplies it by what number? · Décaler un nombre non signé de 3 places vers la gauche le multiplie par quel nombre ?
Shifting by $n$ places multiplies by $2^n$, so by 3 places is $2^3 = 8$. · Décaler de $n$ places multiplie par $2^n$, donc de 3 places c'est $2^3 = 8$.
Worked example: when × 4 stops being true
- Bits shifted off the end are lost, so the multiplication is only correct while they were zeros.
LSL #2on the two's complement byte11001010gives00101000. The two 1s that fell off the left are gone, the sign bit has changed, and the result is no longer four times the original.LSL #2on00001011(11) gives00101100(44), which is correct, because only zeros were lost.- The exam asks for both: the shifted pattern, and a comment on whether the value is still right.
Exemple résolu : quand × 4 cesse d'être correct
- Les bits décalés hors de l'extrémité sont perdus, donc la multiplication n'est correcte que tant qu'ils étaient des zéros.
LSL #2sur le byte en complément à deux11001010donne00101000. Les deux 1s tombés à gauche ont disparu, le bit de signe a changé, et le résultat n'est plus quatre fois la valeur originale.LSL #2sur00001011(11) donne00101100(44), ce qui est correct, car seuls des zéros ont été perdus.- L'examen demande les deux : le motif décalé, et un commentaire sur la validité de la valeur.
Arithmetic right shift
- A plain logical right shift puts a 0 in the top bit, which would turn a negative two's complement number positive.
- An arithmetic right shift 算术右移 copies the sign bit 符号位 into each vacated place, so a negative number stays negative and the shift still divides by 2.
10011110shifted arithmetically right by 3 places is11110011;01011100gives00001011.
Logical and arithmetic right shift on the same byte: only the entering bit differs
Décalage arithmétique droit
- Un simple décalage logique droit place un 0 dans le bit de poids fort, ce qui rendrait un nombre négatif en complément à deux positif.
- Un décalage arithmétique droit 算术右移 copie le bit de signe 符号位 dans chaque position libérée, afin qu'un nombre négatif reste négatif et que le décalage divise toujours par 2.
10011110décalé arithmétiquement droit de 3 places est11110011;01011100donne00001011.
Décalage logique et arithmétique droit sur le même byte : seul le bit entrant diffère
An arithmetic right shift differs from a logical right shift because it: · Un décalage arithmétique à droite diffère d'un décalage logique à droite car il :
It preserves the sign bit, so dividing a negative signed number by a power of 2 keeps it negative. · Il préserve le bit de signe, donc diviser un nombre signé négatif par une puissance de 2 le garde négatif.
A logical right shift always puts a 0 in the top bit, so it can turn a negative signed number positive. · Un décalage logique à droite met toujours un 0 dans le bit de poids fort, donc il peut transformer un nombre signé négatif en positif.
That is exactly why signed division needs an arithmetic right shift, which copies the sign bit instead. · C'est exactement pourquoi la division signée nécessite un décalage arithmétique à droite, qui copie le bit de signe au lieu de ça.
An arithmetic right shift of 10011110 by 3 places gives the 8-bit pattern ____. · Un décalage arithmétique à droite de 10011110 de 3 places donne le motif 8 bits ____.
The three vacated places on the left are filled with copies of the sign bit, 1, and the three rightmost bits 110 fall off. · Les trois emplacements vacants à gauche sont remplis de copies du bit de signe, 1, et les trois bits de droite 110 tombent.
Cyclic shifts
- A cyclic shift 循环移位, or rotate, feeds the bit that drops off one end back in at the other end, so no bits are lost.
- A cyclic left shift of 1 on
10000110gives00001101: the leading 1 reappears on the right. - Logical shifts fill with zeros, arithmetic shifts fill with the sign bit, cyclic shifts fill with the bit that left. That is the whole difference between the three.
Décalages cycliques
- Un décalage cyclique 循环移位, ou rotation, réinjecte le bit qui sort d'une extrémité à l'autre, de sorte qu'aucun bit n'est perdu.
- Un décalage cyclique gauche de 1 sur
10000110donne00001101: le 1 initial réapparaît à droite. - Les décalages logiques se remplissent de zéros, les décalages arithmétiques se remplissent du bit de signe, les décalages cycliques se remplissent du bit qui est sorti. C'est toute la différence entre les trois.
A cyclic left shift of 1 place is applied to 10000110. What is the result? · Un décalage cyclique à gauche de 1 place est appliqué à 10000110. Quel est le résultat ?
The leading 1 leaves on the left and re-enters on the right, so no bit is lost. 00001100 would be the logical shift. · Le 1 de tête sort à gauche et ré-entre à droite, donc aucun bit n'est perdu. 00001100 serait le décalage logique.
Worked example: 240 or minus 16?
- Take
11110000. Read as unsigned it is 240; read as two's complement it is −16. LSR #1brings in a 0 and gives01111000= 120, the correct half of 240.ASR #1copies the sign bit and gives11111000= −8, the correct half of −16.- Neither is wrong. Each halves the value under one reading, which is why a processor needs both instructions.
Exemple résolu : 240 ou moins 16 ?
- Prenez
11110000. Lu comme non signé, c'est 240 ; lu comme complément à deux, c'est −16. LSR #1apporte un 0 et donne01111000= 120, la moiti正确 de 240.ASR #1copie le bit de signe et donne11111000= −8, la moiti正确 de −16.- Aucun n'est faux. Chacun divise la valeur par deux selon une interprétation, ce qui explique pourquoi un processeur a besoin des deux instructions.
Which statements about the byte 11110000 are correct? Select all · tout that apply. · Quelles affirmations concernant l'octet 11110000 sont correctes ? Sélectionnez tous ceux qui s'appliquent.
The two results differ only in the bit that enters on the left: 0 for the logical shift, the sign bit for the arithmetic shift. · Les deux résultats diffèrent uniquement dans le bit entrant à gauche : 0 pour le décalage logique, le bit de signe pour le décalage arithmétique.
Bit masking
- Embedded devices often use one bit 位 of a register per signal. A mask is a pattern combined with the register so that only the chosen bit changes.
- Set bit $n$:
ORwith a mask that has a 1 in position $n$. Clear bit $n$:ANDwith a mask that has a 0 there and 1s everywhere else. - Toggle bit $n$:
XORwith a mask that has a 1 there. Test bit $n$:ANDwith that mask, thenCMP #0: not equal means the bit was set.
Set with OR, clear with AND, toggle with XOR, each using a mask
Masquage de bits
- Les appareils embarqués utilisent souvent un bit 位 de registre par signal. Un masque est un motif combiné au registre pour que seul le bit choisi change.
- Définir le bit $n$ :
ORavec un masque ayant un 1 à la position $n$. Effacer le bit $n$ :ANDavec un masque ayant un 0 à cet endroit et des 1 partout ailleurs. - Basculer le bit $n$ :
XORavec un masque ayant un 1 à cet endroit. Tester le bit $n$ :ANDavec ce masque, puisCMP #0: si différent de zéro, le bit était défini.
Définir avec OR, effacer avec AND, basculer avec XOR, chacun utilisant un masque
Match each bit operation to the bitwise operator (and mask) that does it. · Associez chaque opération binaire à l'opérateur bit à bit (et au masque) qui la réalise.
OR sets, AND clears, XOR toggles, and AND + a non-zero test reads a bit — the four masking moves. · OR définit, AND efface, XOR toggle, et AND + test non nul lit un bit — les quatre mouvements de masquage.
To SET a particular bit to 1, you combine the register with a mask using: · Pour DÉFINIR un bit particulier à 1, vous combinez le registre avec un masque en utilisant :
OR with a mask that has that bit = 1 forces the bit to 1 and leaves the others unchanged. · OR avec un masque ayant ce bit = 1 force le bit à 1 et laisse les autres inchangés.
Worked example: the instructions on one byte
- The ACC holds
10101100. The mask may be written#ndenary,Bnbinary or&nhexadecimal. AND B00001111gives00001100: only the low four bits survive.OR #1gives10101101: the least significant bit is set and nothing else moves.XOR &FFgives01010011: every bit inverted.AND B00001000thenCMP #0tests bit 3; the result00001000is not zero, so bit 3 was set.LSL #2gives10110000, losing the top two bits;LSR #3gives00010101.
Exemple résolu : les instructions sur un byte
- L'ACC contient
10101100. Le masque peut être écrit#ndécimal,Bnbinaire ou&nhexadécimal. AND B00001111donne00001100: seuls les quatre bits de poids faible subsistent.OR #1donne10101101: le bit de poids faible est défini et rien d'autre ne bouge.XOR &FFdonne01010011: tous les bits sont inversés.AND B00001000ensuiteCMP #0teste le bit 3 ; le résultat00001000n'est pas zéro, donc le bit 3 était défini.LSL #2donne10110000, perdant les deux bits de poids fort ;LSR #3donne00010101.
The instruction that sets the least significant bit of the ACC to 1 and leaves the other bits unchanged is OR ____. · L'instruction qui définit le bit de poids faible du ACC à 1 et laisse les autres bits inchangés est OR ____.
OR with a mask that has a 1 only in the last place. Denary #1, binary B00000001 and hexadecimal &1 are the same mask. · OR avec un masque ayant un 1 uniquement dans la dernière position. Décimal #1, binaire B00000001 et hexadécimal &1 sont le même masque.
Put the steps for testing whether bit 3 of the ACC is set in order. · Mettez les étapes pour tester si le bit 3 du ACC est défini dans l'ordre.
Mask, compare, jump. The AND leaves either 00001000 or 00000000, and the compare with zero tells them apart. · Masque, comparer, sauter. L'AND laisse soit 00001000 soit 00000000, et la comparaison avec zéro les distingue.
Monitoring and control, one bit at a time
- In a monitoring device one bit of a register per sensor means a single
ANDchecks whether a particular sensor is on. - In a control device one
ORswitches an actuator's control bit on without disturbing the others, and oneANDswitches it off. - It is fast, it uses almost no memory, and one byte holds eight independent on/off states. That is the "why" the exam asks for.
Surveillance et contrôle, bit par bit
- Dans un dispositif de surveillance, un bit de registre par capteur signifie qu'un seul
ANDvérifie si un capteur particulier est allumé. - Dans un dispositif de contrôle, un
ORactive le bit de commande d'un actionneur sans perturber les autres, et unANDle désactive. - C'est rapide, cela consomme presque aucune mémoire, et un octet contient huit états on/off indépendants. C'est le "pourquoi" demandé à l'examen.
Marks that slip away
- A left shift is × 2 per place only while the bits that fall off are zeros. Say so when a 1 is lost.
- A logical right shift brings in 0; an arithmetic right shift copies the sign bit. Choose by whether the number is signed.
- To clear a bit the mask needs a 0 at that bit and 1s everywhere else. A mask of all zeros clears the whole register.
XORtoggles; it does not set. To set useOR, to test useANDand compare with zero.
Pièges qui font perdre des points
- Un décalage gauche est × 2 par place uniquement tant que les bits qui tombent sont des zéros. Mentionner-le lorsqu'un 1 est perdu.
- Un décalage logique droit apporte un 0 ; un décalage arithmétique droit copie le bit de signe. Choisir selon que le nombre est signé ou non.
- Pour effacer un bit, le masque doit avoir un 0 à cette position et des 1 partout ailleurs. Un masque de tout zéros efface tout le registre.
XORbascule ; il ne définit pas. Pour définir utilisezOR, pour tester utilisezANDet comparez avec zéro.
You've got it
- logical shift fills with 0: left × 2 per place, right ÷ 2, and lost 1s break the arithmetic
- arithmetic right shift copies the sign bit; a cyclic shift wraps the bit round
- masks: OR sets · AND clears · XOR toggles · AND then CMP #0 tests
- one bit per sensor or actuator makes monitoring and control fast and tiny; masks are written
#n,Bnor&n
Vous avez compris
- décalage logique se remplit de 0 : gauche × 2 par place, droit ÷ 2, et les 1 perdus cassent l'arithmétique
- décalage arithmétique droit copie le bit de signe ; un décalage cyclique fait passer le bit autour
- masques : OR définit · AND efface · XOR bascule · AND puis CMP #0 teste
- un bit par capteur ou actionneur rend la surveillance et le contrôle rapides et compacts ; les masques s'écrivent
#n,Bnou&n