第1章 预备知识,1.1 计算机内的数据表示 1.2 数的定点和浮点表示 1.3 简单的逻辑运算 1.4 程序的概念 1.5 算法 习题1,1.1 计算机内的数据表示 数据形态多种多样，凡是计算机能够处理的对象都称为数据，如文字数据、图形数据、声音数据等。但不管其表象多么复杂，多么千差万别，只要一归入计算机处理，都全部地统一为二进制数据，也就是说，数据在计算机内是以二进制(即用数字 0 和 1)来表示的。,在计算机中为什么要采用二进制? 采用二进制有哪些优点? 以下就是问题的答案。 (1) 用二进制表示数字在物理上容易实现。计算机内部用电子器件的状态来表示数字信息。一种数制有多少种不同的数字，电子器件就需要多少种不同的状态。二进制只有数字 0 和 1，因此它只需要由两个稳定状态的电子元件来表示，而十进制则需要由 10 个不同稳定状态的电子元件来表示。显然对电子元件的制造来讲，用二进制要简单，如开关的接通与断开，晶体管的导通与截止，都可以由 0 和 1 两个数字表示。因此用二进制表示数字，数字的状态少，工作可靠。,(2) 二进制运算规则简单。 二进制求和的规则有： 0+0=0 0+1=1+0=1 1+1=10 二进制求积的规则有： 00=0 01=10=0 11=1 一般地，若一种数制中有n个不同的数字，则根据排列组合的法则可知，其求和与求积各需要n(n+1)/2条不同的规则。按这一公式计算，对十进制求和与求积就需要 55 条规则。,(3) 采用二进制可以用逻辑代数作为设计分析的工具。二进制中用 0 和1 可以表示是与非、高与低等，这恰恰是逻辑代数中的内容。 (4) 用二进制可以节约存储设备。比如要表示 0999 这 1000 个数时，十进制要用3位数，需310=30个状态设备量，而用10位二进制数表示时，只需210=20个状态设备量。,1.1.1 数的二进制、十进制、八进制和十六进制表示 常用的数制有二进制、十进制、八进制和十六进制，它们有共性也有差别。 1. 数码及进位法则 数码是构造一种数制所用的不同符号。各种进制的数码为： 二进制：0，1 十进制：0，1，2，3，4，5，6，7，8，9 八进制：0，1，2，3，4，5，6，7 十六进制：0，1，2，3，4，5，6，7，8，9，A(a), B(b), C(c), D(d), E(e), F(f),在十六进制中有16个数码，但自 10 起就没有相应的阿拉伯数字可以使用了，所以用字母A、B、C、D、E、F(大小写均可)来表示 10、11、12、13、14、15。 各种数制的共性是：N进制中的最大数码比N少1； 在N进制中，逢N进1，借1当N。,2. 位置计数法 数据中各个数字所处的位置决定它的大小(即权值)，同样的数字在不同位置上代表的权值是不同的。比如： 22.2=2101+2100+2101 其中，101、100、101就是各位置的权值。 采用位置计数法的任何数制都可以表示成多项式的形式。如有数据 N=KnKn-1K1K0K1K2Km,可以表示成： 这里，Ni为整数部分； Nf为小数部分； x为基数，可以是2、8、10、16等。 二进制、十进制、八进制和十六进制都采用位置计数法。,1.1.2 数制转换 我们日常习惯使用的是十进制，但在计算机中使用的却是二进制，所以需要把十进制转换成二进制。但二进制书写麻烦，因此通常用八进制和十六进制表示，这样就存在各种数制之间的转换问题。,1. 将十进制转换成二进制 把十进制的整数和小数转换成二进制时所用的方法不同，因此应该分别进行转换。 (1) 用余数法将十进制整数转换成二进制整数。把十进制整数不断地用 2 去除，将所得到的余数 0 或 1 依次记为K0, K1, K2, ，直到商是 0 为止，将最后一次所得的余数记为Kn，则KnKn-1K1K0即为该整数的二进制表示。 在演算过程中可用竖式形式，也可用线图形式。,【例 1-2】 把0.47 转换成二进制。 用线图形式可演算如下： 0.470.940.880.760.520.04 2 整数 0 1 1 1 1 K1K2 K3 K4K5 在取 5 位小数时有 (0.47)10=(0. K1K2K3K4K5)2=(0.01111)2 (3) 在把十进制转换成二进制时，熟记一些 2 的幂次的十进制及二进制值能加快转换速度。表1-1 中列出了一些 2 的幂次所对应的十进制和二进制数。,在转换时，可找出小于但最接近于该十进制整数的某个2 的幂次，减去这个幂次，再在减后的数中找小于且最接近于该数的 2 的幂次。2 的n次方的二进制数的特点是 1 后跟有n个 0，利用这一点就能迅速地确定二进制数的长度，然后在相应的位置上填上 1 或 0 即可。例如： (1287.25)10=1024+256+4+2+1+0.25 =210+28+22+21+20+22 =(10000000000+100000000+100+10+1+0.01)2 =(10100000111.01)2 如果一个数比 1024 大很多，则可求出该数对 1024 的倍数，把倍数用 2 的幂次之和的形式表示，再与210相乘。,【例 1-3】 (30 000)10=( )2。 计算30 000除以 1024 得商 29，余数为304，将商和余数分别用 2 的幂次之和的形式表示： 商：29=16+8+4+1=24+23+22+20 余数：304=256+32+16=28+25+24 则 (30 000)10=102429+304=210(24+23+22+20)+28+25+24 =214+213+212+210+28+25+24 =(111010100110000)2 2. 将二进制转换成十进制 把二进制数按多项式展开求和即可得到其十进制表示。例如： (101.101)2=(122+021+120+12-1+02-2+12-3)10 =(14+11+10.5+10.125)10 =(5.625)10,1.1.3 原码、反码和补码 在计算机中，位(bit)是最小的单位，通常用来表示由二进制位组成的信息长度； 把 8 位二进制位定义为一个字节(byte)，计算机中的存储量就是按字节来计算的； 计算机内部数据处理的基本单位称为字(word)，它通常也是输入/输出设备和存储器之间传递数据的基本单位，每个字所包含的位数称为字长。 在计算机中，不仅数值用 0 和 1 表示，而且正负号也用 0 和1 表示。一般规定一个存储单元的最高位(最左边的一位)为符号位，如该位是 0 表示正，该位是 1 表示负。 在计算机中，带符号的数通常有三种表示方法：原码、反码和补码。为简单起见，下面我们只考虑用一个字节表示整数时的原码、反码和补码。,1. 原码 原码是一种机器数，原码表示法就是在机器中最高位用 0 表示正数，用 1 表示负数，而其余位表示数本身。例如： +15的原码为： 00001111 代表正 15的原码为：10001111 代表负 +0的原码为：00000000 0的原码为：10000000 同一个 0 在计算机中有不同的表示，这不适合计算机的运算。,2. 反码 在反码表示法中，正、负数的表示是不同的。正数的反码和原码是一样的，如+15的反码仍然是00001111。负数的反码为符号位是 1、其他各位是对原码求反，如15的反码为11110000。数值 0 的反码有两种：+0的反码为00000000， 0的反码为11111111。即在反码表示法中，0 的表示仍然不惟一。,3. 补码 鉴于以上情况，计算机内部采用补码方法来表示数值。采用补码方法的好处是可以简化设计与计算，把减运算转变为加运算来进行。 我们以时钟为例来说明补码的原理。比如现在的标准时间是 6 点，而你的表停在 11 点的位置，如图 1-1 所示。要调准你的表可用两种方法： 向前拨 7 格； 向后拨 5 格。,图 1-1 时钟示例,不管采用哪种方法，都能达到目的，可谓殊途同归，但从算式上来看： 11+7=18 (向前拨) 115=6 (向后拨) 计算结果并不一样，那么操作结果为什么会一样呢? 这是因为表盘的刻度是以 12 为周期的，超过12 就又从头计数，因此上面的计算结果 18 因超过了 12 ，再从头开始计数后也就得到了 6。这个 12 就称为系统的模数，7 和 5 相对于模数 12 来说称做是互补的，即一个数是另一个数的补码。从上面的计算可以看出，减一个数就等于加上它的补码，效果是相同的，这就是把减法变成加法的原理。,在计算机中以一个有限长度的二进制位作为模。比如用一个字节表示一个数，则其模数为 28，如运算结果超过 28，就从中减去 28。反映在内存中，其情况为 1 00000000 即把 8 位以外的数舍掉。 计算机中的补码是这样定义的： 正数：其补码与其原码、反码相同。例如： +15补=+15原=+15反=00001111 +127补=+127原=+127反=01111111 负数：最高位为 1，其余各位在原码的基础上取反，然后在最低位加 1，简称“求反加 1”。可用如下关系式表示： x补=x反+1,注意：各位取反时不包括符号位，即符号位不求反。例如： -15原=10001111 -127原=11111111 -0原=10000000 -15反=11110000 -127反=10000000 -0反=11111111 -15补=11110001 -127补=10000001 -0补=00000000 因为-0反+1=100000000，把超过 8 位的部分舍掉，则 -0补的结果就是00000000，而+0的补码也是00000000，即在补码表示法中，0 的表示是惟一的。 在 8 位字长情况下，-128是一个特殊的数，计算机中规定它的表示为 10000000，即它的补码为 -128补=10000000 我们也可以这样来看一个补码的生成，如表1-2 所示。,-127 以前各数的补码既可以按x补=x反+1的公式得到，也可以按在前一个负数补码的基础上减 1 的规则来得到，而按这个规则求出-128 的补码为10000000也就很自然了。,1.2 数的定点和浮点表示 对任意一个二进制数N，都可以表示成下面的形式： N=2jS 其中，j是二进制整数，称为数N的阶码，S为二进制小数，称为数N的尾数。尾数表示数N的全部有效数字, 阶码指明小数点的位置。 对任意一个数，如阶码j是固定不变的，则这种表示方法称为数的定点表示，这样的数称为定点数； 如阶码j可以取不同的值，则称为浮点表示，这样的数称为浮点数。 如果j=0，则这样的定点数只能表示小数，这是一种常用的表示小数的方法。采用定点表示的计算机称为定点机，其中数的小数点的位置是固定的。而采用浮点表示的计算机称为浮点机，其中数的小数点的位置是变化的、浮动的。浮点机通用性强，但复杂； 定点机制造简单，但精度受到影响。,设定点计算机的字长是 9 位，其中一位是符号位，另 8 位是数值位，则该计算机所能表示的数的绝对值范围是： 0.000000010.11111111 或写成： 28128 一般地，若定点计算机的字长是n位，其中一位是符号位，则它所能表示的数的绝对值范围是： 2(n1) 12(n1) (数值位最低位为1，其余位皆为0) (数值位各位全是1),例如，浮点数110011.101的机器表示格式如下： 因为 110011.101=26