2.2　二进制和十进制的数学等价性

在2.1节中，你已经看到了二进制数码是表示计算机内部开关状态的一种自然方式。此外你还得知，我们可以使用单个十六进制数码来表示4个开关的状态。本节将介绍二进制数字系统的一些数学特性，并说明它是如何与更熟悉的十进制（基数为10）数字系统进行转换的。

2.2.1　了解位置记数法

依据惯例，我们在书写数字的时候依据的是位置记数法（positional notation）。这意味着符号的值取决于其在一组符号中的位置。在熟悉的十进制数字系统中，我们使用符号0,1,…,9表示数字。

对于数字50，符号5的值是50，因为其位于十位，位于该位的任意数字都要乘以10。对于数字500，符号5的值是500，因为其位于百位。符号5在任意位置都是一个样子，但它的值则取决于其在数字中的位置。

再进一步说，在十进制数字系统中，整数123可以被认为是

1 × 100 + 2 × 10 + 3

或者

1 × 10 ² + 2 × 10 ¹ + 3 × 10 ⁰

在这个例子中，最右侧的数码3是最低有效数码（least significant digit），因为它的值对于整个数字的值贡献最小。最左侧的数码1则是最高有效数码（most significant digit），因为它贡献了最多的值。

十进制数字系统的基数或底数（数码可用的符号数量）是10。这意味着表示数码0～9的符号共计10个。将数码向左移动一位会使其值扩大10倍；将它向右移动一位，其值会变为原来的1/10。位置记数法可以推广到任何基数 r ，如下所示：

其中，数字共有 n 个数码，每个 d _i 代表单个数码（0≤ d _i < r ）。

这个表达式告诉了我们如何确定数字中每个数码的值。从右开始累计每个数码在数字中的位置，初始值为0。在每个位置，我们将基数 r 提升为该位置的幂，然后将得数乘以数码的值。将所有结果相加就得到了此数字所表示的值。

二进制数字系统的基数为2，所以表示数码的只有两个符号。这意味着 d _i =0或1，我们可以将上述表达式写作：

其中，数字共有 n 个数码，每个 d _i =0或1。

在2.2.2节中，我们将介绍如何在二进制数和无符号十进制数之间进行转换。有符号数可以是正数或负数，但是无符号数没有符号。我们将在第3章讨论有符号数。

2.2.2　将二进制数转换为无符号十进制数

通过计算特定位置上的2的幂，然后乘以该位置的比特值，就可以轻松地将二进制数转换为十进制数。来看一个例子：

以下算法总结了二进制到十进制的转换过程：

   Let result = 0
➊ Repeat for each i = 0,...,(n - 1)
       add ➋di x ➌2i to result

在每个比特位置➊，该算法计算2的幂➌并乘以该位置上的比特值（0或1）➋。

注意

虽然我们现在只考虑整数，但是该算法确实可以推广到小数值。只需让基数 r 的指数继续变成负值即可，也就是 r ^{n - 1} , r ^{n - 2} ,…, r ¹ , r ⁰ , r ^{- 1} , r ^{- 2} ,…。详细讨论参见第19章。

2.2.3　将无符号十进制数转换为二进制数

如果我们想把一个无符号的十进制整数 N 转换为二进制数，设其等于先前的二进制数表达式，得到以下等式：

其中， d _i =0或1。我们将等式两边除以2，右边底数为2的各项指数减1，于是得到以下结果：

其中， N ₁ 是整数部分，如果是偶数，余数 r ₀ 为0；如果是奇数，则为1。稍作改写，得到以下等价等式：

右边括号内的所有项都是整数。等式两边的整数部分和小数部分必须分别相等。也就是：

且

因此，我们看到 d ₀ = r ₀ 。从展开的等式的两边减去 r ₀ /2（等于 d ₀ /2），得到以下结果：

两边再除以2：

使用与前面相同的推理， d ₁ = r ₁ 。我们可以通过从右到左反复除以2，并使用余数作为相应位的值，以此产生一个数的二进制表示。这个过程可以总结为以下算法，其中正斜线（/）是整数除法运算符，百分号（%）是模运算符：

quotient = N
i = 0
di = quotient % 2
quotient = quotient / 2
While quotient != 0
    i = i + 1
    di = quotient % 2
    quotient = quotient / 2

一些编程任务（例如，硬件设备编程）需要特定的位模式。在这种情况下，使用位模式代替数值更为自然。我们可以将4位分成一组，用十六进制来表示每一组。例如，如果我们的算法要求0和1交错出现（0101 0101 0101 0101 0101 0101 0101 0101），我们可以将其转换为十进制值431655765，或者用十六进制表示为0x55555555（C/C++语法中的显示）。一旦记住了表2-1，你就会发现用十六进制来表示位模式要容易得多。

这两节的讨论只涉及无符号整数。有符号整数的表示方法依赖于CPU的某些架构特性，我们留待第3章讨论。