第 45 / 187 篇

4.2. 进制之间的转换

说明

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

4.2. Converting Between Bases

在不同的场合,你很可能会遇到本章介绍的这三种进制中的每一种。有时你可能需要把数从一种进制转换成另一种进制。本节首先介绍二进制和十六进制之间的转换,因为这两者很容易相互对应。之后,我们再探讨与十进制之间的相互转换。

You’re likely to encounter each of the three number bases we’ve introduced in this chapter in different contexts. In some cases, you may need to convert from one base to another. This section starts by showing how to convert between binary and hexadecimal, since those two map easily to each other. After that, we’ll explore conversions to and from decimal.

4.2.1. 二进制与十六进制之间的转换

4.2.1. Converting Between Binary and Hexadecimal

由于二进制和十六进制的基数都是 2 的幂,两者之间的转换相对简单。具体来说,每个十六进制数字可以取 16 个不同值之一,而四位也可以表示 24 = 16 个不同的值,所以两者的表达能力相当。表 1 列举了任意四位序列与单个十六进制数字之间的一一对应关系。

Because the bases for both binary and hexadecimal are powers of 2, converting between the two is relatively straightforward. Specifically, each hexadecimal digit holds one of 16 unique values, and four bits also represents 24 = 16 unique values, making their expressive power equivalent. Table 1 enumerates the one-to-one mapping between any sequence of four bits and any single hexadecimal digit.

表 1. 所有四位序列与一位十六进制数之间的对应关系

Table 1. The Correspondence Between All Four-Bit Sequences and One-Digit Hexadecimal Numbers

Binary Hexadecimal Binary Hexadecimal
0000 0 1000 8
0001 1 1001 9
0010 2 1010 A
0011 3 1011 B
0100 4 1100 C
0101 5 1101 D
0110 6 1110 E
0111 7 1111 F

注意,表 1 的内容相当于在两种数制中分别从 0 数到 15,所以不必死记。有了这个对应关系,就可以把任意多个连续的位或十六进制数字往任一方向转换:

Note that the content of Table 1 is equivalent to simply counting from 0 to 15 in both number systems, so there’s no need to memorize it. Armed with this mapping, you can convert any number of consecutive bits or hex digits in either direction:

  • 把 0xB491 转换为二进制,只需把每个十六进制数字替换为对应的二进制值:

    1
    2
      B    4    9    1
    1011 0100 1001 0001 -> 0b1011010010010001
  • Converting 0xB491 to binary, simply substitute the corresponding binary value for each hexadecimal digit:

    1
    2
      B    4    9    1
    1011 0100 1001 0001 -> 0b1011010010010001
  • 把 0b1111011001 转换为十六进制,先从右到左把位分成四位一组。如果最左边的一组不足四位,可以在前面补零。然后替换为对应的十六进制值:

    1
    2
    3
    4
    5
    1111011001  ->  11 1101 1001  ->  0011 1101 1001
    ^ padding

    0011 1101 1001
    3 D 9 -> 0x3D9
  • Converting 0b1111011001 to hexadecimal, first divide up the bits into chunks of four, from right to left. If the leftmost chunk doesn’t have four bits, you can pad with leading zeros. Then, substitute the corresponding hexadecimal values:

    1
    2
    3
    4
    5
    1111011001  ->  11 1101 1001  ->  0011 1101 1001
    ^ padding

    0011 1101 1001
    3 D 9 -> 0x3D9

4.2.2. 转换为十进制

4.2.2. Converting to Decimal

幸运的是,把数值转换为十进制正是我们在本章前面几节中一直在做的事。对于以任意基数 B 表示的数,把各位数字从右到左标记为 d0、d1、d2 等,就能得到把数值转换为十进制的通用公式:

Fortunately, converting values to decimal is what we’ve been doing throughout previous sections of this chapter. Given a number in any base B, labeling the digits from right to left as d0, d1, d2, etc. enables a general formula for converting values to decimal:

原书旁注

(dN-1 × BN-1)    +    (dN-2 × BN-2)    +    …​    +    (d2 × B2)    +    (d1 × B1)    +    (d0 × B0)

4.2.3. 从十进制转换

4.2.3. Converting from Decimal

从十进制转换为其他数制需要多花一点工夫。非正式地说,目标是做前面那个公式的逆运算:确定每一位数字的值,使得按数字所在位置算出的各项相加后,正好等于原来的十进制数。可以像我们描述十进制的各个位(「个」位、「十」位等)那样,来思考目标数制中的每一位数字。例如,考虑把十进制转换为十六进制。十六进制数的每一位都对应一个越来越大的 16 的幂,表 2 列出了前几个幂。

Converting from decimal to other systems requires a little more work. Informally, the goal is to do the reverse of the previous formula: determine the value of each digit such that, based on the position of the digit, adding each term results in the source decimal number. It may help to think about each digit in the target base system in the same way that we described the places (the “ones” place, the “tens” place, etc.) for decimal. For example, consider converting from decimal to hexadecimal. Each digit of a hexadecimal number corresponds to an increasingly large power of 16, and Table 2 lists the first few powers.

表 2. 16 的幂

Table 2. Powers of 16.

164 163 162 161 160
65536 4096 256 16 1

例如,要把 9742 转换为十六进制,可以这样考虑:

For example, to convert 9742 to hexadecimal, consider:

  • 9742 中能容纳多少个 65536?(换句话说,「65536 位」的值是多少?)

    得到的十六进制值不需要任何 65536 的倍数,因为这个值(9742)小于 65536,所以 d4 应当设为 0。注意,按照同样的道理,所有更高编号的数位也都是 0,因为每一位贡献的值都会比 65536 还大。到目前为止,结果只有:

    0
    d4 d3 d2 d1 d0
  • How many multiples of 65536 fit into 9742? (In other words, what is the value of the “65536’s” place?)

    The resulting hexadecimal value doesn’t need any multiples of 65536, since the value (9742) is smaller than 65536, so d4 should be set to 0. Note that by the same logic, all higher-numbered digits will also be 0, because each digit would contribute values even larger than 65536. Thus far, the result contains only:

    0
    d4 d3 d2 d1 d0
  • 9742 中能容纳多少个 4096?(换句话说,「4096 位」的值是多少?)

    9742 中能容纳两个 4096(2 × 4096 = 8192),所以 d3 的值应当是 2。于是 d3 对总值贡献 8192,结果还需要表示 9742 - 8192 = 1550。

    0 2
    d4 d3 d2 d1 d0
  • How many multiples of 4096 fit into 9742? (In other words, what is the value of the “4096’s” place?)

    4096 fits into 9742 twice (2 × 4096 = 8192), so the value of d3 should be 2. Thus, d3 will contribute 8192 to the overall value, so the result must still account for 9742 - 8192 = 1550.

    0 2
    d4 d3 d2 d1 d0
  • 1550 中能容纳多少个 256?(换句话说,「256 位」的值是多少?)

    1550 中能容纳六个 256(6 × 256 = 1536),所以 d2 的值应当是 6,还剩 1550 - 1536 = 14。

    0 2 6
    d4 d3 d2 d1 d0
  • How many multiples of 256 fit into 1550? (In other words, what is the value of the “256’s” place?)

    256 fits into 1550 six times (6 × 256 = 1536), so the value of d2 should be 6, leaving 1550 - 1536 = 14.

    0 2 6
    d4 d3 d2 d1 d0
  • 14 中能容纳多少个 16?(换句话说,「十六位」的值是多少?)

    一个也没有,所以 d1 必然是 0。

    0 2 6 0
    d4 d3 d2 d1 d0
  • How many multiples of 16 fit into 14? (In other words, what is the value of the “sixteens” place?)

    None, so d1 must be 0.

    0 2 6 0
    d4 d3 d2 d1 d0
  • 最后,14 中能容纳多少个 1?(换句话说,「个位」的值是多少?)

    答案当然是 14,在十六进制中用数字 E 表示。

    0 2 6 0 E
    d4 d3 d2 d1 d0
  • Finally, how many multiples of 1 fit into 14? (In other words, what is the value of the “ones” place?)

    The answer is 14, of course, which hexadecimal represents with the digit E.

    0 2 6 0 E
    d4 d3 d2 d1 d0

因此,十进制的 9742 对应于 0x260E。

Thus, decimal 9742 corresponds to 0x260E.

十进制转二进制:2 的幂

Decimal to Binary: Powers of Two

只要使用相应基数的幂,同样的步骤也适用于二进制(或任何其他数制)。表 3 列出了 2 的前几个幂,借助它把示例十进制值 422 转换为二进制。

The same procedure works for binary, as well (or any other number system), provided that you use powers of the appropriate base. Table 3 lists the first few powers of two, which will help to convert the example decimal value 422 to binary.

表 3. 2 的幂

Table 3. Powers of Two

28 27 26 25 24 23 22 21 20
256 128 64 32 16 8 4 2 1

由于单独一位只能存储 0 或 1,转换为二进制时,问题不再是「这个值中能容纳多少个某次幂?」,而是一个更简单的问题:「下一个 2 的幂能不能放得下?」例如,转换 422 时:

Because an individual bit is only allowed to store a 0 or 1, the question is no longer “How many multiples of each power fit within a value?” when converting to binary. Instead, ask a simpler question: “Does the next power of two fit?” For example, in converting 422:

  • 422 中放得下 256,所以 d8 应当是 1,还剩 422 - 256 = 166。
  • 256 fits into 422, so d8 should be a 1. That leaves 422 - 256 = 166.
  • 166 中放得下 128,所以 d7 应当是 1,还剩 166 - 128 = 38。
  • 128 fits into 166, so d7 should be a 1. That leaves 166 - 128 = 38.
  • 38 中放不下 64,所以 d6 应当是 0。
  • 64 does not fit into 38, so d6 should be a 0.
  • 38 中放得下 32,所以 d5 应当是 1,还剩 38 - 32 = 6。
  • 32 fits into 38, so d5 should be a 1. That leaves 38 - 32 = 6.
  • 6 中放不下 16,所以 d4 应当是 0。
  • 16 does not fit into 6, so d4 should be a 0.
  • 6 中放不下 8,所以 d3 应当是 0。
  • 8 does not fit into 6, so d3 should be a 0.
  • 6 中放得下 4,所以 d2 应当是 1,还剩 6 - 4 = 2。
  • 4 fits into 6, so d2 should be a 1. That leaves 6 - 4 = 2.
  • 2 中放得下 2,所以 d1 应当是 1,还剩 2 - 2 = 0。(注意:一旦减到 0,其余所有数位都必然是 0。)
  • 2 fits into 2, so d1 should be a 1. That leaves 2 - 2 = 0. (Note: upon reaching 0, all remaining digits will always be 0.)
  • 0 中放不下 1,所以 d0 应当是 0。
  • 1 does not fit into 0, so d0 should be a 0.

因此,十进制的 422 对应于 0b110100110。

Thus, decimal 422 corresponds to 0b110100110.

十进制转二进制:反复除以 2

Decimal to Binary: Repeated Division

对于熟悉相关 2 的幂的学生,我们刚才描述的方法通常很好用(例如对于 422,做转换的人必须认识到应当从 d8 开始,因为 29 = 512 太大了)。

The method we just described generally works well for students who are familiar with the relevant powers of two (e.g., for 422, the converter must recognize that it should start at d8 because 29 = 512 is too large).

另一种方法不需要知道 2 的幂。这种方法通过检查十进制数的奇偶性,并反复把它除以 2(舍去余数)来逐位确定结果,从而构建出二进制结果。注意它是从右到左构建结果位序列的。如果十进制值是偶数,下一位就是 0;如果是奇数,下一位就是 1。当除法得到零时,转换就完成了。

An alternative method doesn’t require knowing powers of two. Instead, this method builds a binary result by checking the parity (even or odd) status of a decimal number and repeatedly dividing it by two (rounding halves down) to determine each successive bit. Note that it builds the resulting bit sequence from right to left. If the decimal value is even, the next bit should be a zero; if it’s odd, the next bit should be a one. When the division reaches zero, the conversion is complete.

例如,转换 422 时:

For example, when converting 422:

  • 422 是偶数,所以 d0 应当是 0。(这是最右边的位。)
  • 422 is even, so d0 should be a 0. (This is the rightmost bit.)
  • 422 / 2 = 211,是奇数,所以 d1 应当是 1。
  • 422 / 2 = 211, which is odd, so d1 should be a 1.
  • 211 / 2 = 105,是奇数,所以 d2 应当是 1。
  • 211 / 2 = 105, which is odd, so d2 should be a 1.
  • 105 / 2 = 52,是偶数,所以 d3 应当是 0。
  • 105 / 2 = 52, which is even, so d3 should be a 0.
  • 52 / 2 = 26,是偶数,所以 d4 应当是 0。
  • 52 / 2 = 26, which is even, so d4 should be a 0.
  • 26 / 2 = 13,是奇数,所以 d5 应当是 1。
  • 26 / 2 = 13, which is odd, so d5 should be a 1.
  • 13 / 2 = 6,是偶数,所以 d6 应当是 0。
  • 13 / 2 = 6, which is even, so d6 should be a 0.
  • 6 / 2 = 3,是奇数,所以 d7 应当是 1。
  • 6 / 2 = 3, which is odd, so d7 should be a 1.
  • 3 / 2 = 1,是奇数,所以 d8 应当是 1。
  • 3 / 2 = 1, which is odd, so d8 should be a 1.
  • 1 / 2 = 0,所以第九位及以上的所有数位都是 0,算法结束。
  • 1 / 2 = 0, so any digit numbered nine or above will be 0, and the algorithm terminates.

正如预期,这种方法得出了相同的二进制序列:0b110100110。

As expected, this method produces the same binary sequence: 0b110100110.