Binary shifts and bit manipulation · 二进制移位与位操作
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| bit/bɪt/ | 位 | wèi |
| mask/mæsk/ | 掩码 | yǎn mǎ |
| logical shift/ˈlɒdʒɪkl ʃɪft/ | 逻辑移位 | luó jí yí wèi |
| sign bit/saɪn bɪt/ | 符号位 | fú hào wèi |
| arithmetic right shift/ˌærɪθˈmetɪk raɪt ʃɪft/ | 算术右移 | suàn shù yòu yí |
| cyclic shift/ˈsaɪklɪk ʃɪft/ | 循环移位 | xún huán yí wèi |
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.
在不会乘法的芯片上做乘法
- 1989 年 Game Boy 里的处理器根本没有乘法指令。每一个需要加倍的分数、每一个需要加倍的坐标,都是把它的比特向左滑一位来加倍的。
- 一次移位只用一个时钟周期。用移位和加法搭出来的乘法,就是那些游戏能在几千字节和几毫瓦上运行的原因。
- 同样的技巧用来控制嵌入式设备里的单根导线:寄存器的一个比特对应一个传感器或执行器,用一个掩码(mask)来测试和设置。
- 这一课讲三种移位和四种掩码操作,用考试自己的指令。
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)
逻辑移位
- 逻辑移位(logical shift)把每个比特向左或向右移若干位,空出来的位置填 0。
LSL #1把比特左移,右边进一个 0:对无符号数这是 × 2。LSR #1把它们右移,左边进一个 0:整数 ÷ 2。- 移 $n$ 位就是乘或除 $2^{n}$。
00001011(11)经LSL #1后是00010110(22);经LSR #1后是00000101(5,余数丢失)。
逻辑左移(× 2)、逻辑右移(÷ 2)和算术右移(保留符号位)
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. · 选一个运算符,看每个结果位。一个左移(<<)把每个位上移一位(×2);一个右移(>>)把它们下移(÷2);和一个掩码做 AND 清除你不想要的位。
The 8-bit value 00001011 (11) is shifted left by 1 (LSL #1). What is the new denary value? · 8 位的值 00001011(11)左移 1 位(LSL #1)。新的十进制值是多少?
A left shift by 1 multiplies by 2: $11 \times 2 = 22$ (00010110). · 左移 1 位乘以 2:$11 \times 2 = 22$(00010110)。
Shifting an unsigned number left by 3 places multiplies it by what number? · 把一个无符号数左移 3 位,乘以什么数?
Shifting by $n$ places multiplies by $2^n$, so by 3 places is $2^3 = 8$. · 移 $n$ 位乘以 $2^n$,所以移 3 位是 $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.
例题:什么时候 × 4 不再成立
- 移出末端的比特就丢了,所以只有当它们是 0 时乘法才正确。
- 对二进制补码字节
11001010做LSL #2得到00101000。从左边掉出去的两个 1 没了,符号位变了,结果不再是原来的四倍。 - 对
00001011(11)做LSL #2得到00101100(44),这是正确的,因为只丢了 0。 - 考试两个都要:移位后的模式,以及对数值是否仍然正确的说明。
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
算术右移
- 普通的逻辑右移在最高位放一个 0,这会把负的二进制补码数变成正数。
- 算术右移(arithmetic right shift)把符号位(sign bit)复制到每个空出的位置,所以负数仍然是负数,而且移位仍然是除以 2。
10011110算术右移 3 位是11110011;01011100得到00001011。
同一个字节的逻辑和算术右移:只有进入的那一位不同
An arithmetic right shift differs from a logical right shift because it: · 一个算术右移与一个逻辑右移不同,因为它:
It preserves the sign bit, so dividing a negative signed number by a power of 2 keeps it negative. · 它保留符号位,所以把一个负的有符号数除以 2 的幂保持它为负。
A logical right shift always puts a 0 in the top bit, so it can turn a negative signed number positive. · 一个逻辑右移总是在最高位放一个 0,所以它能把一个负的有符号数变成正的。
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 ____. · 对 10011110 算术右移 3 位得到 8 位模式 ____。
The three vacated places on the left are filled with copies of the sign bit, 1, and the three rightmost bits 110 fall off. · 左边空出的三个位置填上符号位 1 的副本,最右边的三位 110 掉出去。
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.
循环移位
- 循环移位(cyclic shift),或旋转,把从一端掉出的比特从另一端送回来,所以没有比特丢失。
- 对
10000110循环左移 1 位得到00001101:最高位的 1 在右边重新出现。 - 逻辑移位填 0,算术移位填符号位,循环移位填离开的那一位。这就是三者的全部区别。
A cyclic left shift of 1 place is applied to 10000110. What is the result? · 对 10000110 做 1 位循环左移。结果是什么?
The leading 1 leaves on the left and re-enters on the right, so no bit is lost. 00001100 would be the logical shift. · 最高位的 1 从左边离开,从右边重新进入,所以没有比特丢失。00001100 是逻辑移位的结果。
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.
例题:240 还是负 16?
- 取
11110000。按无符号读是 240;按二进制补码读是 −16。 LSR #1进一个 0,得到01111000= 120,是 240 正确的一半。ASR #1复制符号位,得到11111000= −8,是 −16 正确的一半。- 两者都不错。各自在一种读法下把值减半,这就是处理器为什么需要两条指令。
Which statements about the byte 11110000 are correct? Select all · 所有 that apply. · 关于字节 11110000 的哪些陈述是正确的?选出所有适用的。
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. · 两个结果只在左边进入的那一位不同:逻辑移位进 0,算术移位进符号位。
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
位掩码
- 嵌入式设备常用寄存器的一个位(bit)对应一个信号。掩码是一个与寄存器组合的模式,使得只有选中的位改变。
- 置位第 $n$ 位:与在第 $n$ 位为 1 的掩码做
OR。清零第 $n$ 位:与在该位为 0、其余全为 1 的掩码做AND。 - 翻转第 $n$ 位:与在该位为 1 的掩码做
XOR。测试第 $n$ 位:与该掩码做AND,然后CMP #0:不相等意味着该位被置位。
用 OR 置位,用 AND 清零,用 XOR 翻转,各用一个掩码
Match each bit operation to the bitwise operator (and mask) that does it. · 把每个位操作与做它的位运算符(和掩码)配对。
OR sets, AND clears, XOR toggles, and AND + a non-zero test reads a bit — the four masking moves. · OR 设置,AND 清除,XOR 翻转,AND + 一个非零测试读一个位——四个掩码动作。
To SET a particular bit to 1, you combine the register with a mask using: · 要把一个特定的位设置为 1,你用以下把寄存器和一个掩码结合:
OR with a mask that has that bit = 1 forces the bit to 1 and leaves the others unchanged. · 和一个那一位 = 1 的掩码做 OR 把那一位强制为 1 并让其他的不变。
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.
例题:对一个字节的各条指令
- ACC 存着
10101100。掩码可以写成#n十进制、Bn二进制或&n十六进制。 AND B00001111得到00001100:只有低四位留下。OR #1得到10101101:最低位被置位,其余不动。XOR &FF得到01010011:每一位取反。AND B00001000然后CMP #0测试第 3 位;结果00001000不为零,所以第 3 位是置位的。LSL #2得到10110000,丢掉最高两位;LSR #3得到00010101。
The instruction that sets the least significant bit of the ACC to 1 and leaves the other bits unchanged is OR ____. · 把 ACC 最低位置为 1 并保持其他位不变的指令是 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. · 与只在最后一位为 1 的掩码做 OR。十进制 #1、二进制 B00000001 和十六进制 &1 是同一个掩码。
Put the steps for testing whether bit 3 of the ACC is set in order. · 把测试 ACC 第 3 位是否置位的步骤按顺序排列。
Mask, compare, jump. The AND leaves either 00001000 or 00000000, and the compare with zero tells them apart. · 掩码、比较、跳转。AND 只留下 00001000 或 00000000,与零比较就能区分它们。
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.
一位一位地监控和控制
- 在监控设备里,寄存器的一个位对应一个传感器,意味着一条
AND就能检查某个传感器是否开着。 - 在控制设备里,一条
OR打开一个执行器的控制位而不干扰其他位,一条AND把它关掉。 - 它快,几乎不占存储器,而且一个字节保存八个独立的开/关状态。这就是考试要问的"为什么"。
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.
容易丢掉的分
- 左移每位 × 2 只有在掉出的比特是 0 时成立。丢了 1 时要说出来。
- 逻辑右移进 0;算术右移复制符号位。按数字是否有符号来选。
- 要清零一个位,掩码在该位要是 0,其余全是 1。全 0 的掩码会清空整个寄存器。
XOR是翻转;它不是置位。置位用OR,测试用AND再与零比较。
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
你掌握了
- 逻辑移位填 0:左移每位 × 2,右移 ÷ 2,丢掉的 1 会破坏算术
- 算术右移复制符号位;循环移位把比特绕回来
- 掩码:OR 置位 · AND 清零 · XOR 翻转 · AND 再 CMP #0 测试
- 每个传感器或执行器一位,让监控和控制又快又小;掩码写成
#n、Bn或&n