本节书摘来自异步社区《计算机科学概论(第12版)》一书中的第1章1.5节二进制系统,作者【美】J. 格伦•布鲁克希尔(J. Glenn *shear) , 丹尼斯•布里罗(Dennis Brylow),更多章节内容可以访问云栖社区“异步社区”公众号查看。
1.5 二进制系统
在1.4节中我们看到,二进制记数法是表示数字值的一种方法,它只使用数字0和1,而不用较常见的十进制记数系统中的10个数字0到9。现在,我们来深入了解一下二进制记数法。
1.5.1 二进制记数法
回顾十进制系统,表示中的每一个位置都与一个量值相关联。在375这个表示中,5的位置与量1相关联,7的位置与量10相关联,3的位置与量100相关联(见图1-13a)。每一个量值是它右边量值的10倍。整个表达式代表的数值是,每一个数字值与其位置的量值相乘所得积之和。举例说明:模式375表示(3×100)+(7×10)+(5×1),用更加技术性的表示法表示就是(3×102)+(7×101)+(5×100)。
在二进制记数法中,每个数字的位置也与一个量值相关联,只是与每个位置相关联的那个量值是它右边量值的两倍。更精确地说,在二进制表示中,最右边的数字与量值1(即20)相关联,其左边的下一个位置与量值2(即21)相关联,下一个与量值4(即22)相关联,再下一个与量值8(即23)相关联,依次类推。例如,在二进制表示1011中,最右边1的位置与量值1相关联,接下来一个1的位置与量值2相关联,0的位置与量值4相关联,最左边1的位置与量值8相关联(见图1-13b)。
为了求得二进制表示所表示的数值,我们可以采取和十进制相同的步骤:先求得每个数字值与其量值的积,再计算各个乘积之和。例如,100101表示的数值是37,如图1-14所示。需要注意的是,因为二进制记数法仅使用数字0和1,这种求积再求和的步骤就可以简化为求数字值为1的位置对应的量值的和。因此,二进制模式1011表示的是十进制数值11,因为3个1的位置分别与量值1、2和8相关联。
在1.4节中,我们学习了如何用二进制记数法计数,这就使得我们可以对小整数进行编码。为了求得大数值的二进制表示,你可能更倾向于图1-15所描述的算法。让我们利用这个算法来求十进制数值13的二进制表示(见图1-16)。首先,将13除以2,得到商数6和余数1。因为这个商不是0,步骤2告诉我们还要在商数(6)的基础上除以2,得到新的商数3和余数0。最新的商数仍然不为0,所以再除以2,得出商数1和余数1。再一次,将最新的商数(1)除以2,此时得到商数0和余数1。因为现在的商数是0,我们进入步骤3,从余数列中得到原数(13)的二进制表示1101。
1.5.2 二进制加法
为了理解两个用二进制表示的整数的相加过程,首先让我们回顾一下用传统十进制记数法表示的数值的相加过程。例如,考虑下面的问题:
我们先把最右列的8和7相加,得到和15,我们把5记录在这一列的底部,进位1放到下一列中,得到:
现在我们把下一列的5和2相加,并加上进位到这一列的1,得到和8,我们把8记录在这一列的底部,得到:
总之,这个过程就是从右到左相加每一列中的数字,把和中的最低有效位写在列的底部,把和的较高有效位(如果有)进位到下一列。
为了将两个用二进制表示的正整数相加,我们遵照相同的过程,只是所有和的计算都使用图1-17中显示的加法规则,而不是你在小学所学的传统的十进制加法法则。例如,为了解决问题:
首先将最右边的0和1相加,得到1,写于该列下方。接着将下一列的1和1相加,得到10。把其中的0写于该列下方,将1记在了下一列的上面。这时,加法如下:
把下一列的1、0和0相加,得到1,将1写于该列下方。下一列的1和1总和为10,将0写于该列下方,将1记于下一列。这时,加法如下:
下一列的1、1和1总和为11(数值3的二进制表示),将低位1写于该列下方,并将另外一个1写在下一列的上面。把那个1与那列原本的1相加,得到10。再一次,在该列下方写下低位0,并将1写在下一列的上面。现在得到
下一列的唯一项就是1,是上一列进过来的,所以我们将其记录为答案。最终的结果是:
1.5.3 二进制中的小数
为了扩展二进制记数法,使其包含小数数值,我们使用了小数点(radix point),其功能与十进制记数法中的十进制小数点是相同的,即小数点左边的数字代表数值的整数部分(整个部分),其解释和前面讨论的二进制系统一样。小数点右边的数字代表数值的小数部分,其解释和其他二进制位类似,只是它们的位置被赋予了小数的量值。更确切地说,小数点右边第一位的量值是$\frac{1}{2}$(即2-1),下一位的量值是$\frac{1}{4}$(即2-2),再下一位是$\frac{1}{8}$(即2-3),依次类推。需要注意的是,这仅仅是前面所述规则的延续:即每位所被赋予的量值是它右边大小的两倍。利用这些赋予二进制位位置的量值,对包含小数点和不包含小数点的二进制表示进行解码的步骤基本是相同的。更精确地说,我们是把表示中每一个位值与其对应位位置的量值相乘。举例来说,二进制表示101.101的解码为$5\frac{5}{8}$,如图1-18所示。
另外,应用于十进制系统的加法技术同样适用于二进制系统,即两个有小数点的二进制表示相加时,我们只需要对齐小数点,然后应用前面介绍的加法步骤进行计算即可。例如,10.011加100.11得111.001,如下所示:
问题与练习
1.将下列二进制表示转换为相应的十进制形式。
- 101010 b. 100001 c. 10111 d. 0110 e. 11111
2.将下列十进制表示转换为相应的二进制形式。
- 32 b. 64 c. 96 d. 15 e. 27
3.将下列二进制表示转换为相应的十进制形式。
- 11.01 b. 101.111 c. 10.1 d. 110.011 e. 0.101
4.用二进制记数法表示下列数值。
- 4frac{1}{2} b.2frac{3}{4} c. 1frac{1}{8} d. frac{5}{16} e. 5frac{5}{8}
5.按照二进制记数法做下列加法。
a.11011 b. 1010.001 c.11111 d. 111.11
+ 1100 + 1.101 + 0001 + 00.01