计算机导论(1)

《计算机导论(1)》由会员分享，可在线阅读，更多相关《计算机导论(1)（42页珍藏版）》请在金锄头文库上搜索。

1、计算机基本原理简介数制,计算机会“自动计算”的基本原理（一）,计算模型与图灵机 计算模型:计算模型是刻划计算这一概念的一种抽象的形式系统或数学系统 。 算法：算法是对计算过程步骤（状态）的一种刻划，是计算方法的一种可行实现方式。凡是能用算法方法解决的问题，也一定能用这些计算模型解决；反之计算模型解决不了的问题，任何算法也解决不了。 计算模型之间在能力上是等价的 图灵机就是一个计算机模型。它更接近普通人计算的思想方法，又因其好用而被现代计算机的研究开发者所采纳计算模型。,图灵机可形式化地描述为：图灵机是一个五元组：K,s,H；K是一个有穷个状态的集合；是字母表，即符号的集合：0,1，*；是转移函

2、数，即控制器的规则集合；sK,是初始状态；HK,是停机状态：,例1、设计一台可以计算“x+1”的图灵机。（见P1719） 状态集合K:start, add ,carry, noncarry, overflow, return, halt 字母表：0,1,* 初始状态s：start 状态编码 停机状态H：halt 状态 编码 规则集合： start 0101add 0110字母表编码 cary 0111符号 编码 noncary 1000 0 0000 overflow 1001 1 0001 run 1010 * 0010 halt 1011 读写头动作编码 动作 编码 Left 0011 R

3、ight 0100,表1 “x+1”的图灵机转换规则,数的进制与各进制间的转换,数的进制：人们为了记数的方便和计算，创造了各种“权值”（即逢“几”进一）的记数方法，这些方法就称为数的进制。 十进制 R=10，可使用0,1,2,3,4,5,6,7,8,9 二进制 R=2 ，可使用0,1 八进制 R=8 ，可使用0,1,2,3,4,5,6,7 十六进制 R=16 ，可使用0,9,A,B,C,D,E,F “逢R进一，借一当R”,p进制：N= an pn+an-1pn-1+a1p1+a0p0+a-1p-1+a-2p-2+a-mp-m其中 p为正整数，ai 是0，1，2，（p-1）这p个数中的任一个，m

4、、n是正整数。,不同数制之间的转换,二、八、十六进制转换为十进制 对任意一个二、八、十六进制数，均可按照前述R进制数的展开和式方便的转成相应的十进制数 例如：（1101.01)2=1*23+1*22+0*21+1*20+0*2-1+1*2-2（132）81*82+3*81+2*8064+24+290,十进制数转换为R进制数,(1)十进制整数转换为r进制 规则：采用除以r取余数，直到商为零时结束。所得余数序列，先余为低位，后余为高位。 (2)十进制小数转换为r进制 规则：采用乘以r取整数，直到余数为0时结束。所得整数序列，先整为高位，后整为低位。,1101,例1：(13)10 = ( )2,1

5、3,6,3,1,0,2,2,2,2,余数,1,0,1,1,二进制数低位,二进制数高位,(0.6875)10 = ( )2,0. 6 8 7 5,2,3 7 5 0,1.,2,7 5 0,2,0.,5 0,1.,2,0,1.,整数,1,0,1,1,二进制数高位,二进制数低位,例2：,二进制与八进制、十六进制之间的相互转换,(1) 二进制数转换成八进制数：以小数点为分界点，左右三位一节，不足三位以零补足三位。,例: (101101.01) 2=(101,101.010)=(55.2)8,(2)八进制数转换成二进制数：将每位八进制数码以三位二进制数表示。,例: (76.42) 8=(111110.1

6、00010)2=(111110.10001)2,二进制与八进制、十六进制之间的相互转换,(3)二进制数转换成十六进制数：以小数点为分界点，左右每四位一节，不足四位以零补足四位。,(4)十六进制数转换成二进制数：将每位十六进制数码以四位二进制数表示。,【例】 求(1001.101)2的十进制数值。解：(1001.101)2 123+022+021+120+12-1+02-2+12-3 = 8+1+0.5+0.125 = (9.625)10二进制数转换为十进制数的方法是：用十进制 计数制把二进制数各位置的数按权展开后相加。,十进制整数转换为二进制整数的方法是：首先不断地对前次得到的商除2并列出其余

7、数，然后把所得余数按从后向前的次序排列。该方法简称除2取余法。【例】 求(19)10的二进制数值。解： 2 19 1 (低位)2 9 1 2 4 02 2 02 1 1 (高位)0(19)10=(10011)2,表2-1 十进制数和二进制数转换表,在十进制小数转换为二进制小数过程中，有时会出现乘积的小数部分总不等于0的情况，如(0.4435)10就不能在10步内使乘积的小数部分等于0；甚至还会出现循环小数的情况，如(0.6)10 = (0.100110011001)2。在上述两种情况下，乘2过程的结束由所要求的转换精度确定。,计算机中数据的表示,定点表示法 所谓定点(fixed point)表

8、示法 , 是指计算机中的小数点位置是固定不变的。根据小数点位置的固定方法不同，又可分为定点整数及定点小数表示法。前者小数点固定在数的最低位之后，后者小数点固定在数的最高位之前。设计算机的字长为位，则上述两种表示法的格式如下：,浮点数可以扩大数的表示范围。 一个数N用浮点数表示可以写成：N MREM表示尾数，E表示阶码，R表示基数。计算机中基数R一般取2，8，16等，由于R为常数，不需要在数码中表示出来，所以在浮点数表示中只需要一对定点数表示：一个是尾数M，通常是小数;另一个是阶码E，通常是整数。,浮点表示法,在计算机数的实际表示中，阶码采用二进制整数表示，尾数用二进制小数表示。 阶符 阶码 数

9、符小数点 尾数 如二进制数N11010.1101001可表示成N10.10101101001*20100,N1在计算机中具体可以表示为：,浮点数的精度基本上由M（尾数）的位数决定，数的范围有R和E决定。另外，对同一个数N，浮点表示法也不唯一。如对二进制数，尾数右移一位（即小数点左移一位），阶码加1；尾数左移一位（即小数点右移一位），阶码减1。 例如： N1=-0. 0010010101001*20101=-0.010010101001*20100=-0.10010101001*20011 为了使浮点数表示法唯一，也为了使数的有效数字尽可能多地占据尾数的有效数位，必须对数进行“规格化”处理。规格

10、化数处理时规定非零浮点数的尾数最高位必须是非零的有效位，即尾数必须是以“1”打头。,由于数都有符号，如正数、负数和零，在计算机中是二进制，计算机不容易直接用“+”和“-”的符号来表示，只能用“0”和“1”来表示。计算机如何识别是符号“1”还是数值“1”？所以，必须寻找一种方法，将数的符号和数值通过统一的方法表示出来。这就涉及原码、补码、反码及移码的概念。一般约定正数的符号用0表示，负数的符号用1表示。 例如：正数 N1=+0.1011； 负数 N2=-0.1011它们在机器中分别表示为：0.1011和1.1011。 我们将数在机器中的这些编码表示叫机器数，而将原来一般书写表示的数叫机器数的真值

11、。,计算机中数的表示方法,1.原码表示方法 原码是一种机器数。所谓数的原码表示方法，是在机器中用符号位的0和1表示数的正号和负号，而其余位表示数的本身。 原码的定义：x 0x11-x,-1x0,X原=,+0原 =0.00000-0原 =1.0000 例如，正数X=0.63510=0.1012， 则X的原码为X原=0.101 又如，负数X=0.63510=0.1012， 则X的原码为X原=.101,2.反码表示方法 求反码的规则：对于负的二进制数，符号位为，各位数值取反，即 0变为， 1变为0; 正数的反码为真值本身。 反码的定义：x 0x1（2-2-n）+x,X反=,-1x0,+0反 =0.0

12、0000-0反 =1.0000 例：正数X=0.63510=0.1012 则X的原码为X原=0.101 X的反码为X反=0.101 又例：负数X=0.63510=0.1012则X的原码为X原=.101 X的反码为X反=.010,3.补码表示方法 我们先以日常钟表对时为例， 说明补码的概念。 假设现在的标准时间为4点整，而有一只表却已是7点， 为了校准时间，可以采用两种办法:二是将时针退(7一4)=3格;一是将时针向前拨9(=12一3)格,都能对准到4点.可见,减 3和加 9是等价的.我们把(+9)称为 (- 3) 对12的补码,可以用数学公式表示为39（MOD 12）。 补码的定义：x 0x1

13、2+x,X补=,-1x0,求补码的规则：对于负的二进制数，符号位为，数值各位取反，末尾位加；正数的补码为真值本身。优点：负数用补码表示时，可以把减法转化成加法，这样，在计算中可以用加法器实现减法。+0补=-0补=0.0000,由x补求-X补 对绝对值小于的x（不论是正数还是负数），由x补求-X补的方法就是：通过对x补连同符号位一起“求反加1” 例：正数X=0.63510=0.1012则 X的补码为：X补=0.101则 X的补码为： X补=1.011,1二进制的加法运算按下列三条法则进行： （1）0+0=0 （2） 0+1=1+0=1 （3）1+1=0（此时向高位有进1位，逢二进1） 2二进制的减法运算按下列三条法则进行： （1）0+0=1-1=0 （2） 1-0=1 （3）0-1=1（此时向高位有借1，借一当二）,3二进制的乘法运算按下列三条法则进行： （1）00=0 （2） 01=10=0 （3）11=1 例3（1011）2+（1101）2=（？）2 被乘数 1 0 1 1）乘数 1 1 0 1 部 1 0 1 1 分 0 0 0 0 积 1 0 1 1 1 0 1 1 乘积 1 0 0 0 1 1 1 1 在计算机中实现二进制的乘法运算，通常采用的是移位相加的方法。,