第 48 / 187 篇

4.4.1. 加法

说明

本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C4-Binary/arithmetic_addition.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。

4.4.1. Addition

回想一下,二进制数中的每一位只能是 0 或 1。因此,把两个都为 1 的位相加时,结果会向下一位进位输出(carry out)(例如 1 + 1 = 0b10,需要两位来表示)。在实践中,程序相加的是多位变量,某一位的进位输出会通过进位输入(carry in)影响下一位。

Recall that in a binary number, each digit holds only 0 or 1. Consequently, when adding two bits that are both 1, the result carries out to the next digit (e.g., 1 + 1 = 0b10, which requires two bits to represent). In practice, programs add multibit variables, where the result of one digit’s carry out influences the next digit by carrying in.

一般来说,把两个二进制数(A 和 B)的某一位相加时,根据 DigitA、DigitB 以及来自前一位的 Carryin(进位输入)的值,共有八种可能的结果。表 1 列举了一对位相加可能产生的八种情况。Carryin 列指的是从前一位输入到这次求和中的进位,Carryout 列表示这一对数位相加是否会向下一位输出进位。

In general, when summing digits from two binary numbers (A and B), there are eight possible outcomes depending on the values of DigitA, DigitB, and a Carryin from the previous digit. Table 1 enumerates the eight possibilities that may result from adding one pair of bits. The Carryin column refers to a carry feeding into the sum from the previous digit, and the Carryout column indicates whether adding the pair of digits will feed a carry out to the next digit.

表 1. 两个二进制位(A 和 B)加上可能来自前一位的进位输入时的八种可能结果

Table 1. The Eight Possible Outcomes of Adding Two Binary Digits (A and B) with a Potential Carry In from the Previous Digit

输入 输出
DigitA DigitB Carryin 结果(和) Carryout
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
Inputs Outputs
DigitA DigitB Carryin Result (Sum) Carryout
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

考虑两个四位二进制数的加法。先把两个数对齐,使它们对应的数位上下对齐,然后从低位(d0)到高位(d3)依次把对应的数位相加。例如,计算 0b0010 + 0b1011:

Consider the addition of two four-bit binary numbers. Start by lining up the numbers so that their corresponding digits match vertically, and then sum each corresponding digit in order, from the low-order digit (d0) to the high-order digit (d3). For example, adding 0b0010 + 0b1011:

题目

Problem Setup

1
2
3
 
0010
+ 1011

计算过程

Worked Example

1
2
3
4
5
         1    <- Carry the 1 from digit 1 into digit 2
0010
+ 1011

Result: 1101

这个例子展示了从 d1 向 d2 进 1 的情形。这类似于两个十进制数字相加、和大于 9 的情形。例如,计算 5 + 8 = 13 时,结果的个位是 3,并向十位进 1。

The example shows a 1 carrying from d1 into d2. This situation is analogous to adding two decimal digits that sum to a value larger than 9. For example, when adding 5 + 8 = 13, the resulting ones place contains 3, and a 1 carries into the tens place.

第一个操作数(0b0010)以 0 开头,所以无论按补码还是按无符号解释,它都表示 2。第二个操作数(0b1011)如果解释为有符号补码值,表示 -5;如果解释为无符号值,则表示 11。幸运的是,操作数的解释方式不影响计算结果的步骤。也就是说,算出的结果(0b1101)要么表示 13(无符号:2 + 11),要么表示 -3(有符号:2 + -5),取决于对第二个操作数的解释,两者都是正确的。

The first operand (0b0010) has a leading 0, so it represents 2 for both two’s complement and unsigned interpretations. The second operand (0b1011) represents -5 if interpreted as a signed two’s complement value. Otherwise, it represents 11 if interpreted as an unsigned value. Fortunately, the interpretation of the operands doesn’t affect the steps for computing the result. That is, the computed result (0b1101) represents either 13 (unsigned: 2 + 11) or -3 (signed: 2 + -5), both of which are correct depending on the interpretation of the second operand.

更一般地说,四位序列按无符号解释时表示 [0, 15] 范围内的值,按有符号解释时表示 [-8, 7] 范围内的值。在前面的例子中,无论哪种解释,结果都落在可表示的范围内,但我们不会总是这么幸运。例如,计算 0b1100(无符号 12)+ 0b0111(7)时,答案应该是 19,但四位无法表示 19:

More generally, a four-bit sequence represents values in the range [0, 15] when interpreted as unsigned. When interpreted as signed, it represents the range [-8, 7]. In the previous example, the result fits within the representable range either way, but we may not always be so lucky. For example, when adding 0b1100 (unsigned 12) + 0b0111 (7), the answer should be 19, but four bits can’t represent 19:

题目

Problem Setup

1
2
3
 
1100
+ 0111

计算过程

Worked Example

1
2
3
4
5
6
             11     <- Carry a 1 from: digit 2 into digit 3, and
1100 digit 3 out of the overall value
+ 0111

Result: 0011
Carry out: 1

注意,这个例子中的加法从最高有效位进了一个 1,这种情况称为整个算术运算的进位输出(carry out)。在这个例子中,进位输出表明算术结果需要多一位才能存下预期的结果。然而,在做四位运算时,进位输出多出来的那一位无处可放,所以硬件只能把它丢弃,即截断(truncate),留下 0b0011 作为结果。当然,如果本意是计算 12 + 7,结果为 3 很可能会让人吃惊。这一意外是溢出的结果。我们会在后面的一节中探讨如何检测溢出,以及它为什么会产生这样的结果。

Note that the addition in this example carries a 1 from the most significant bit, a condition known as a carry out for the overall arithmetic operation. In this example, the carry out suggests that the arithmetic output needs an extra bit to store the intended result. However, when performing four-bit arithmetic, there’s nowhere to put the carry out’s extra bit, so the hardware simply drops or truncates it, leaving 0b0011 as the result. Of course, if the goal was to add 12 + 7, a result of 3 is likely to be surprising. The surprise is a consequence of overflow. We’ll explore how to detect overflow and why it produces the results that it does in a later section.

原书注

多位加法器电路还支持一个进位输入(carry in),它的作用就像是向最右边一位输入的进位(即作为 d0 的 Carryin 输入)。做加法时进位输入没有用处——它被隐式地设为 0,这就是它没有出现在前面例子中的原因。不过,在使用加法器电路的其他运算中,进位输入就变得重要了,最典型的就是减法。

Multibit adder circuits also support a carry in that behaves like a carry into the rightmost digit (that is, it serves as the Carryin input for d0). The carry in isn’t useful when performing addition — it’s implicitly set to 0, which is why it doesn’t appear in the preceding example. However, the carry in does become relevant for other operations that use adder circuitry, most notably subtraction.