【文档说明】计算机导论0课件1.ppt，共(58)页，476.018 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-77310.html

以下为本文档部分文字说明：

计算机导论第2章图灵机模型及数据编码内容提要2.1概2.3数据在计算机中的表示计算机导论第2章图灵机模型及数据编码2.2图灵机在第一台电子计算机ENIAC诞生的10年前即1936年，英国数学家图灵发表了题为“论可计算数及其在判定问题中的应用”﹙OnComputerNumbersWithanAp

plicationtotheEntscheidungsProblem﹚的学术论文，奠定了学术界公认的现代电子计算机的理论和模型基础。1、希尔伯特纲领20世纪初，逐步形成了关于数学基础研究的逻辑主义、直觉主义和形式主义三大流派。其中，形式主义流派的代表人物是数学家希尔伯特﹙D．Hilbert﹚。他

在数学基础的研究中提出了一个设想，其大意是：将每一门数学的分支形式化，构成形式系统或形式理论，并在以此为对象的元理论即计算机导论第2章图灵机模型及数据编码元数学中，证明每一个形式系统的相容性，从而导出

全部数学的相容性，希尔伯特的这一设想，就是所谓的“西尔伯特纲领”。“西尔伯特纲领”的目标，其实质就是要寻找通用的形式逻辑系统，该系统应当是完备的，即在该系统中，可以机械地判定任何给定命题的真伪。D．Hilbert希尔伯特计算机导论第2章图

灵机模型及数据编码“西尔伯特纲领”的研究基础是逻辑和代数，主要源于19世纪英国数学家乔治·布尔﹙G．Boole﹚所创立的逻辑代数体系﹙即布尔代数﹚。1854年，布尔在他的著作中成功地将“真”、“假”两种逻辑值和“与”、“或”、“非”3种逻辑运算归结为一种代数。这样，形式逻辑系

统中的任何命题都可用数学符号表示出来，并能按照一定的规则推导出结论。尽管布尔没有将“布尔代数”与计算机联系起来，但他的工作却为现代计算机的诞生作了重要的理论准备。G．Boole乔治·布尔计算机导论第2章图灵机模型及数据编码希尔伯特的工作建立在布尔工作

的基础上，并使其进一步具体化。希尔伯特对实现自己的纲领充满信心。然而，1931年，奥地利25岁的数理逻辑学家哥德尔﹙K．Gödel﹚提出的关于形式系统的“不完备性定理”中指出，这种形式系统是不存在的，

从而宣告了著名的“西尔伯特纲领”的失败。希尔伯特纲领的失败同时也暴露了形式系统的局限性，它表明形式系统不能穷尽全部数学命题，任何形式系统中都存在着该系统所不能判定其真伪的命题。计算机导论第2章图灵机模型及数据编码“西尔伯特纲领”虽然失败了，但它仍然不失为人类抽象思维的一个伟大成果，它的历

史意义是多方面的。首先，“西尔伯特纲领”是在保全古典数学的前提下去排除集合论悖论的，它给数学基础问题的研究带来了全新的转机。其次，希尔伯特纲领的提出使元数学得到了确立和发展。最后，对计算学科而言，最具意义的是，希尔伯特纲领的失败启发人们应避

免花费大量的精力去证明那些不能判定的问题，而应把精力集中于解决具有能行性的问题。计算机导论第2章图灵机模型及数据编码2、图灵对计算本质的揭示在哥德尔研究成果的影响下20世纪30年代后期，图灵﹙A．M．

Turing﹚从计算一个数的一般过程入手对计算的本质进行了研究，从而实现了对计算本质的真正认识。根据图灵的研究，直观地说，所谓计算就是计算者﹙人或机器﹚对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改

变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。图灵用形式化方法成功表述可计算这一过程的本质。图灵的研究成果是哥德尔研究成果的进一步深化，该成果不仅再次表明了某些数学问题是不能用任何机械过程来解决的

思想，而且还深刻揭示可计算所具有的“能行过程”的本质特征。计算机导论第2章图灵机模型及数据编码图灵的描述是关于数值计算的，不过，我们知道英文字母表的字母以及汉字均可以用数来表示，因此，图灵机同样可以处理非数值计算。不仅如此，更为重要的是，由数值和非数值﹙英文字母、汉字

等﹚组成的字符串，既可以解释成数据，又可以解释成程序，从而计算的每一过程都可以用字符串的形式进行编码，并存放在存储器中，以后使用时译码，并由处理器执行，机器码﹙结果﹚可以从高级符号形式﹙即程序设计语言﹚机械地推导出来。图灵的研究成果是：可计算

性＝图灵可计算性。在进行可计算性问题的讨论时，不可避免地要提到一个与计算具有同等地位和意义的基本概念，那就是算法。算法也称为能行计算机导论第2章图灵机模型及数据编码方法或能行过程，是对解题﹙计算﹚过程的精确描

述，它由一组定义明确且能机械执行的规则﹙语句、指令等﹚组成。根据图灵的论点，可以得到这样的结论：任一过程是能行的﹙能够具体表现在一个算法中﹚，当且仅当它能够被一台图灵机实现。图灵机等计算模型均是用来解决问题的，理论上的能行性隐含着计算模型的正确性，

而实际实现中的能行性还包含时间与空间的有效性。计算机导论第2章图灵机模型及数据编码3、图灵机为纪念图灵对计算机的贡献，美国计算机博物馆于1966年设立了“图灵奖”计算机是使用相应的程序来完成任何设定好的任务。图灵机是一种思想模型，它由三部分组成

：一个控制器，一条可以无限延伸的带子和一个在带子上左右移动的读写头。计算机导论第2章图灵机模型及数据编码根据图灵的观点可以得到这样的结论：凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。今天我们知道，图灵机与当时提出的用于解决计算问题的递归函

数、λ演算和POST规范系统等计算模型在计算能力上是等价的。它们于20世纪30年代共同奠定了计算科学的理论基础。相比于其他几种计算模型，图灵机是从过程这一角度来刻画计算的本质，其结构简单，操作运行规则也较少，从而为更多的人所理解。图灵机的特征①图灵机由一

条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成，如图所示。图灵机计算机导论第2章图灵机模型及数据编码的带子被划分为一系列均匀的方格。读写头可以沿带子方向左右移动，并可以在每个方格上进行读写。②写在带子上的符号为一个有穷

字母表：｛S0,S1,S2,…,SP｝。通常，可以认为这个有穷字母表仅有两个S0、S1字符，其中S0可以看作是“0”，S1可以看作是“1”，它们只是两个符号，要说有意义的话，也只有形式的意义。…bb10100010bbb…状态q1读—写头控制器计算机导论第2章图灵机模型及数据

编码由字符“0”和“1”组成的字母表可以表示任何一个数。③机器的控制状态表为｛q1,q2,…qm,｝。通常，将一个图灵机的初始状态设为q1，在每一个具体的图灵机中还要确定一个结束状态qw。一个给定机器的“程序”认

为是机器内的五元组﹙qiSjSkR﹙或L或N﹚ql﹚形式的指令集，五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下：qi表示机器目前所处的状态；Sj表示机器从方格中读入的符号；Sk表示机器用来代替写入方格中的符号；R、L、N分别表示向右

移一格、向左移一格、不移动；ql表示下一步机器的状态。计算机导论第2章图灵机模型及数据编码图灵机的工作原理机器从给定带子上的某起始点出发，其动作完全由其初始状态及机内五元组来决定。就某种意义而言，一个机器其实就是它作用于纸带上的五元组集。一个机器计算的结果是

从机器停止时带子上的信息得到的。4、冯·诺依曼型计算机1946年2月14日，世界上第一台数字电子计算机ENIAC在美国宾夕法尼亚大学研制成功。该机是使用电子线路来执行算术和逻辑运算以及信息存储的真正工作的计算机器，它的成功研制显示了电子线路的巨大优越性。但是，ENIAC的结构在很大程度上是依照机电

系统设计的，还存在重大的线路结构等问题。在图灵等人工作的影响下，1946年6月，美国杰出的数学家冯·诺依曼及其同事完成了关于《电子计算装置逻辑结构设计》的研究报告，具体计算机导论第2章图灵机模型及数据编码介绍了制造电子计算机和程序设计的

新思想，给出了由控制器、运算器、存储器、输入和输出设备5类部件组成的，被称为冯·诺依曼型计算机﹙或存储程序式计算机﹚的组织结构，以及实现它们的方法，为现代计算机的研制奠定了基础，至尽为止，大多数计算机采用的仍然

是冯·诺依曼型计算机的组织结构，只是作了一些改进而已。因此，冯·诺依曼被人们誉为“计算机器之父”。计算机导论第2章图灵机模型及数据编码内存储器运算器外存储器输入设备输出设备控制器数据信号控制信号注：冯·诺依曼型计算机的组织结构计算

机导论第2章图灵机模型及数据编码JohnvonNeumann冯诺依曼1949EDSAC存储程序工作原理计算机的两个基本能力：一是能够存储程序，二是能够自动地执行程序。计算机是利用“存储器”（内存）来存放所要执行的程序的，而称之为CPU的部件可以依次从

存储器中取出程序中的每一条指令，并加以分析和执行，直至完成全部指令任务为止。计算机导论第2章图灵机模型及数据编码香侬是现代信息论的著名创始人。1938年，香侬在发表的论文中，首次用布尔代数进行开关电路分析，

并证明布尔代数的逻辑运算可以通过继电器电路来实现。阿塔纳索夫提出了计算机的三条原则：1）以二进制的逻辑基础来实现数字运算，以保证精度；2）利用电子技术来实现控制、逻辑运算和算术运算，以保证计算速度；3）采用把计算功能和

二进制数更新存储功能相分离的结构。ClaudeShannon奠定现代计算机发展的重要人物和思想计算机导论第2章图灵机模型及数据编码2.3数据在计算机中的表示计算机中的数据和指令都是用二进制代码表示的，这是因为计算机的各

组成部分是仅具有两个稳定状态的物理元件—电子开关线路所组成。为此，要想深入学习计算机的各个部分，必须掌握二进制代码的有关知识。计算机中用二进制代码表示数据信息有两种方法：①按“值”表示：在选定的进位制中正确地表示出数值，包括数字、符号、小数点位置及正负号等。如“－9.5”可表

示为二进制的“－1001.1”。②按“形”表示：按照一定的编码方法来表示数据。如用ASCII码表示“－9.5”，其形式为0101101、0111001、0101110、0110101。计算机导论第2章图灵机模型及数据编码1、进位

制数及其相互转化(一)进位制数（进位计数制）数制的定义：用一组固定的数字(数码符号)和一套统一的规则来表示数值的方法就叫做数制(numbersystem也称计数制)。这一定义主要的内涵是：(1)数制的种类很多，除了十进制数，还有二

十四进制(24小时为一天)，六十进制(60分为1小时，60秒为1分)，二进制(鞋、袜、筷子等两只为一双)，等等。(2)在一种数制中，只能使用一组固定的数字来表示数的大小。数字在一个数中所处的位置称为数位。具体使用多

少个数字来表示一个数值的大小，就称为该数制的基数(base)。例如，十进制数(Decimal)计算机导论第2章图灵机模型及数据编码的基数是10，使用0～9十个数字，二进制数(Binary)的基数为2，使用0，

1两个数字。在计算机文献中，十进制数是在数的末尾加字母D来标识。例如，1989D，表示十进制数1989。一般情况下，1989就是一个十进制数，不在后面加D。二进制数是在数的末尾加字母B来标识。例如，101B，表示二进制数的101，即十进制数的5。(3)在一种数制中，有一套统一的规则。N进

制的规则是逢N进1，或者借1为N。权或称位权，是指数位上的数字乘上一个固定的数值。十制数是逢十进一，所以对每一位数可以分别赋以位权100，101，102，…。用这样的位权就能够表示十进制的数。计算机导论第2章图灵机模型及数据编码基数某一基

数中的最大数是“基数减1”，而不是基数本身，如十进制数中的最大数为(10－1＝)9，二进制数中的最大数为(2－1＝)1；最小数均为0。数位、基数和位权是进位计数制中的三个要素。采用二进制记数法原因目前，在计算机内部，数据的计算和处理都

采用二进制记数法，主要是由二进制数在技术操作上的可行性、可靠性、简易性以及其逻辑性所决定的。(1)可行性若用十进制数，需要0，1，…，9等不同的10个基数，用电子技术实现这10种状态就很困难。而用二进制数，则只需0，1两个基数，要表示两个状态，这在电学

技术上的计算机导论第2章图灵机模型及数据编码实现最为容易。例如，电灯的亮和灭，晶体管的导通和截止，等等。(2)可靠性因二进制数只要两个状态，数字转移和处理就不易出错，这样计算机工作的可靠性就高。(3)简易性二进制数运算法则简单。例如，二进制的加法、积法法则都只有三个。

运算法则少，使计算机运算器结构大大简化，控制也可随之简化。(4)逻辑性由于二进制数只要0，1两个数码，可以代表逻辑代数中的“假”和“真”，这就是在计算机中使用二进制的逻辑性。计算机导论第2章图灵机模型及数据编码具体分析二进制、十进制、八进制、十六进制的性质：①十进制

﹙D﹚ⅰ具有十个数字符号0，1，2，3，…，9；ⅱ逢十进一；ⅲ基数为10，第i位的权为﹙10﹚i。•举例：﹙123.45﹚10＝1×102＋2×101＋3×100＋4×10-1•＋5×10-2表示方法：﹙123

.45﹚10＝123.45D②二进制﹙B﹚ⅰ具有两个数字符号0，1；ⅱ逢二进一；ⅲ基数为2，第i位的权为﹙2﹚i。计算机导论第2章图灵机模型及数据编码举例：﹙101.101﹚2＝1×22＋0×21＋1×20＋1×2-1＋0×2-2＋1×2-3表示方法：﹙101.101﹚2＝101.10

1B③八进制﹙Q﹚ⅰ具有八个数字符号0，1，2…，7；ⅱ逢八进一；ⅲ基数为8，第i位的权为﹙8﹚i。举例：﹙137.43﹚8＝1×82＋3×81＋7×80＋4×8-1＋3×8-2表示方法：﹙137.43﹚8＝137.43Q计算机导论第2章图灵机模型及数据编码④十六进制﹙H﹚ⅰⅰ具有十六个

数字符号0，1，2…，9，A，B，C，D，E，F；ⅱ逢十六进一；ⅲ基数为16，第i位的权为﹙16﹚i。举例：﹙147B.CD﹚16＝1×163＋4×162＋7×161＋B×160＋C×16-1＋D×16-2表示方法：﹙147B.C

D﹚16＝147B.CDH㈡进位制数的相互转换1、十进制数与二进制数间的相互转换①DB计算机导论第2章图灵机模型及数据编码﹙27﹚10＝﹙？﹚2例1：﹙5﹚10＝﹙？﹚2251……0222……10……1227213……126……123……021……10……1

即﹙5﹚10＝﹙101﹚2﹙27﹚10＝﹙11011﹚2计算机导论第2章图灵机模型及数据编码例2：﹙0.625﹚10＝﹙？﹚20.625×21.250……1×20.50……0×21.0……1即﹙0.625﹚10＝﹙0.101﹚2例3：﹙27.625﹚10＝﹙

11011.101﹚2口诀：整数部分，除2取余数，直到商为0。余数排列，由下到上；小数部分，乘2取整数，直到小数部分为0﹙或达到所求的精确度﹚。整数排列，由上到下。计算机导论第2章图灵机模型及数据编码

将二进制数的各位按权展开相加。例4：﹙101﹚2＝﹙？﹚10﹙101﹚2＝1×22＋0×21＋1×20＝﹙5﹚10例5：﹙11011.101﹚2＝﹙？﹚10﹙11011.101﹚2＝1×24＋1×23＋0×22＋1×21＋1×20＋1×2-1＋0×2-2＋1×2-3＝27＋0.5＋0.125＝﹙2

7.625﹚10②BD计算机导论第2章图灵机模型及数据编码2、十进制与八进制间的相互转化①DQ同与二进制间的转化类似，整数部分除以8，取余数；小数部分则乘以8，取整数。此外，我们知道，八进制的基数8正好是二

进制基数的3次幂，即81＝23，故八进制的一位相当于二进制的三位。因此在转化时，也可以先将十进制数转化为二进制数，而后在进一步转化为八进制数。例﹙略﹚②QD将八进制数的各位按权展开相加。例﹙略﹚计算机导论第2章图灵机模型及数据编码八

进制与二进制的关系八进制对应二进制八进制对应二进制00004100100151012010611030117111计算机导论第2章图灵机模型及数据编码3、十进制数与十六进制数间的相互转化①DH•同与二进制间的转化

类似，整数部分除以16，取余数；•小数部分则乘以16，取整数。十六进制的基数16正好是二进制基数的4次幂，即161＝24，故十六进制的一位相当于二进制的四位。因此在转化时，也可以先将十进制数转化为二进制数，而后在进一步转化为十六进制数。例﹙略﹚②HD将十六进

制数的各位按权展开相加。例﹙略﹚计算机导论第2章图灵机模型及数据编码十六进制与二进制的关系十六进制对应二进制十六进制对应二进制0000081000100019100120010A101030011B101140100C110

050101D110160110E111070111F1111计算机导论第2章图灵机模型及数据编码2、数据的长度单位数据的长度单位有位、字节和字等。(1)位也称比特，记为bit(binarydigit的缩写)或小写b，这是最小的信息单位，是用0或1来表示的1个二进制数位。(2

)字节记为Byte或大写B，这是计算机的最小存储单元。PC机中由8个二进制位构成一个字节，从最小的00000000到最大的11111111，即一个字节可有256个值。一个字节也可以表示由8个二进制位构成的其它信息。一个字节可存放一个半角英文字符的编码(ASCII

码)。两个字节可存放一个汉字编码，计算机导论第2章图灵机模型及数据编码1个汉字至少需要两个字节或两个字符来表示。这里所说的字符是指ASCII码字符，即半角下的英文字母、数字或其它符号。位（Bit）：度量数据的最

小单位字节（Byte）：最常用的基本单位K(KiloBytes，千)字节1K=1024byte=210M（MegaBytes，兆）字节1M=1024K=220G（GigaBytes，吉）字节1G=1024M=230T（TeraBytes，太）字节1T=1024G=240P（Pe

taBytes，拍）字节1T=1024G=250计算机导论第2章图灵机模型及数据编码(3)字记为word或小写w，是计算机信息交换、加工、存储的基本单元。用二进制代码表示，一个字由一个字节或若干字节构成。它可以代表数据代码、字符代码、操作码和地址码或它们的组合。计算机的“

字”用来表示数据或信息长度。3、数值的表示㈠机器数在计算机中，因为只有“0”和“1”两种形式，为了表示数的正、负号，也必须以“0”和“1”表示。通常把一个数的最高位定义为符号位，用0表示正，1表示负，称

为数符；其余位仍表示数值。通常，把在机器内存放的正负号数码化的数成为机器数，把机器外部由正负表示的数称为真值数。计算机导论第2章图灵机模型及数据编码例如，若一个数占8位，真值数﹙－0101100﹚B的机器数为10101100，存放在机器

中如图示。机器数表示的范围受到字长和数据类型的限制。字长和数据类型确定了，机器数表示的范围也定了。㈡整数和实数在机器中，难以表示小数点，故在机器中通过对小数点的位置加以规定来表示。因此，就有整数和实数区分。10101100数符计算机

导论第2章图灵机模型及数据编码1、整数整数是没有小数部分的数，也可以认为小数点在数的最右边。整数分为带符号和不带符号两类。对带符号的整数，符号位被放在最高位。整数表示的数是精确的，但数的范围是有限的。根据存放数的字长，它们可以用8、16、32位等表示，各

自表示数的范围见下表。不同位数和数的表示范围二进制位数无符号整数的表示范围有符号整数的表示范围80～255﹙28—1﹚－128～127﹙27—1﹚160～65535﹙216—1﹚－32768～32767﹙215—1﹚320～﹙232—1﹚－231～231—1计算机导论

第2章图灵机模型及数据编码•2、实数计算机处理的数值大部分是实数，即带有小数部分的数，尤其是在科学计算中。通常，为了能表示特大或特小的数，实数采用“浮点数”或称“科学表示法”表示，“浮点数”由两部分组成，即尾数和阶码。任意二进制规格化浮点数的表示形式为

：N＝±d×2±p,式中：d是尾数，前面的“±”表示数符；p是阶码，前面的“±”表示阶符。它在计算机内的存储形式如图示：阶符Ef阶码E数符Sf尾数S浮点数存储格式计算机导论第2章图灵机模型及数据编码阶码通常用整数形式来表

示，它指出的是小数点在数据中的位置，决定了浮点数的表示范围；尾数通常用小数形式表示，给出了有效数字的位数，决定了浮点数的表示精度。所谓规格化的浮点数就是指尾数需满足条件：≤S＜1。㈢二进制的原码、反码及补码表示按值表示数需解决的一个问题是如何表示数的正负号。在计算机中，数的正负号是

用“0”、“1”表示的。机器数在计算机时，若将符号同时和数值参加运算，则会产生错误的结果；否则要考虑计算机结果的符号问题，将增加计算机实现的难度。例如，－5＋4的结果应为－1，但在计算机导论第2章图灵机模型及数据编码计算机中若按照上面讲的符号和数值同时参加

运算，结果为－9，显然是错误的。若要考虑符号位的处理，则运算变得复杂。为了解决此类问题，在机器数中，数有三种表示法：原码﹙primarycode﹚、反码﹙one’scomplement﹚和补码﹙tow’scompleme

nt﹚。设计算机的字长为n位，它可表示的真值x＝±xn-2xn-3……x0,其中xi＝0或1﹙二进制数﹚，则有：1、真值x＝＋xn-2xn-3……x0时，原码、反码和补码完全相同，即[x]原＝[x]反＝[x]补＝0xn-2xn-3……x0计算

机导论第2章图灵机模型及数据编码2、真值x＝－xn-2xn-3……x0时，原码、反码和补码与x的关系如下：[x]原＝1xn-2xn-3……x0[x]反＝1……[x]补＝1……(+1)从而可知，在n位的机器数中，最高位为符号位，若该位为0真值为正，该位为1则

真值为负；其余的﹙n－1﹚位为数值位，其取值为0或1。当真值为正时，原码、反码和补码的数值位完全相同；当真值为负时，原码的数值位保持真值的原样，反码的数值位为原码的各位取反，补码则是反码的最低位加1。根据以上关系，很容易实现真值与机器数之间及三种机器数之间的

相互。xn2xn3x0xn2xn3x0x1计算机导论第2章图灵机模型及数据编码转换。例1：已知计算机字长为8位，试写出二进制数＋101010和－101010在机器中表示的原码、反码及补码。首先写出它们的真值。设该机器采用定点整数表示，则真值形式如

下：x＝＋0101010y＝－0101010真值x为正，故有[x]原＝[x]反＝[x][x]补＝00101010真值y为负，有[x]原＝10101010[x]反＝11010101[x]补＝11010110计算机导论第2章图灵机模型及数据编码例

2：已知＝101101，求真值x。分析：最高位为符号位，先由[x]补求出[x]反[x]反＝101101－1＝101100[x]补＝110011从而有y＝－10011㈣运算基础计算机中的运算有两类，一是算术运算

，另一类是逻辑运算。算术运算包括加、减、乘、除等四则运算。⒈逻辑运算常用的逻辑运算有逻辑乘﹙“与”运算﹚、逻辑加﹙“或”运算﹚、逻辑非﹙“非”运算﹚等运算，它们都是按位进行运算的，也称逻辑操作。计算机导论第2章图灵机模型及数据编码①“与

”运算﹙∧，·﹚“与”﹙AND﹚运算的规则如下：0∧0＝00∧1＝01∧0＝01∧1＝1式中，“∧”是“与”的运算符号，也可以用“·”代替。“与”运算的一般式为C＝A∧B或C＝A·B＝AB②“或”运算﹙∨，＋﹚“或”

﹙OR﹚运算的规则如下：0∨0＝00∨1＝11∨0＝11∨1＝1式中，“∨”是“或”的运算符号，也可以用“＋”代替。“或”运算的一般式为C＝A∨B或C＝A＋B计算机导论第2章图灵机模型及数据编码③“非”运算“非”﹙NOT﹚运算的规则如下：＝1＝0式中

，“ˉ”是“非”的运算符号。“非”运算的一般式为C＝④“异或”运算﹙﹚“异或”﹙EOR：ExclusiveOR﹚运算的规则如下：式中，“”是“异或”的运算符号。01A000=01=110=11

1=0“异或”运算的一般式为C＝AB计算机导论第2章图灵机模型及数据编码2、算术运算二进制的四则运算﹙按位进行运算﹚例2：1110-0011＝？1110-001110111101×10011101000001101111010111010000001101例4：100000

1101＝？例1：1001＋1000＝？1001+100010001例3：1101×1001＝？10000011011101101110101101101000计算机导论第2章图灵机模型及数据编码补码加减运算⒈补码加法设x,y为正或负整数的真值，则由补码的定[x]补＋[y]补＝[x+y]补﹙＊

﹚应用这一公式很容易实现补码的加法运算。例1：设x＝＋0110110,y＝－1111001。求x＋y＝？解：在计算机中，真值x,y表示下列补码形式[x]补＝0,0110110[y]补＝1,0000111根据﹙

＊﹚式，有[x+y]补＝[x]补＋[y]补＝1，0111101求得x＋y＝－1000011结果正确计算机导论第2章图灵机模型及数据编码例2：设x＝＋1010011,y＝＋0100101。求x＋y＝？解：[x]补＝0,1010011[y]补＝0,01001

01根据﹙＊﹚式，有[x+y]补＝[x]补＋[y]补＝0，1111000求得x＋y＝＋1111000结果正确例3：设x＝－1000011,y＝－0100001。求x＋y＝？[x]补＝1,0111101+[y]补＝1,1011111[x]补＋[y]补＝11,0011100丢

失即[x]补＋[y]补＝[x+y]补＝1,0011100求得x＋y＝－1100100结果正确该例中，因机器字长假定为8位，故[x]补＋[y]补的结果中最高位﹙“1”﹚无法保存，自动丢失，计算机中的实结果为1,0011100。计算机导论第2章图灵机模型及数据编码例4：设x＝＋1000101

,y＝＋1100111。求x＋y＝？解：[x]补＝0,1000101[y]补＝0,1100111[x]补＋[y]补＝1，0101100即[x+y]补＝[x]补＋[y]补＝1,0101100求得x＋y＝－1010100显然，该结果是错误的，因为两个

正数想加，其和不可能为负数。分析如下：真值x和y所表示的十进制数分别为﹙＋69﹚10和﹙＋103﹚10，其和为﹙＋172﹚10。该十进制数所对应的二进制数为＋10101100，需用9位字长的机器数表示，

现机器只有8位字长，无法表示，称这种现象为“溢出﹙overflow﹚”。计算机导论第2章图灵机模型及数据编码在计算机中，一旦发生溢出，其运算结果肯定是错误的，机器将进行溢出处理。⒉补码减法设x，y为正或负整数的真值，则可利用下列补码关系求得x－y之值。[x-y]补＝[x+(-y)]补＝[x

]补＋[-y]补﹙＊＊﹚例如，设x＝＋1010101,y＝＋1100001。求x－y＝？[x]补＝0,1010101－y＝-1100001[-y]补＝1，0011111故得[x-y]补＝[x+(-y)]补＝1，1110100x－y＝－0001100计算机

导论第2章图灵机模型及数据编码㈤字符的表示字符包括西文字符和中文字符。字符编码的方法和简单，首先确定需要编码的字符总数，然后将每一个字符按顺序编号，编号值的大小无意义，仅作为识别与使用这些字符的依据。1、西文字符对西文字符编码最常用的是ASCII字符编码，即AmericanStandardCod

eforInformationInterchange﹙美国信息交换标准代码﹚。ASCII是用7为二进制编码，它可以表示2即128个字符。每个字符用7位二进制码表示，其排列次序为d6d5dd3d2d1d0

，d6为高位，d0为低位。计算机导论第2章图灵机模型及数据编码B6B5B4B3B2B1B00000010100111001011101110000NULDLE空格0@P、p0001SOHDC1！1AQaq0010STXDC2”2BRbr0011ETXDC3#3CS

cs0100EOTDC4$4DTdt0101ENQNAK%5EUeu0110ACKSYN&6FVfv0111BELETB'7GWgw1000BSCAN（8HXhx1001HTEM）9IYiy1010LFS

UB*:JZjz1011VTESC+;K[k{1100FFFS,<L\l|1101CRGS-=M]m}1110SORS·>N^n～1111SIUS/?O_oDEL计算机导论第2章图灵机模型及数据编码在ASCII码表中，十进制码值0～32和127﹙NUL～SP和DEL﹚共34个字符称为非

图形字符﹙又称为控制字符﹚其余94个字符称为图形字符﹙又称为普通字符﹚。在这些字符中，从“0”～“9”、从“A”～“Z”、从“a”～“z”都是顺序排列的，且小写比大写字母码值大32，即位值d5为0或1，这有利于大、小写字母

之间的编码转换。计算机的内部存储与操作常以字节为单位，即8个二进制位为单位。因此，一个字符在计算机内实际是用8位表示。正常情况下，最高位d7为“0”。在需要奇偶校验时，这一位可用于存放奇偶校验的值，此时称这一位为校验位。计算机导论第2章图灵机模型及数据编码西文字符除了常用的ASCII编码外

，还有另一种EBCDIC码。这种字符编码主要用在大型机器中。EBCDIC代码，即ExtendedBinaryCodedDecimalInterchangeCode﹙扩展的二—十进制交换码﹚。EBCDIC码采用8位二进制码表示，有256个编码状态，但只选用其中一部

分。1、汉字编码英文是拼音文字，采用不超过128种字符的字符集就满足英文处理的需要，编码容易，而且在一个计算机系统中，输入、内部处理和存储都可以使用同一编码﹙一般为ASCII码﹚。汉字是象形文字，种类繁多，编码比较困难

，而且在一个汉字处理系统中，输入、内部处理、输出对汉字编码的要求不尽相同。因此进行一系列的汉计算机导论第2章图灵机模型及数据编码字编码转换，用户用输入码输入汉字，系统由输入码找到相应的内码，内码是计算机内部对汉字的表示，要在显示器上显示或在打印机上

打印出用户所输入的汉字，需要汉字的字形码，系统由内码找到相应的字形码。全称是GB2312—80《信息交换用汉字编码字符集—基本集》，1980年发布，是中文信息处理的国家标准，也称汉字交换码，简称GB码。一个国标码占两个字节,每个字节最高位仍为“0”；英文字符的机内码是7位ASCII码，最高位也是“

0”。因为西文字符和汉字都是字符，为了在计算机内部能够区分是汉字编码还是ASCII码，将国标码的每个字节的最高位由“0”变为“1”，变换后的国标码称为汉字机内码。由此可知汉字机内码的每个字节都大于128

，计算机导论第2章图灵机模型及数据编码而每个西文字符的ASCII码值均小于128。汉字输入码是一种用计算机标准键盘上按键的不同排列组合来对汉字的输入设计的编码，目的是进行汉字的输入，那么对于输入码，要求编码要尽可能的短，从而输入时击键的次数就比较少；另外重码要尽量少，这样输入时就可以基本

上实现盲打；再者，输入编码还要容易学容易上手，以便推广。为了汉字的输出显示和打印，需要描述汉字的字形，即对汉字的字形进行编码，称为汉字的字形码，也称为汉字字模。汉字字形码通常有两种表示方式：点阵方式和矢量方式。

用点阵表示字形时，汉字字形码指的就是这个汉字字形点阵的代码。点阵规模越大，字形就越美观，同时其编码也就越长，所需的存储空间也就越大。矢量表示方式存储的是计算机导论第2章图灵机模型及数据编码描述汉字字形的轮廓特征，当要输出汉字时，通过计算机的计算，由汉字

字形描述生成所需要大小和形状的汉字点阵。二者的区别在于：前者编码、存储方式简单、无需转换直接输出，但字形放大后产生效果差，而且同一种字体不同的点阵需要不同的字库。矢量方式特点正好与前者相反。