第二章计算机基础知识

第2章计算机基础知识2.1

图灵机简介2.2

数的不同进制2.3

数制间相互转换2.4

原码、补码、反码2.5字符数据编码2.1图灵机简介图灵机模型理论是计算学科最核心的理论之一图灵机模型为计算机设计指明了方向图灵机模型是算法分析和程序语言设计的基础理论。本章主要内容图灵机概述计算“X+1”的图灵机通用图灵机图灵机模型的启示

图灵机概述图灵机（英语：TuringMachine，又称确定型图灵机）是1936年，英国剑桥大学著名数学家图灵在研究解决数学的一个基础理论问题时，图灵提出了一种抽象的计算模型。

图灵的基本思想：是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：在纸上写上或擦除某个符号；把注意力从纸的一个位置移动到另一个位置；而在每个阶段，人要决定下一步的动作，依赖于(a)此人当前所关注的纸上某个位置的符号和(b)此人当前思维的状态

图灵机概述为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：一条无限长的纸带TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。纸带上的格子从左到右依此被编号为0,1,2,...，纸带的右端可以无限伸展。一个读写头HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。一套控制规则TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。参见停机问题。注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。图灵机的直观描述3个部件：有穷控制器、无穷带和读写头3个动作：改写当前格、左移或右移一格读写头有穷控制器存储带…………图灵机模型图灵机的形式化描述图灵机是一个五元组（K，∑，δ，s，H），其中：K是有穷个状态的集合；∑是字母表，即符号的集合；s∈K是初始状态；H∈K是停机状态的集合，当控制器内部状态为停机状态时图灵机结束计算；δ是转移函数，即控制器的规则集合。

计算“x+1”的图灵机目标：利用二进制来设计一个专门计算“x+1”的图灵机，要求计算完成时，读写头要回归原位状态集合K：{start，add，carry，noncarry，overflow，return，halt}；字母表∑：{0，1，*}；初始状态s：start；停机状态集合H：{halt}；计算“x+1”的图灵机规则集合δ：“5＋1”的计算过程（1）“5＋1”的计算过程（2）“5＋1”的计算过程（3）“5＋1”的计算过程（4）通用图灵机（1）编码方案：通用图灵机（2）通用图灵机蕴含的计算思想程序也是数据“x+1”图灵机功能是固定的，相当于一个程序通用的图灵机功能根据输入编码的不同而变化存储程序和程序控制M图灵机进一步展示了程序和其输入可以先保存到存储带上，M就按程序一步一步运行直到给出结果，结果也保存在存储带上。通用图灵机蕴含的计算思想通用图灵机模型是计算机的计算能力的极限计算机系统应该有:存储器（相当于存储带）中央处理器（控制器及其状态），并且其字母表可以仅有0和1两个符号；为了能将数据保存到存储器并将计算结果从存储器送出来展示给用户，计算机系统还应该有输入设备和输出设备如键盘、鼠标、显示器和打印机等。2.2数制与编码2.2.1进制及其相互转换

2.2.2计算机中数的表示

2.2.3字符数据编码2.2.1进制及其相互转换

1.进位计数制2.十进制数与二进制数之间的转换3.十进制数与八、十六进制数之间的转换4.二进制数与八、十六进制数的转换1.进位计数制根据不同的进位原则，可以得到不同的进位制。在日常生活中，人们广泛使用的是十进制数，有时也会遇到其他进制的数，例如，钟表上，六十秒钟为一分钟，六十分钟为一小时，即为六十进制。在计算机中，最常使用的是：

(1)十进制

(2)二进制

(3)八进制

(4)十六进制

（1）十进制

十进制记数法有两个特点：·它有十个不同的记数符号：0、1、2、…、9。每一位数只能用这十个记数符号之一来表示，称这些记数符号为数码。·它采用逢十进一的原则计数。小数点前面自右向左，分别为个位、十位、百位、千位等，相应地，小数点后面自左向右，分别为十分位、百分位、千分位等。各个数码所在的位置称为数位。

例如：十进制数666.66

个位的6表示其本身的数值；而十位的6，表示其本身数值的十倍，即6×10，百位的6，则代表其本身数值的一百倍，即6×100；而小数点右边第一位小数位的6表示的值为6×0.1；第二位小数位的6表示的值为6×0.01。因此这个十进制数可以用多项式展开写成：

666.66＝6×102＋6×101＋6×100＋6×10－1＋6×10－2如果用ai表示某一位的不同数码，对任意一个十进制数A，可用多项式表示为：

A＝an－110n－1＋…＋a1101＋a0100＋a－110－1＋…＋a－m10―m在上式中，m、n为正整数，n为小数点左边的位数，m为小数点右边的位数，即m、n为相应的数位值。各个数码由于所在数位不同而乘以10的若干次幂称为相应数位的“权”。“权”的底数称为进位制的基数。在这里，因为是十进制数，所以基数是10。

以上是十进制数的计数机理，在正常书写时，各数码的“权”隐含在数位之中，即：

A＝an－1an－2…a1a0.a–1…a－m

（2）二进制

二进制记数法也有两个特点：·它有两不同的记数符号，即数码：0和1。

·它采用逢二进一的原则计数。也就是说，进位基数是2。数码在不同的数位所代表的值也是不相同的，各数位的“权”是以2为底的幂。

例如：

（10110.1）2

＝1×24＋0×23＋1×21＋0×20＋1×2－1＝（22.5）10任意一个二进制数B，可以展开成多项式之和,即

B=

bn－12n－1+bn－22n－2+…+b121+b020+b－12－1+…+b－m2－m

其中，bI的取值为0或1，n为小数点左边的位数，m为小数点右边的位数。二进制记数法各数位的“权”，整数部分从小数点开始向左分别为1，2，4，8，16，32，…；小数部分的“权”，从小数点向右分别为0.5,0.25,0.125，…。二进制的基数是2，数位的“权”是以2为底数的幂。一般书写时，各数码的“权”隐含在数位之中，即：

B＝bn－1bn－2…b1b0.b–1…b－m

（3）八进制数

八进制记数法的两个特点是：

·采用八个不同的记数符号，即数码：0～7。·采用逢八进一的进位原则。在不同的数位，数码所表示的值等于数码的值乘上相应数位的“权”。例如：

（456.45）8＝4×82＋5×81＋6×80＋4×8－1＋5×8－2＝（302.578125）10一般地，任意一个八进制数可以表示为：

C＝cn－18n－1+cn－28n－2+…+c181+c080+c－18－1+…+c－m8－m

在上式中，Ci只能取0～7之一的值；八进制的基数是8。

（4）十六进制十六进制记数法也有两个特点：

·它采用十六个不同的记数符号，即数码：0～9及A、B、C、D、E、F。其中A表示十进制数10，B表示11，C表示12，D表示13，E表示14，F表示15。

·它采用逢十六进一的进位原则，各位数的“权”是以16为底数的幂。

例如：（2AF）16＝2×162＋A×161＋F×160

＝2×162＋10×16＋15×1＝（687）10一个任意的十六进制数可以表示为：

D＝dn－116n－1+dn－216n－2+…+d1161+d0160+d－116－1+…+d－m16－m在上式中，di可以取0～F之一的值；十六进制的基数是16。

2.十进制数与二进制数之间的转换（1）二进制数转换成十进制数（2）十进制整数转换成二进制整数（3）十进制小数转换成二进制小数（4）任意十进制数转换成二进制数（1）二进制数转换成十进制数

根据公式：

B=bn－12n－1+bn－22n－2+…+b121+b020+b－12－1+…+b－m2－m

将待转换的二进制数按各数位的权展开成一个多项式，求出该多项式的和就可以了。

例如：

（1101.01）2＝1×23＋1×22＋0×21＋1×20＋0×2－1＋1×2－2

＝（13.25）10（2）十进制整数转换成二进制整数逐次除2取余法：

用2逐次去除待转换的十进制整数，直至商为0时停止。每次所得的余数即为二进制数码，先得到的余数在低位，后得到的余数排在高位。例如，将83转换成二进制数，逐次除2取余：

283124112201210025022110

得到的余数从先至后依次为：

1、1、0、0、1、0、1可得到：（83）10＝（1010011）2（3）十进制小数转换成二进制小数乘2取整法：

逐次用2去乘待转换的十进制小数，将每次得到的整数部分（0或1）依次记为二进制小数b－1，b－2，…，b－m。

例如，将0.8125转换为二进制小数，逐次乘2取整：

0.8125×21.625×21.25×20.5×21.0

可得：

（0.8125）10

＝

（0.1101）2

值得注意的是:

并非每一个十进制小数都能转换为有限位的二进制小数，此时可以采用0舍1入的方法进行处理（类似于十进制中的四舍五入的方法）。

例如，将0.335转换为二进制小数，精确到0.001。

0.335×20.67×21.34×20.68×21.536可得：（0.335）10＝（0.0101…）2≈（0.011）2（4）任意十进制数转换成二进制数

对于任意一个既有整数部分，又有小数部分的十进制数，在转换为二进制数时:

只要将它的整数部分和小数部分分别按除2取余和乘2取整的法则转换，最后把所得的结果用小数点连接起来即可。必须注意:

逐次除2取余的余数是按从低位到高位的排列顺序与二进制整数数位相对应的；逐次乘2取整的整数是按从高位向低位的排列顺序与二进制小数数位相对应的。其共同特点是以小数点为中心，逐次向左、右两边排列。（1）八进制、十六进制数转换成十进制数

同二进制数到十进制数的转换，分别套用相应公式。（2）十进制数转换成八进制、十六进制数分别采用除8取余法（对小数部分为乘8取整法）、除16取余法（对小数部分为乘16取整法）。注意：

在进行十进制数转换成十六进制数的过程中，对于采用除16取余法得到的余数和采用乘16取整法得到的整数，若为10～15之间的数值，最后要分别用字符A、B、C、D、E、F代替。

4.二进制数与八、十六进制数的转换（1）二进制数转换成八进制数（2）八进制数转换成二进制数（3）二进制数转换成十六进制数（4）十六进制数转换成二进制数（1）二进制数转换成八进制数

因为23＝8，所以三位二进制数位相当于一个八进制数位，它们之间存在简单直接的关系。

三位一并法：从待转换的二进制数的小数点开始，分别向左、右两个方向进行，将每三位合并为一组，不足三位的以0补齐（注意：整数部分在前面补0，小数部分在末尾补0）。然后每三位二进制数用相应的八进制码（0～7）表示，即完成二－八转换工作。

〖例1〗将（101010001.001）2转换成八进制数。首先以小数点为中心，分别向左右两个方向每三位划分成一组（以逗号作为分界符）：

101，010，001.001，然后，每三位用一个相应八进制数码代替，即得：（101010001.001）2＝（521.1）8

〖例2〗将（10010001.0011）2转换成八进制数。首先分组（以逗号作为分界符）：

10，010，001.001，1

小数点的左边，有一组“10”不足三位，应该补一位0，即应补为“010”；小数点的右边，有一组“1”不足三位，应该补两位0，即应补为“100”。则补0后的分组情况为：

010，010，001.001，100，即得：

（10010001.0011）2＝（221.14）8（2）八进制数转换为二进制数此为上述转换的逆过程。将每一位八进制数码用三位二进制数码代替，即“一分为三”。〖例3〗将（576.35）8转换成二进制数。将八进制数的每位数码依次用三位二进制数代替，即得：

（576.35）8＝（101111110.011101）2（3）二进制数转换为十六进制数

因为24＝16，因此四位二进制数与一位十六进制数是完全对应的。四位一并法：

从待转换的二进制数的小数点开始，分别向左、右两个方向进行，将每四位合并为一组，不足四位的以0补齐。然后每四位二进制数用一个相应的十六进制码（0～F）表示，即完成二－十六转换工作。

〖例4〗将（10110001.0011）2转换成十六进制数。首先以小数点为中心，分别向左右两个方向每四位划分成一组（以逗号作为分界符）：

1011，0001.0011，然后，每四位用一个相应十六进制数码代替，即得：

（10110001.0011）2＝（B1.3）16

（4）十六进制数转换为二进制数与八－二转换类似，采用“一分为四”的方法，把每个十六进制数码用四位二进制数代替就完成了十六－二转换工作。

〖例6〗将（576.35）16转换成二进制数。将八进制数的每位数码依次用三位二进制数代替，即得：（576.35）16

＝

（010101110110.00110101）2

2.2.2计算机中数的表示1．正数与负数2．原码、补码、反码

3．定点数和浮点数

1．正数与负数

在计算机中数的符号也是用数码来表示的，一般用“0”表示正数的符号，“1”表示负数的符号，并放在数的最高位。例如：（01011）2＝（＋11）10（11011）2＝（－11）102．原码、补码、反码在计算机中一个数可以采用原码、补码或反码表示，上面讲到的正数与负数表示法即为原码表示法。一个正数的原码、补码、反码是相同的，而负数就不同了。

原码：数符位以0表示正1表示负，数值部分就是绝对值的二进制表示，不便于加减运算反码：对于正数与原码相同；对于负数，数符位为1，其数值部分为绝对值取反补码：对于正数与原码相同；对于负数，数符位为1，其数值部分为绝对值取反最右加1，即为反码加1可方便地实现正负数的加法运算，符号位如同数值一样参加运算，也允许产生最高位的进位

假设x为n位小数，用小数点左面一位表示数的符号，则：

数的范围：（1－2－n）～－（1－2－n）。

零有两种表示：正零为0.0…0；负零为1.0…0。

数的范围：（1－2－n）～－1。零的表示是唯一的，即：

0.0…0。

数的范围：（1－2－n）～－（1－2－n）。零的表示有两种：正零为0.0…0，负零为1.1…1。

3．定点数和浮点数（1）定点数表示法在机器中，小数点位置固定的数称为定点数，一般采用定点小数表示法，即小数点固定在符号位与最高位之间。有时也采用定点整数表示法，此时将小数点固定在数的最低位的后面。定点数的运算规则比较简单，但不适宜对数值范围变化比较大的数据进行运算。（2）浮点数表示法浮点数可以扩大数的表示范围。浮点数由两部分组成，一部分用以表示数据的有效位，称为尾数；一部分用于表示该数的小数点位置，称为阶码。一般阶码用整数表示，尾数大多用小数表示。一个数N用浮点数表示可以写成：

N＝M·ReM表示尾数，e表示指数，R表示基数。基数一般取2，8，16。一旦机器定义好了基数值，就不能再改变了。因此，在浮点数表示中基数不出现，是隐含的。2.2.3字符数据编码字符包括西文字符和汉字字符。计算机只能识别1和0，因此在计算机内表示的数字、字母、符号等都要以二进制数码的组合来代表，这就是二进制编码。根据不同的用途，有各种各样的编码方案，较常用的有ASCII码、EBCDIC码、汉字编码等。西文字符编码最常用的是ASCII字符编码，即mericanStandardCodeforInformationInterchange（美国信息交换标准代码）。1．ASCII码2．二－十进制编码（BCD码）

3．汉字编码

1．ASCII码

ASCII码（AmericanStandardCodeForInformationInterchange）即美国标准信息交换码，在计算机界，尤其是在微型计算机中得到了广泛使用。这一编码最初是由美国制订的，后来由国际标准组织（ISO）确定为国际标准字符编码。为了和国际标准兼容，我国根据它制定了国家标准，即GB1988。其中除了将货币符号转换为人民币符号外，其他相同。

ASCII码采用七位二进制位编码，共可表示27＝128个字符。计算机中常以8位二进制，即一个字节为单位表示信息，因此将ASCII码的最高位取0。当ASCII码的最高位取1时，又可表示128个字符，这种编码称为扩展ASCII码，主要是一些制符。

在ASCII码表中看出，十进制码值0～32和127（即NUL～SP和DEL）共34个字符称为非图形字符（又称为控制字符）；其余94个字符称为图形字符（又称为普通字符）。在这些字符中，从“0”～“9”、从“A”～“Z”、从“a”～“z”都是顺序排列的，且小写比大写字母码值达32，即位值d5为0或1，这有利与大、小写字母之间的编码转换。

2．二－十进制编码（BCD码）由于人们日常使用的是十进制，而机器内使用的是二进制，所以，需要把十制数表示成二进制码。一位十进制数字，用4位二进制编码来表示可以有多种方法，但常用的是BCD码。四位二进制数表示24即16种状态。只取前10种状态来表示0～9，从左到右每位二进制数的权分别为8，4，2，1，因此又叫8421码。

BCD码有十个不同的码，0000，0001，0010，0011，0100，0101，0110，0111，1000，1001，且它是逢“十”进位的，所以是十进制数，但它的每位是用二进制编码来表示的，因此称为二进制编码的十进制（BinaryCodedDecinel）。BCD码十分直观，可以很容易实现与十进制的转换。例如：（0010100001011001.01110010）BCD

可以方便的认出2859.72是它代表的十进制数。3字符数据编码西文字符最常用的是ASCII字符编码，即AmericanStandardCodeforInformationInterchange(美国信息交换标准代码)，用7位二进制编码，它可以表示27即128个字符EBCDIC码，即ExtendedBinaryCodedDecimalInterchangeCode（扩展的二-十进制交换码），主要用在大型机器中，采用8位二进制编码，有256个编码状态，但只选用其中一部分存放和使用数据的软件会以其他方式保存有关类型的信息，指明这个数据是何类型，不致引起混淆汉字编码用户用输入码输入汉字，输入码比较容易学习和记忆；系统由输入码找到相应的内码，内码是计算机内部对汉字的表示；要在显示器上显示或在打印机上打印出用户所输入的汉字，需要汉字的字形码，系统由内码找到相应的字形码汉字国标码全称是GB2312－80《信息交换用汉字编码字符集——基本集》，1980年发布，是中文信息处理的国家标准，也称汉字交换码，简称GB码。根据统计，把最常用的6763个汉字分成两级：一级汉字有3755个，按汉语拼音排列；二级汉字有3008个，按偏旁部首排列。为了编码，将汉字分成若干个区，每个区中94个汉字。由区号和位号（区中的位置）构成了区位码。例如，“中”位于第54区48位，区位码为5448。区号和位号各加32就构成了国标码，这是为了与ASCII码兼容，每个字节值大于32（0～32为非图形字符码值）。所以，“中”的国标码为8650。汉字机内码一个国标码占两个字节，每个字节最高位仍为“0”；英文字符的机内码是7位ASCII码，最高位也是“0”。因为西文字符和汉字都是字符，为了在计算机内部能够区分是汉字编码还是ASCII码，将国标码的每个字节的最高位由“0”变为“1”，变换后的国标码称为汉字机内码。由此可知汉字机内码的每个字节都大于128，而每个西文字符的ASCII码值均小于128。汉字的输入编码目的：进行汉字的输入要求：编码要尽可能的短，重码要尽量少，容易学容易上手最常用的输入码：五笔字型、智能拼音等。汉字字形码点阵方式矢量方式

图形和图象数据编码（1）基本概念图形一般是指通过绘图软件绘制的由直线、圆、圆弧、任意曲线等组成的画面，即图形是由计算机产生的，且以矢量形式存储；图像是由扫描仪、数字照相机、摄像机等输入的画面，即图像是由真实的场景或现实存在的图片输入计算机产生的，图像以位图形式存储。图形和图象数据编码（2）基本概念动画每一副画面通过一些工具软件对图像素材进行编辑制作而成；动画是用人工合成的方法对真实世界的一种模拟视频对视频信号源（如电视机、摄像机等）经过采样和数字化后保存；而视频影像则是对真实世界的记录图形和图象数据编码（3）一副图像可认为是由若干行和若干列的像素（Pixels）点组成的阵列，每个像素点用若干个二进制进行编码，表示图像的颜色，这就是图像的数字化。图像分辨率颜色深度即每一个像素点表示颜色的二进制位数音频数据的表示采样频率采样频率即每秒钟的采样次数。采样点精度即存放每一个采样点振幅值的二进制位数声道数数据压缩在保留原数据表达的信息不变或者在稍有变动但不致于影响使用的同时尽量减少表达这些信息的数据量就是数据压缩数据压缩有利于节省存储空间，而且可有效提高数据传输效率无损压缩（熵编码）有损压缩无损压缩（1）行程编码法(Run-lengthEncoding,RLE)00000000

111111

777……77

111……111

（8个0）（6个1）（30个7）（50个1）000……00

8888

（30个0）（4个8）可以编码为：8A0A6A1A30A7A50A1A30A0A4A8

无损压缩（2）霍夫曼编码（1）根据符号出现的概率大小按由小到大的次序排序；（2）把概率最小的两个符号组成一个节点P1；（3）重复步骤（2），依次得到节点P2，P3，P4，构成了如图1.17所示的一棵倒立的“树”；其中，P4为树根，称为根节点；P1、P2、P3为树枝，称为枝节点；A、B、C、D和E为树叶；（4）从根节点P4开始到对应于每个符号的树叶，左分支标上“0”，右分支标上“1”；（5）从根节点P4开始顺着树枝到每个叶子分别写出每