Binary arithmetic and signed integers · 二进制算术与有符号整数
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| overflow/ˌəʊvəˈfləʊ/ | 溢出 | yì chū |
| two's complement/tuːz ˈkɒmplɪmənt/ | 补码 | bǔ mǎ |
| register/ˈredʒɪstə/ | 寄存器 | jì cún qì |
| sign bit/saɪn bɪt/ | 符号位 | fú hào wèi |
| most significant bit/məʊst sɪɡˈnɪfɪkənt bɪt/ | 最高有效位 | zuì gāo yǒu xiào wèi |
| one's complement/wʌnz ˈkɒmplɪmənt/ | 反码 | fǎn mǎ |
| Binary Coded Decimal/ˈbaɪnəri ˈkəʊdɪd ˈdesɪml/ | 二进制编码十进制 | èr jìn zhì biān mǎ shí jìn zhì |
The bank that lost a day
- On 1 September 1983 the Vancouver Stock Exchange index stood at 524.811. It had opened at 1000 twenty-two months earlier, and the market had risen the whole time.
- The program recalculated the index after every trade, truncating rather than rounding each time. Each truncation lost a fraction of a point. Three thousand trades a day did the rest.
- When it was recomputed properly the index was 1098.892: the arithmetic, not the market, had halved it.
- Arithmetic on a fixed number of bits is not the arithmetic you learned at school. This lesson is binary addition, overflow 溢出, subtraction by two's complement 补码, signed integers, and BCD.
丢了一半的指数
- 1983 年 9 月 1 日,温哥华证券交易所指数停在 524.811。它在二十二个月前从 1000 开盘,而市场一路上涨。
- 程序在每笔交易后重算指数,每次都截断而不是四舍五入。每次截断丢掉零点几分。每天三千笔交易完成了其余的工作。
- 正确重算后,指数是 1098.892:把它腰斩的是算术,不是市场。
- 固定位数上的算术不是你在学校学的算术。这一课讲二进制加法、溢出(overflow)、用补码(two's complement)做减法、有符号整数,以及 BCD。
Binary addition
- Add column by column from the right, carrying into the next column, exactly as in denary.
- The rules: $0 + 0 = 0$; $0 + 1 = 1$; $1 + 1 = 10$, write 0 and carry 1; $1 + 1 + 1 = 11$, write 1 and carry 1.
0101$+$0011$=$1000, that is $5 + 3 = 8$.
Same method as denary, only two digits to carry between
二进制加法
- 从右往左逐列相加,向下一列进位,和十进制完全一样。
- 规则:$0 + 0 = 0$;$0 + 1 = 1$;$1 + 1 = 10$,写 0 进 1;$1 + 1 + 1 = 11$,写 1 进 1。
0101$+$0011$=$1000,也就是 $5 + 3 = 8$。
方法和十进制一样,只是只有两个数字要进位
Binary & signed integers · 二进制与有符号整数
byte = Σ place values · 字节 = Σ 位值
See how an 8-bit pattern maps to a number (and how it would overflow past 255). · 看一个 8 位模式如何映射到一个数字(以及它如何会溢出超过 255)。
Add the binary numbers 0101 + 0011. Give the 4-bit result. · 把二进制数 0101 + 0011 相加。给出 4 位结果。
$5 + 3 = 8$, which is 1000 in binary. · $5 + 3 = 8$,在二进制中是 1000。
Overflow
- Overflow happens when the result of a calculation needs more bits than the register 寄存器 can hold. The carry out of the most significant column is lost, so the stored answer is wrong.
- It is a property of the register width, not of the number 255: in a 16-bit register the same sum is fine.
- In signed arithmetic the tell-tale is a sign bit that flips wrongly: two positives giving a negative, or two negatives giving a positive.
溢出
- 当计算结果需要的位数超过寄存器(register)能容纳的位数时,就发生溢出。最高位的进位丢失,所以存下的答案是错的。
- 它是寄存器宽度的属性,不是数字 255 的属性:在 16 位寄存器里同样的加法毫无问题。
- 在有符号算术里,标志是符号位错误地翻转:两个正数得出负数,或两个负数得出正数。
Overflow in binary addition means: · 二进制加法中的溢出意味着:
Overflow occurs when the sum is too large to fit in the available bits; the carry out of the leftmost column is lost. · 当和太大无法放进可用的位时发生溢出;最左列的进位丢失。
Worked example: name the overflow properly
- Add the 8-bit unsigned integers
10110101and01101100and comment on the result. - The sum is
1 0010 0001, which needs 9 bits. The true result is 289. - Full answer: overflow has occurred, because 289 is larger than the largest value an 8-bit register can hold, 255; the carry out of the most significant bit is lost, so the stored result
0010 0001is 33, which is wrong. - The mark is for naming the register width and saying the result cannot be represented in it. "The answer was more than 255" alone does not score.
例题:正确地说出溢出
- 把 8 位无符号整数
10110101和01101100相加并对结果作出说明。 - 和是
1 0010 0001,需要 9 位。真实结果是 289。 - 完整答案:发生了溢出,因为 289 大于 8 位寄存器能容纳的最大值 255;最高位的进位丢失,所以存下的结果
0010 0001是 33,是错的。 - 得分点在于说出寄存器宽度,并说明结果无法在其中表示。单说"答案大于 255"不得分。
Two 8-bit unsigned integers are added and the result needs 9 bits. Which is the full-mark explanation? · 两个 8 位无符号整数相加,结果需要 9 位。哪一个是满分的解释?
Name the register width, say the result cannot be represented in it, and say what happens to the carry. The other options state a symptom without the cause. · 说出寄存器宽度,说明结果无法在其中表示,再说进位怎么了。其他选项只描述现象,没有原因。
Subtraction by two's complement
- To calculate $A - B$: form the two's complement of $B$ by inverting every bit and adding 1, add it to $A$, then discard any final carry-out.
- $100 - 30$ in 8 bits: two's complement of
0001 1110is1110 0001inverted, plus 1, so1110 0010. 0110 0100$+$1110 0010$=$1 0100 0110; discard the leading 1 and read0100 0110$= 70$. ✓
Subtraction becomes addition, which is why processors need no subtractor
用补码做减法
- 计算 $A - B$:把 $B$ 的每一位取反再加 1,得到它的补码,加到 $A$ 上,然后丢弃最后的进位。
- 8 位下的 $100 - 30$:
0001 1110取反是1110 0001,加 1 得1110 0010。 0110 0100$+$1110 0010$=$1 0100 0110;丢掉最前面的 1,读0100 0110$= 70$。✓
减法变成了加法,这就是处理器不需要减法器的原因
What is the 4-bit two's complement of 0011? (invert, then add 1) · 0011 的 4 位二进制补码是什么?(取反,然后加 1)
Invert 0011 → 1100, then add 1 → 1101 (which represents $-3$). · 取反 0011 → 1100,然后加 1 → 1101(它表示 $-3$)。
Put the steps of subtracting B from A by two's complement in order. · 把用补码从 A 中减去 B 的步骤按顺序排列。
Invert, add one, add, discard. The discard is what keeps the answer in the register's width. · 取反、加一、相加、丢弃。丢弃这一步让答案保持在寄存器宽度内。
Two's complement signed integers
- In an $n$-bit two's complement number the most significant bit 最高有效位 is the sign bit 符号位: 0 means positive, 1 means negative. Equivalently, the top bit carries a negative place value, $-2^{n-1}$.
- To read a negative number: invert every bit, add 1, then put a minus sign in front.
1011 0100inverts to0100 1011, plus 1 is0100 1100$= 76$, so the value is $-76$. Check by place value: $-128 + 32 + 16 + 4 = -76$. ✓ - For $n$ bits the range is $-2^{n-1}$ to $+2^{n-1} - 1$: 8 bits give $-128$ to $+127$, 12 bits give $-2048$ to $+2047$. The most negative value is a 1 followed by zeros; the most positive is a 0 followed by ones.
11111111 is 255 read one way and −1 read the other
补码有符号整数
- 在 $n$ 位补码数中,最高有效位(most significant bit)是符号位(sign bit):0 表示正,1 表示负。等价地说,最高位带一个负的位值 $-2^{n-1}$。
- 读一个负数:每一位取反,加 1,再在前面加负号。
1011 0100取反得0100 1011,加 1 得0100 1100$= 76$,所以值是 $-76$。用位值检查:$-128 + 32 + 16 + 4 = -76$。✓ - $n$ 位的范围是 $-2^{n-1}$ 到 $+2^{n-1} - 1$:8 位给出 $-128$ 到 $+127$,12 位给出 $-2048$ 到 $+2047$。最负的值是一个 1 后面全是 0;最正的值是一个 0 后面全是 1。
11111111 一种读法是 255,另一种读法是 −1
Two's complement signed bits · 二进制补码(有符号位)
The leftmost bit carries a negative · 负形 place value. Flip any bit — or hit Negate (invert every bit, then add 1) — and watch the signed value change. · 最左边的位带有一个负的位值。翻转任意一位——或点击取负(每一位取反,然后加 1)——看有符号值如何变化。
Read the 8-bit two's complement number 11111101 as a signed denary value. · 把 8 位二进制补码数 11111101 读作一个有符号的十进制值。
MSB is 1 (negative). Invert → 00000010, add 1 → 00000011 $= 3$, so the value is $-3$. · MSB 是 1(负)。取反 → 00000010,加 1 → 00000011 $= 3$,所以这个值是 $-3$。
What is the largest positive value an 8-bit two's complement number can hold? · 一个 8 位二进制补码数能容纳的最大正值是多少?
Range is $-2^{7}$ to · 到 $2^{7}-1$, i.e. $-128$ to · 到 $+127$. The maximum is 01111111 = 127. · 范围是 $-2^{7}$ 到 $2^{7}-1$,即 $-128$ 到 $+127$。最大值是 01111111 = 127。
Worked example: write −108 in 12 bits
- Start from $+108$ in 12 bits: $108 = 64 + 32 + 8 + 4$, so
0000 0110 1100. - Invert every bit:
1111 1001 0011. Add 1:1111 1001 0100. - Check with place values, where the top bit is worth $-2048$: $-2048 + 1024 + 512 + 256 + 128 + 16 + 4 = -108$. ✓
- The commonest error is sign and magnitude: setting the top bit to 1 and leaving the rest. That is a different, older scheme and scores zero here.
例题:用 12 位写出 −108
- 从 12 位的 $+108$ 开始:$108 = 64 + 32 + 8 + 4$,所以是
0000 0110 1100。 - 每一位取反:
1111 1001 0011。加 1:1111 1001 0100。 - 用位值检查,最高位值 $-2048$:$-2048 + 1024 + 512 + 256 + 128 + 16 + 4 = -108$。✓
- 最常见的错误是符号加数值:把最高位设为 1、其余不动。那是另一种更老的方案,在这里零分。
Write −108 as a 12-bit two's complement number (spaces allowed). · 把 −108 写成 12 位补码数(可以有空格)。
+108 is 0000 0110 1100; invert to 1111 1001 0011 and add 1. Check: −2048 + 1024 + 512 + 256 + 128 + 16 + 4 = −108. · +108 是 0000 0110 1100;取反得 1111 1001 0011 再加 1。检查:−2048 + 1024 + 512 + 256 + 128 + 16 + 4 = −108。
One's complement
- One's complement 反码 is the older scheme: a negative is made by inverting every bit of the positive, with no add-1 step. $+30$ is
0001 1110, so $-30$ is1110 0001. - Its drawback is two zeros,
0000 0000and1111 1111, which wastes a bit pattern and complicates the arithmetic. - Two's complement has one zero and lets the same adder circuit do subtraction, which is why it won.
反码
- 反码(one's complement)是更老的方案:把正数的每一位取反就得到负数,没有加 1 这一步。$+30$ 是
0001 1110,所以 $-30$ 是1110 0001。 - 它的缺点是两个零,
0000 0000和1111 1111,浪费一个位模式,也让算术变得别扭。 - 补码只有一个零,而且让同一个加法器电路就能做减法,这就是它胜出的原因。
One's complement is preferred to two's complement because it has only one representation of zero. · 反码比补码更受青睐,因为它只有一种零的表示。
The opposite: one's complement has two zeros, +0 and −0. Two's complement has one, and lets the adder do subtraction. · 恰恰相反:反码有两个零,+0 和 −0。补码只有一个,而且让加法器就能做减法。
Binary Coded Decimal
- In Binary Coded Decimal 二进制编码十进制 (BCD) each denary digit is stored as its own 4-bit pattern, using only
0000to1001. - 93 in BCD is
1001 0011, which is not the same as 93 in pure binary,0101 1101. Reading one as the other is a favourite exam trap. - Uses: calculators, digital clocks and seven-segment displays, where each digit is driven separately, and currency, where BCD avoids the rounding errors of storing $0.1$ in pure binary. The cost is wasted patterns, since
1010to1111are never used.
One digit, one nibble, one display
二进制编码十进制
- 在 二进制编码十进制(Binary Coded Decimal,BCD)中,每个十进制数位存成它自己的 4 位模式,只用
0000到1001。 - 93 的 BCD 是
1001 0011,这与纯二进制的 930101 1101不同。把一个当成另一个读是考试最爱的陷阱。 - 用途:计算器、数字钟和七段显示器,每个数位单独驱动;还有货币,BCD 避免了纯二进制存 $0.1$ 的舍入误差。代价是浪费了位模式,因为
1010到1111从不使用。
一个数位,一个半字节,一个显示位
Write the denary digit $9$ as a 4-bit BCD pattern. · 把十进制数字 $9$ 写成一个 4 位 BCD 模式。
$9$ is 1001. In BCD each denary digit gets its own nibble (0000–1001). · $9$ 是 1001。在 BCD 中每个十进制数字得到它自己的半字节(0000–1001)。
Match each bit pattern to what it represents. · 把每个位模式与它表示的东西配对。
Nothing in the bits says how to read them. The agreed representation decides the value. · 位本身不说明怎样读它们。约定的表示法决定了值。
Marks that slip away
- Explain overflow with the register width the question gave, not with "it was more than 255".
- To negate, invert and add 1. Setting the top bit to 1 is sign and magnitude, a different scheme.
- Two's complement subtraction ends by discarding the final carry-out. Keeping it gives a nine-bit answer.
- BCD stores each digit separately; pure binary stores the whole number.
1001 0011is 93 in BCD and 147 in binary.
容易丢掉的分
- 用题目给的寄存器宽度解释溢出,不要说"它大于 255"。
- 取负要取反再加 1。把最高位设为 1 是符号加数值,是另一种方案。
- 补码减法以丢弃最后的进位结束。留着它会得到九位的答案。
- BCD 分别存每个数位;纯二进制存整个数。
1001 0011在 BCD 里是 93,在二进制里是 147。
You've got it
- add column by column with carries; overflow is a result needing more bits than the register holds, and the answer names that width
- subtract by adding the two's complement, invert and add 1, then discard the final carry
- signed: the MSB is the sign bit and carries $-2^{n-1}$; range $-2^{n-1}$ to $+2^{n-1}-1$; read a negative by inverting, adding 1 and negating
- one's complement inverts only and has two zeros; BCD stores each denary digit in its own nibble, for clocks, calculators and currency
你掌握了
- 带进位逐列相加;溢出是结果需要的位数超过寄存器容量,答案要点出那个宽度
- 减法靠加补码——取反加 1——然后丢弃最后的进位
- 有符号:MSB 是符号位,带 $-2^{n-1}$;范围 $-2^{n-1}$ 到 $+2^{n-1}-1$;读负数靠取反、加 1、再取负
- 反码只取反,有两个零;BCD 把每个十进制数位存进自己的半字节,用于钟表、计算器和货币