二進数シフトとビット操作

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 #1 moves the bits left and a 0 enters on the right: for an unsigned number that is × 2. LSR #1 moves them right and a 0 enters on the left: integer ÷ 2.
• Shifting by $n$ places multiplies or divides by $2^{n}$. 00001011 (11) after LSL #1 is 00010110 (22); after LSR #1 it is 00000101 (5, the remainder lost).

Logical left (× 2), logical right (÷ 2) and arithmetic right (keeps the sign bit)

Worked example: when × 4 stops being true

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.
• 10011110 shifted arithmetically right by 3 places is 11110011; 01011100 gives 00001011.

Logical and arithmetic right shift on the same byte: only the entering bit differs

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 10000110 gives 00001101: 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.

Worked example: 240 or minus 16?

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$: OR with a mask that has a 1 in position $n$. Clear bit $n$: AND with a mask that has a 0 there and 1s everywhere else.
• Toggle bit $n$: XOR with a mask that has a 1 there. Test bit $n$: AND with that mask, then CMP #0: not equal means the bit was set.

Set with OR, clear with AND, toggle with XOR, each using a mask

Worked example: the instructions on one byte

Monitoring and control, one bit at a time

• In a monitoring device one bit of a register per sensor means a single AND checks whether a particular sensor is on.
• In a control device one OR switches an actuator's control bit on without disturbing the others, and one AND switches 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

You've got it