Binary shifts and bit manipulation
Introduced| English | Meaning |
|---|---|
| bit/bɪt/ | A binary digit, taking the value zero or one. |
| mask/mæsk/ | A pattern of bits used with logical operations to select, test, set or clear particular bits. |
| logical shift/ˈlɒdʒɪkl ʃɪft/ | logical shift |
| sign bit/saɪn bɪt/ | The bit in a signed-number representation that indicates or contributes the number's sign. |
| arithmetic right shift/ˌærɪθˈmetɪk raɪt ʃɪft/ | arithmetic right shift |
| cyclic shift/ˈsaɪklɪk ʃɪft/ | A bit shift in which bits moved beyond one end of a word re-enter at the other end. |
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.
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)
Shift and mask the bits of a byte
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.
The 8-bit value 00001011 (11) is shifted left by 1 (LSL #1). What is the new denary value?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
A left shift by 1 multiplies by 2: $11 \times 2 = 22$ (00010110).
Shifting an unsigned number left by 3 places multiplies it by what number?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Shifting by $n$ places multiplies by $2^n$, so by 3 places is $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.
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
An arithmetic right shift differs from a logical right shift because it:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
It preserves the sign bit, so dividing a negative signed number by a power of 2 keeps it negative.
A logical right shift always puts a 0 in the top bit, so it can turn a negative signed number positive.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
That is exactly why signed division needs an arithmetic right shift, which copies the sign bit instead.
An arithmetic right shift of 10011110 by 3 places gives the 8-bit pattern ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The three vacated places on the left are filled with copies of the sign bit, 1, and the three rightmost bits 110 fall off.
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.
A cyclic left shift of 1 place is applied to 10000110. What is the result?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The leading 1 leaves on the left and re-enters on the right, so no bit is lost. 00001100 would be the logical shift.
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.
Which statements about the byte 11110000 are correct? Select all that apply.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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.
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
Match each bit operation to the bitwise operator (and mask) that does it.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
OR sets, AND clears, XOR toggles, and AND + a non-zero test reads a bit — the four masking moves.
To SET a particular bit to 1, you combine the register with a mask using:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
OR with a mask that has that bit = 1 forces the bit to 1 and leaves the others unchanged.
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.
The instruction that sets the least significant bit of the ACC to 1 and leaves the other bits unchanged is OR ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
OR with a mask that has a 1 only in the last place. Denary #1, binary B00000001 and hexadecimal &1 are the same mask.
Put the steps for testing whether bit 3 of the ACC is set in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Mask, compare, jump. The AND leaves either 00001000 or 00000000, and the compare with zero tells them apart.
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.
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.
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