第 44 / 187 篇

4.1. 数的进制与无符号整数

说明

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

4.1. Number Bases and Unsigned Integers

我们已经看到,二进制序列可以用各种非数值的方式来解释,现在把注意力转向数。具体来说,我们从无符号(unsigned)数开始,它可以解释为零或正数,但永远不会是负数(它们没有符号)。

Having seen that binary sequences can be interpreted in all sorts of nonnumerical ways, let’s turn our attention to numbers. Specifically, we’ll start with unsigned numbers, which can be interpreted as zero or positive, but they can never be negative (they have no sign).

4.1.1. 十进制数

4.1.1. Decimal Numbers

我们不从二进制开始,而是先看一看我们已经用惯了的数制——十进制数制(decimal number system),它的基数(base)是 10。以 10 为基数意味着在解释和表示十进制值时有两个重要性质。

Rather than starting with binary, let’s first examine a number system we’re already comfortable using, the decimal number system, which uses a base of 10. Base 10 implies two important properties for the interpretation and representation of decimal values.

  1. 十进制数中的任何一位数字都存储 10 个不同值(0–9)之一。要存储大于 9 的值,就必须向左边多出来的一位进位(carry)。例如,如果某一位从它的最大值(9)开始,再加 1,结果就需要两位数字(9 + 1 = 10)。无论这一位在数中的什么位置,都遵循同样的模式(例如 5080 + 20 = 5100)。
  1. Any individual digit in a base 10 number stores one of 10 unique values (0-9). To store a value larger than 9, the value must carry to an additional digit to the left. For example, if one digit starts at its maximum value (9) and we add 1 to it, the result requires two digits (9 + 1 = 10). The same pattern holds for any digit, regardless of its position within a number (e.g., 5080 + 20 = 5100).
  1. 数中每一位数字的位置决定了这位数字对整个数值的重要程度。把各位数字从右到左标记为 d0、d1、d2 等,每往左一位,贡献就比右边那一位大 10 倍。例如,看看数值 8425(图 1)。
  1. The position of each digit in the number determines how important that digit is to the overall value of the number. Labeling the digits from right to left as d0, d1, d2, etc., each successive digit contributes a factor of ten more than the next. For example, take the value 8425 (Figure 1).

For the number 8425, digit 0 is the 5, which is in the "ones place". Digit 1 is the 2, which is in the "tens place". Digit 2 is the 4, in the "hundreds place". Finally, digit 3 is the 8, in the "thousands place".

图 1. 十进制数中每一位数字的重要程度,用的是你在小学时可能用过的各位名称。

Figure 1. The importance of each digit in a base 10 number, using names that you may have given to each digit in grade school.

译注 · 图中内容

对于数 8425,第 0 位是 5,在「个位」;第 1 位是 2,在「十位」;第 2 位是 4,在「百位」;第 3 位是 8,在「千位」。

对于示例值 8425,「个」位上的 5 贡献 5(5 × 100),「十」位上的 2 贡献 20(2 × 101),「百」位上的 4 贡献 400(4 × 102),最后,「千」位上的 8 贡献 8000(8 × 103)。更正式地说,8425 可以表示为

For the example value 8425, the 5 in the “ones” place contributes 5 (5 × 100). The 2 in the “tens” place contributes 20 (2 × 101). The 4 in the “hundreds” place contributes 400 (4 × 102), and, finally, the 8 in the “thousands” place contributes 8000 (8 × 103). More formally, one could express 8425 as

原书旁注

(8 × 103)    +    (4 × 102)    +    (2 × 101)    +    (5 × 100)

这种对底数 10 施加递增指数的模式,正是它被称为十进制(base 10)数制的原因。从右到左给各位数字指定位置编号、从 d0 开始,意味着每一位数字 di 对总值的贡献为 10i(的倍数)。因此,任何 N 位十进制数的总值都可以表示为:

This pattern of increasing exponents applied to a base of 10 is the reason why it’s called a base 10 number system. Assigning position numbers to digits from right to left starting with d0 implies that each digit di contributes 10i to the overall value. Thus, the overall value of any N-digit decimal number can be expressed as:

原书旁注

(dN-1 × 10N-1)    +    (dN-2 × 10N-2)    +    …​    +    (d2 × 102)    +    (d1 × 101)    +    (d0 × 100)

幸运的是,我们很快会看到,其他数制也适用非常相似的模式。

Fortunately, as we’ll soon see, a very similar pattern applies to other number systems.

原书注 · 区分数的进制(Distinguishing Number Bases)

既然我们即将介绍第二种数制,一个潜在的问题是如何解释一个数可能不够清楚。例如,看看数值 1000。它应当被解释为十进制值(即一千),还是二进制值(即八,原因稍后解释),一时并不明显。为了表达清楚,本章其余部分会给所有非十进制的数显式地加上前缀。我们很快会介绍二进制,它的前缀是 0b;还有十六进制,它用前缀 0x。

因此,如果你看到 1000,应当认为它是十进制的「一千」;如果你看到 0b1000,应当把它解释为二进制数,这里的值是「八」。

Now that we’re about to introduce a second number system, one potential problem is a lack of clarity regarding how to interpret a number. For example, consider the value 1000. It’s not immediately obvious whether you should interpret that number as a decimal value (i.e., one thousand) or a binary value (i.e., eight, for reasons explained soon). To help clarify, the remainder of this chapter will explicitly attach a prefix to all nondecimal numbers. We’ll soon introduce binary, for which the prefix is 0b, and hexadecimal, which uses a prefix of 0x.

Therefore, if you see 1000, you should assume it’s a decimal “one thousand”, and if you see 0b1000, you should interpret it as a binary number, in this case the value “eight”.

4.1.2. 无符号二进制数

4.1.2. Unsigned Binary Numbers

你也许从未想过用 10 的幂来描述十进制数的具体公式,但{ 个、十、百…… }位的概念应该很熟悉。幸运的是,类似的术语也适用于二进制等其他数制。当然,其他数制的基数不同,所以每个数位对数值的贡献也不同。

While you may never have considered the specific formula describing decimal numbers as powers of 10, the concept of { ones, tens, hundreds, etc. } places should hopefully feel comfortable. Luckily, similar terminology applies to other number systems, like binary. Of course, the base is different in other number systems, so each digit position contributes a different amount to its numerical value.

二进制数制(binary number system)的基数是 2,而不是十进制的 10。用刚才分析十进制的方法来分析它,会发现几处相似之处(只是把 10 换成了 2):

A binary number system uses a base of 2 instead of decimal’s 10. Analyzing it the same way that we just did for decimal reveals several parallels (with 2 substituted for 10):

  1. 以 2 为基数的数中,任何一位都存储两个不同值(0 或 1)之一。要存储大于 1 的值,二进制编码就必须向左边多出来的一位进位。例如,如果某一位从它的最大值(1)开始,再加 1,结果就需要两位(1 + 1 = 0b10)。无论这一位在数中的什么位置,都遵循同样的模式(例如 0b100100 + 0b100 = 0b101000)。
  1. Any individual bit in a base 2 number stores one of two unique values (0 or 1). To store a value larger than 1, the binary encoding must carry to an additional bit to the left. For example, if one bit starts at its maximum value (1) and we add 1 to it, the result requires two bits (1 + 1 = 0b10). The same pattern holds for any bit, regardless of its position within a number (e.g., 0b100100 + 0b100 = 0b101000).
  1. 数中每一位的位置决定了这一位对数值的重要程度。把各位从右到左标记为 d0、d1、d2 等,每往左一位,贡献就比右边那一位大两倍。
  1. The position of each bit in the number determines how important that bit is to the numerical value of the number. Labeling the digits from right to left as d0, d1, d2, etc., each successive bit contributes a factor of two more than the next.

第一点意味着二进制计数与十进制遵循同样的模式:只需依次列举各个值,并按需增加数位(位)。由于本节关注的是无符号数(只有零和正数),从零开始数是很自然的。表 1 展示了如何用二进制数出前几个自然数。从表中可以看出,用二进制计数时位数增长得很快。直观上,这种增长是合理的,因为每个二进制数位(两个可能的值)所表示的信息比一个十进制数位(10 个可能的值)少。

The first point implies that counting in binary follows the same pattern as decimal: by simply enumerating the values and adding digits (bits). Because this section focuses on unsigned numbers (zero and positives only), it’s natural to start counting from zero. Table 1 shows how to count the first few natural numbers in binary. As you can see from the table, counting in binary quickly increases the number of digits. Intuitively, this growth makes sense, since each binary digit (two possible values) represents less information than a decimal digit (10 possible values).

表 1. 二进制计数与十进制计数的对比

Table 1. A Comparison of Counting in Binary versus Decimal

二进制值 十进制值
0 0
1 1
10 2
11 3
100 4
101 5
… …
Binary value Decimal value
0 0
1 1
10 2
11 3
100 4
101 5
…​ …​

关于标记数位的第二点看起来非常眼熟!事实上,它与十进制太相似了,以至于得出了几乎完全相同的二进制数解释公式。只需把每个指数的底数 10 换成 2:

The second point about labeling digits looks really familiar! In fact, it’s so similar to decimal that it leads to a nearly identical formula for interpreting a binary number. Simply replace the 10 at the base of each exponent with a 2:

原书旁注

(dN-1 × 2N-1)    +    (dN-2 × 2N-2)    +    …​    +    (d2 × 22)    +    (d1 × 21)    +    (d0 × 20)

应用这个公式,就能得到任何二进制数的无符号解释。例如,看看 0b1000:

Applying this formula yields the unsigned interpretation of any binary number. For example, take 0b1000:

原书旁注

(1 × 23)    +    (0 × 22)    +    (0 × 21)    +    (0 × 20)

  =    8 + 0 + 0 + 0    =    8

下面是一个更长的单字节例子,0b10110100:

Here’s a longer one-byte example, 0b10110100:

原书旁注

(1 × 27)    +    (0 × 26)    +    (1 × 25)    +    (1 × 24)    +    (0 × 23)    +    (1 × 22)    +    (0 × 21)    +    (0 × 20)

  =    128 + 0 + 32 + 16 + 0 + 4 + 0 + 0    =    180

4.1.3. 十六进制

4.1.3. Hexadecimal

到目前为止,我们考察了两种数制:十进制和二进制。十进制之所以重要,是因为它对人类来说用着顺手;而二进制则与硬件中存储数据的方式相吻合。要注意,两者的表达能力是等价的,也就是说,能用其中一种数制表示的数,都能用另一种表示。既然两者等价,我们还要再讨论一种数制——以 16 为基数的十六进制(hexadecimal)——这可能会让你感到意外。

Thus far, we’ve examined two number systems, decimal and binary. Decimal is notable due to its comfort for humans, whereas binary matches the way data is stored in hardware. It’s important to note that they are equivalent in their expressive power. That is, there’s no number you can represent in one system that you can’t represent in the other. Given their equivalence, it may surprise you that we’re going to discuss one more number system: the base 16 hexadecimal system.

已经有了两种完全够用的数制,你可能会问为什么还需要另一种。答案主要是为了方便。如表 1 所示,二进制位序列的位数增长得很快。人们往往很难理解只含 0 和 1 的长序列。而十进制虽然更紧凑,但它的基数 10 与二进制的基数 2 不匹配。

With two perfectly good number systems, you may wonder why we need another. The answer is primarily convenience. As shown in Table 1, binary bit sequences quickly grow to a large number of digits. Humans tend to have a tough time making sense of long sequences containing only 0’s and 1’s. And whereas decimal is more compact, its base of 10 is a mismatch with binary’s base 2.

十进制不容易体现出固定位数所能表示的范围。例如,假设一台老式计算机使用 16 位内存地址,它的有效地址范围是 0b0000000000000000 到 0b1111111111111111。用十进制表示,地址范围是 0 到 65535。显然,十进制表示比长长的二进制序列更紧凑,但除非你记住它们之间的换算,否则用十进制数来推理会更困难。在使用 32 位或 64 位地址的现代设备上,这两个问题都只会更糟!

Decimal doesn’t easily capture the range that can be expressed using a fixed number of bits. For example, suppose that an old computer uses 16-bit memory addresses. Its valid addresses range from 0b0000000000000000 to 0b1111111111111111. Represented in decimal, the addresses range from 0 to 65535. Clearly, the decimal representations are more compact than the long binary sequences, but unless you memorize their conversions, it’s more difficult to reason about the decimal numbers. Both problems only get worse on modern devices, which use 32- or 64-bit addresses!

面对这些长长的位序列,正是十六进制的基数 16 大显身手的时候。较大的基数让每一位数字能表示足够多的信息,使十六进制数很紧凑。此外,由于基数本身是 2 的幂(24 = 16),十六进制与二进制之间的相互转换很容易。为完整起见,我们用分析十进制和二进制的方法来分析十六进制:

These long bit sequences are where hexadecimal’s base 16 shines. The large base allows each digit to represent enough information for hexadecimal numbers to be compact. Furthermore, because the base is itself a power of two (24 = 16), it’s easy to map hexadecimal to binary, and vice versa. For the sake of completeness, let’s analyze hexadecimal in the same way as decimal and binary:

  1. 以 16 为基数的数中,任何一位数字都存储 16 个不同值之一。超过 10 个值给十六进制带来了一个新问题——传统的十进制数字最大只到 9。按照惯例,十六进制用字母表示大于 9 的值:A 表示 10,B 表示 11,一直到 F 表示 15。和其他数制一样,要存储大于 15 的值,就必须向左边多出来的一位进位。例如,如果某一位从它的最大值(F)开始,再加 1,结果就需要两位数字(0xF + 0x1 = 0x10;注意我们用 0x 表示十六进制数)。
  1. Any individual digit in a base 16 number stores one of 16 unique values. Having more than 10 values presents a new challenge for hexadecimal — traditional base 10 digits stop at a maximum value of 9. By convention, hexadecimal uses letters to represent values larger than 9, with A for 10, B for 11, up to F for 15. Like the other systems, to store a value larger than 15, the number must carry to an additional digit to the left. For example, if one digit starts at its maximum value (F) and we add 1 to it, the result requires two digits (0xF + 0x1 = 0x10; note that we use 0x to indicate hexadecimal numbers).
  1. 数中每一位数字的位置决定了这位数字对数值的重要程度。把各位数字从右到左标记为 d0、d1、d2 等,每往左一位,贡献就比右边那一位大 16 倍。
  1. The position of each digit in the number determines how important that digit is to the numerical value of the number. Labeling the digits from right to left as d0, d1, d2, etc., each successive digit contributes a factor of 16 more than the next.

毫不意外,那个可靠的解释公式同样适用于十六进制,只是基数换成了 16:

Unsurprisingly, the same trusty formula for interpreting a number applies to hexadecimal, with 16 as the base:

原书旁注

(dN-1 × 16N-1)    +    (dN-2 × 16N-2)    +    …​    +    (d2 × 162)    +    (d1 × 161)    +    (d0 × 160)

例如,求 0x23C8 的十进制值:

For example, to determine the decimal value of 0x23C8:

原书旁注

(2 × 163)    +    (3 × 162)    +    (C × 161)    +    (8 × 160)

  =    (2 × 163)    +    (3 × 162)    +    (12 × 161)    +    (8 × 160)

  =    (2 × 4096)    +    (3 × 256)    +    (12 × 16)    +    (8 × 1)

  =    8192 + 768 + 192 + 8    =    9160

原书警示 · 关于十六进制的误解(Hexadecimal Misconception)

刚开始学习系统编程时,你可能不会经常遇到十六进制数。实际上,你最可能见到它们的场合是表示内存地址。例如,如果用 printf 的 %p(指针)格式码打印变量的地址,得到的就是十六进制输出。

很多学生常常开始把内存地址(例如 C 指针变量)等同于十六进制。虽然你可能会习惯于看到以这种方式表示的地址,但要记住,它们在硬件中仍然以二进制存储,和所有其他数据一样!

You may not encounter hexadecimal numbers frequently as you’re first learning about systems programming. In fact, the only context where you’re likely to find them is in representing memory addresses. For example, if you print the address of a variable using the %p (pointer) format code for printf, you’ll get hexadecimal output.

Many students often begin to equate memory addresses (e.g., C pointer variables) with hexadecimal. While you may get used to seeing addresses represented that way, keep in mind that they are still stored using binary in the hardware, just like all other data!

4.1.4. 存储的限制

4.1.4. Storage Limitations

从概念上讲,无符号整数有无穷多个。实际上,出于多种原因,程序员必须在存储一个值之前就选定要为变量分配多少位:

Conceptually, there are infinitely many unsigned integers. In practice, a programmer must choose how many bits to dedicate to a variable prior to storing it, for a variety of reasons:

  • 在存储一个值之前,程序必须为它分配存储空间。在 C 中,声明一个变量就是根据它的类型告诉编译器它需要多少内存。
  • Before storing a value, a program must allocate storage space for it. In C, declaring a variable tells the compiler how much memory it needs based on its type.
  • 硬件存储设备的容量是有限的。系统的主存通常很大,不太可能成为限制因素,但 CPU 内部用作临时「草稿空间」的存储位置(即寄存器)就受限得多。CPU 使用的寄存器大小受限于它的字长(通常是 32 或 64 位,取决于 CPU 体系结构)。
  • Hardware storage devices have finite capacity. Whereas a system’s main memory is typically large and unlikely to be a limiting factor, storage locations inside the CPU that are used as temporary “scratch space” (i.e., registers) are more constrained. A CPU uses registers that are limited to its word size (typically 32 or 64 bits, depending on the CPU architecture).
  • 程序经常把数据从一个存储设备移到另一个(例如在 CPU 寄存器和主存之间)。值越大,存储设备之间就需要越多的导线来传递信号。因此,扩大存储会增加硬件的复杂度,并给其他部件留下更少的物理空间。
  • Programs often move data from one storage device to another (e.g., between CPU registers and main memory). As values get larger, storage devices need more wires to communicate signals between them. Hence, expanding storage increases the complexity of the hardware and leaves less physical space for other components.

存储一个整数所用的位数决定了它可表示值的范围。图 2 描绘了我们可以如何理解无限的和有限的无符号整数存储空间。

The number of bits used to store an integer dictates the range of its representable values. Figure 2 depicts how we might conceptualize infinite and finite unsigned integer storage spaces.

The infinite unsigned number line starts at zero and increases infinitely. The finite unsigned number line starts at 0 and ends at a maximum value. Attempting to move off one end wraps around to the other.

图 2. (a) 无限的无符号数轴和 (b) 有限的无符号数轴示意图。后者在两端都会「回绕」(溢出)。

Figure 2. Illustrations of (a) an infinite unsigned number line and (b) a finite unsigned number line. The latter “wraps around” at either endpoint (overflow).

试图把大于变量大小所允许范围的值存入变量,称为整数溢出(integer overflow)。本章把溢出的细节留到后面的一节。目前,可以把它想象成汽车的里程表:当它试图超过最大值时,就会「翻转」回零。类似地,零减一会得到最大值。

Attempting to store a larger value to a variable than the variable’s size allows is known as integer overflow. This chapter defers the details of overflow to a later section. For now, think of it like a car’s odometer that “rolls over” back to zero if it attempts to increase beyond its maximum value. Similarly, subtracting one from zero yields the maximum value.

到这里,关于无符号二进制数,一个自然的问题是:「N 位能存储的最大正数是多少?」换句话说,给定一个全为 1 的 N 位序列,这个序列表示什么值?非正式地推理一下这个问题:上一节的分析表明,N 位可以产生 2N 个不同的位序列。由于其中一个序列必须表示数 0,剩下的 2N - 1 个序列表示从 1 到 2N - 1 的正值。因此,N 位无符号二进制数的最大值必然是 2N - 1。

At this point, a natural question to ask about unsigned binary is “What’s the largest positive value that N bits can store?“ In other words, given a sequence of N bits that are all 1, what value does the sequence represent? Reasoning about this question informally, the analysis in the previous section shows that N bits yield 2N unique bit sequences. Since one of those sequences must represent the number 0, that leaves 2N - 1 positive values ranging from 1 to 2N - 1. Thus, the maximum value for an unsigned binary number of N bits must be 2N - 1.

例如,8 位提供 28 = 256 个不同的序列。其中一个序列 0b00000000 留给 0,剩下 255 个序列用于存储正值。因此,一个 8 位变量可以表示 1 到 255 的正值,其中最大的是 255。

For example, 8 bits provide 28 = 256 unique sequences. One of those sequences, 0b00000000, is reserved for 0, leaving 255 sequences for storing positive values. Therefore, an 8-bit variable represents the positive values 1 through 255, the largest of which is 255.