第2章-计算机基础

第2章计算机的基础知识

内容提要计算机的运算基础命题逻辑与逻辑代数基础计算机的基本结构与工作原理程序设计基础算法基础数据结构基础基本要求：掌握数制间的转换方法以及数据在计算机内部的表示形式理解逻辑代数、计算机的工作原理、程序设计以及算法与数据结构的基本知识，为学习本书的以下各章和后续课程打好基础十进制

数制：按进位的原则进行计数称为进位计数制，简称数制。十进制：是使用数字1、2、…

、9、0等符号来表示数值且采用“逢十进一”的进位计数制。位权表示法数制的特点： 数字的总个数等于基数。最大的数字比基数小1。每个数字都要乘以基数的幂次，该幂次由每个数字所在的位置决定。任何一个N进制数A可表示为：A＝AnAn－1

…A1A0.A－1A－2

…A－m-m

＝∑Ai×Nii=n二进制

二进制：使用数字0和1等符号来表示数值且采用“逢二进一”的进位计数制。二进制数制的特点：仅使用0和1两个数字。最大的数字为1，最小的数字为0。每个数字都要乘以基数2的幂次，该幂次由每个数字所在的位置决定。二进制加法和乘法运算规则：

0＋0＝0 0×0＝0 0＋1＝1 0×1＝0 1＋0＝1 1×0＝0 1＋1＝1 1×1＝1八进制与十六进制

八进制：使用数字0、1、2、3、4、5、6、7等符号来表示数值的，且采用“逢八进一”的进位计数制。十六进制：使用数字0、1、2、3、4、5、6、7、8、9和A、B、C、D、E、F等符号来表示数值，其中A、B、C、D、E、F分别表示数字10、11、12、13、14、15。十六进制的计数方法为“逢十六进一”。数据在计算机中的表示一、基本概念二进制编码：任何形式的数据在计算机内部均以0和1表示。采用二进制的优点：容易实现，可靠性强，运算简单，通用性强。二、数制及其相互转换数制及其转换

一、数制

1、进位记数制2、计算机中数的表示法——二进制十进制（D）二进制（B）八进制（O）十六进制（H）

0123456789101112131415

01101110010111011110001001101010111100110111101111

012345671011121314151617

0123456789ABCDEF（1）r进制转化成十进制10101(B)=1

24+023+1

22+021+120=21101.11(B)=1

22+021+120+1

2-1+1

2-2=5.75101(O)=1

82+0

81+1

80=6571(O)=7

81+180=57101A(H)=1

163+0162

+1

161+10

160

＝41063、不同进制之间的转换

原则：按权展开，相加之和。（2）十进制转化成r进制

整数部分：除以r取余数，直到商为0，余数从右到左排列。小数部分：乘以r取整数，整数从左到右排列。例100.345(D)=1100100.01011(B)100(D)=144(O)=64(H)100(D)=144(O)=64(H)=1100100(B)1002502

2521226232100010010.34520.69021.3802

0.760

2

1.520

2100812818044110016604616×××××1

1.04十进制小数转换为非十进制小数十进制小数并不是都能够用有限位的其他进制数精确地表示,这时应根据精度要求转换到一定的位数为止，作为其近似值。如果一个十进制数既有整数部分，又有小数部分，则应将整数部分和小数部分分别进行转换。（4）二进制转化成十六进制原则：四位一组整数部分：从右向左进行分组。小数部分：从左向右进行分组。

不足4位补零。

11

0110

1110.1101

01(B)=36E.D4(H)36ED464(H)：64

0110

0100(B)（3）十六进制转化成二进制

原则：一分为四

每一个十六进制数对应二进制的四位。2C1D(H)：2C1D

0010

1100

0001

1101（B）后边补两个零变为0100（5）八进制转化成二进制每一个八进制数对应二进制的三位。(7123)O=(111

001

010

011)B(144)O=(001

100

100)B（6）二进制转化成八进制整数部分：从右向左进行分组。小数部分：从左向右进行分组。转化成八进制时三位一组，不足补零。(1

101

101

110.110

101)B=(1556.65)O数值的表示机器数正数和负数：通常把数的最高位定义为符号位，0表示正，1表示负。机器数表示的范围受到字长和数据类型的限制。若表示一个整数，字长为8位，最大值为01111111，即127。整数和实数整数：带符号数和不带符号数。不同位数和数的表示范围实数：采用“浮点数”原码、反码和补码正数：原码、反码和补码均相同，其最高位为符号位，数值位是数的绝对值。负数原码：符号位为1，数值位是数的绝对值。反码：符号位不变，其余各位将原码按位取反。补码：符号位不变，其余各位将原码按位取反，再在最低位加1形成。给定一个数的真值，求原码、反码和补码。给定一个数的原码、反码和补码，求数的真值。（1）原码（假设字长8位）[X]原=0X，0X+7：00000111+0：000000001|X|，X0-7：10000111-0：10000000(2)反码[X]反=0X，0X+7：00000111+0：000000001|X|，X0-7：11111000-0：11111111（3）补码[X]补=0X，0X+7：00000111+0：000000001|X|+1，X0-7：11111001-0：00000000补码加法（1）-5+4[-5]补：11111011[+4]补：+)0000010011111111[-1]补（2）-9+(-5)[-9]补：11110111[-5]补：+)1111101111110010[-14]补1（3）127+5[+127]补：01111111[+5]补：+)0000010110000100运算结果是一个负数，溢出。

当运算结果超出了数的表达范围，称为溢出。什么情况下发生溢出？同号数相加，异号数相减，有可能产生溢出。

8位补码所能表达的数的范围是-128~+127；16位补码所能表达的数的范围是-32768~+32767课上作业对于二进制数10010101和01000010，对于下列情况分别相当于十进制数的多少？将其看做无符号数将其看做原码将其看做反码将其看做补码给定一个十进制数57，将其分别转换为八进制和十六进制数。定点小数格式

定点小数格式：把小数点固定在数值部分最高位的左边。

N0.N-1N-2......N-m

符号位小数点 数值部分

数的范围：二进制的（m+1）位定点小数格式的数N，所能表示的数的范围为｜N｜≤1－2-m。比例因子：对于绝对值大于1的数，如果直接使用定点小数格式将会产生“溢出”，需根据实际需要使用一个比例因子，将原始数据按该比例缩小，以定点小数格式表示，得出结果后再按该比例扩大得到实际的结果。定点整数格式

定点整数格式：把小数点固定在数值部分最低位的右边。

N0

NnNn-1......N2N1.

符号位数值部分 小数点

数的范围：二进制的（m+1）位定点整数格式的数N，所能表示的数的范围为｜N｜≤2m－1。比例因子：对于绝对值大于该范围的数，如果直接使用定点小数格式也将会产生“溢出”，需根据实际需要选择一个比例因子进行调整，使所表示的数据在规定的范围之内。浮点表示法(M.RE)浮点表示法：小数点的位置不固定，一个浮点数分为阶码和尾数两部分。阶码：用于表示小数点在该数中的位置，是一个整数。尾数：用于表示数的有效数值，可以采用整数或纯小数两种形式可供选择的一种位数分配形式：设字长为32位符号位阶码部分尾数部分

1位 8位 23位

规格化的浮点数：为了提高浮点数表示的精度通常规定其尾数的最高位必须是非零的有效位，称为浮点数的规格化形式。

BCD码与ASCII码

BCD码：是一种二－十进制的编码，使用四位二进制数表示一位十进制数。十进制数与BCD码之间的转换：可按位（或四位二进制数组）直接进行。ASCII(AmericanStandardsCommitteeofInformation)码:是由美国信息交换标准委员会制定的、国际上使用最广泛的字符编码方案。ASCII码的编码方案：采用7位二进制数表示一个字符，把7位二进制数分为高三位（b7b6b5）和低四位（b4b3b2b1）7位ASCII编码表：如表2-5所示，利用该表可以查找数字、运算符、标点符号以及控制符等字符与ASCII码之间的对应关系。西文字符ASCII：用七位二进制表示，存储时占8位，最高位是奇偶校验位。常用字符有128个，编码从0到127。数字0~9，英文字母A~Z，a~z都是顺序排列每个字符占一个字节，即8位二进制位，最高位恒为0。字符的表示汉字编码体系

汉字输入码：由输入设备产生的汉字编码，如区位码、国标码、拼音码、新全拼、新双拼、五笔字型码、简码、表形码、自然码、智能ABC汉字输入码等。汉字内码：用于计算机内部存储和处理的汉字编码，通常由该汉字的国标码的两个字节（最高位置“1”）形成。汉字字形码：确定一个汉字字形点阵的编码，用于汉字显示和打印输出。保留在存储介质中的全部汉字字形码称为字库。汉字交换码：用于在不同的汉字信息处理系统之间或与其他计算机系统之间进行信息交换。汉字地址码：表示汉字字形信息在汉字库中的地址，用于在汉字库中查找汉字字形信息的汉字地址码等。数据校验码

奇偶校验码：在表示数据的N位代码中增加一位奇偶校验位，使N＋1位中“1”的个数为奇数（奇校验）或偶数（偶校验）。海明校验码：在有效信息代码中增加校验位，用来校验代码中“1”的个数是奇数（奇校验）还是偶数（偶校验），通过奇偶校验可以发现代码传输过程中的错误并自动校正。应用：用于计算机各部件之间信息传输以及计算机网络的信息传输。汉字编码(1)汉字输入码国标区位码、全拼、双拼、微软拼音、五笔字形等。(2)汉字交换码国标码(GB2312－80)：我国汉字交换码的国家标准其中：一级汉字：3755个；二级汉字：3008个。汉字分区，每个区94个汉字。

每个汉字占两个字节，国标码最高位为0。

每个汉字占两个字节，机内码最高位为1。区号区中位置例：汉字国标码汉字内码沪2706(0001101100000110B)1001101110000110B

久3035(0001111000100011B)1001111010100011B(3)汉字内码汉字在设备或信息处理系统内部最基本的表达形式。(4)汉字字形码：又称汉字字模，用于汉字的显示或打印。汉字字形的字模数据，以点阵或矢量函数表示。

点阵：16×16、24×24、32×32、48×48。汉字字形码占用的存储空间：例：一个16╳16的汉字：

16╱8

╳16=32字节一个24╳24的汉字：

24╱8

╳24=72字节一个32╳32的汉字：

32╱8

╳32=128字节两个48╳48的汉字：

48╱8

╳48╳2=576字节2.2逻辑代数基础命题命题：有具体意义且能够判断真假的陈述句。命题的真值:命题所具有的值“真”(true，简记为T)或“假”（false,简记为F）称为其真值。命题标识符：表示命题的符号，该标识符称为命题常量。原子命题：不能分解为更为简单的陈述句的命题；复合命题：将原子命题用连接词和标点符号复合而成的命题。连接词“与”（∧）

“与”(∧):两个命题A和B的“与”(又称为A和B的“合取”)是一个复合命题，记为A∧B。当且仅当A和B同时为真时A∧B为真，在其他的情况下A∧B的真值均为假。

A∧B的真值表:

A

BA∧BTTTT

F

FFT

FF

F

F连接词“或”（∨）

“或”（∨）：两个命题A和B的“或”（又称为A和B的“析取”）是一个复合命题，记为A∨B。当且仅当A和B同时为假时A∨B为假，在其他的情况下A∨B的真值均为真。A∨B的真值表：A

B

A∨BTTTT

FTFT

TF

F

F连接词“非”（┑）“非”（┑）：命题A的“非”（又称为A的“否定”）是一个复合命题，记为┑A。若A为真，则┑A为假；若A为假，则┑A为真。┑A的真值表：

A┑ATFFT连接词“异或”（⊕）“异或”（⊕）：两个命题的A和B的“异或”（又称为A和B的“不可兼或”）是一个复合命题，记为A⊕B。当且仅当A和B同时为真或者同时为假时A⊕B为假，在其他的情况下A⊕B的真值为真。A⊕B的真值表：A

B

A⊕BTT

FT

FTFT

TF

F

F连接词“条件”（→）“条件”（→）：两个命题的A和B的“条件”是一个复合命题，记为

A→B,读作“如果A，则B”。当且仅当A的真值为真，B的真值为假时，A→B为假，在其他的情况下A→B的真值均为真。A→B的真值表：A

B

A→BTT

TT

FFFT

TF

FT连接词

“双条件”()

“双条件”():两个命题的A和B的“双条件”（又称为A当且仅当B）是一个复合命题，记为AB，读作“A当且仅当B”。当且仅当A的真值与B的真值相同时，AB为真，否则AB的真值均为假。AB的真值表：A

B

ABTT

TT

FFFT

TF

FT命题公式

命题公式：由命题变元、连接词和括号组成的合式的式子称为命题公式。命题公式等价：如果两个不同的命题公式P和Q，无论其命题变元取什么值它们的真值都相同，则称该两个命题公式等价，记为P＝Q。〖例2-25〗证明┑（A→B）与A∧┑B是等价的。

AB┑（A→B）A∧┑BTTFFTFTTFTFFFFFF命题公式的等价律

其中A、B、C等为命题变元，T表示“真”，F表示“假”零律：A∨F＝A A∧F＝F幺律：A∨T＝T A∧T＝A幂等律：A∨A＝A A∧A＝A求补律：A∨┓A＝TA∧┓A＝F交换律：A∨B＝B∨AA∧B＝B∧A命题公式的等价律（续）

结合律：A∨（B∨C）＝（A∨B）∨C A∧（B∧C）＝（A∧B）∧C分配律：A∧（B∨C）＝A∧B∨A∧CA∨B∧C＝（A∨B）∧（A∨C）吸收律：A∧B∨A∧┓B＝A

（A∨B）∧（A∨┓B）＝A 狄－摩根定律：┓（A∨B）＝┓A∧┓B ┓（A∧B）＝┓A∨┓B双重否定律：┓┓A＝A证明狄－摩根定律

〖例2-26〗证明狄－摩根定律之一：┓（A∧B）＝┓A∨┓B。AB

A∧B┓（A∧B）┓A┓B┓A∨┓BTTTFFFFTFFTFTTFTFTTFTFFFTTTT逻辑代数的等价律

零律：A＋0＝A A0＝0幺律：A＋1＝1 A1＝A幂等律：A＋A＝A AA＝A求补律：A＋Ā＝1 AĀ＝0逻辑代数的等价律（续）

BBBB(A+B)A

(AB)交换律：A＋B＝B＋A AB＝BA结合律：A＋（B＋C）＝（A＋B）＋CA（BC）＝（AB）C分配律：A（B＋C）＝AB＋ACA＋BC＝（A＋B）（A＋C）吸收律：AB＋A＝A

（A＋B）（A＋）＝A 狄－摩根定律：＝Ā

＝Ā＋双重否定律：

＝A

A逻辑函数的化简

〖例2-27〗试将逻辑函数F＝A＋ĀB化简。解：F＝A＋ĀB

＝（A＋Ā）(A＋B) （分配律） ＝1(A＋B) （求补律）＝A＋B （幺律）〖例2-28〗试将逻辑函数F＝AB＋A＋ĀB＋化简。解：F＝AB＋A＋ĀB＋＝A（B＋）＋Ā（B＋） （分配律）＝A＋Ā

（求补律）＝1 （求补律）BBBB

(AB)

(AB)计算机硬件的基本结构

辅助存储器内存储器运算器控制器输入设备输出设备

程序原始数据运算结果控制信息数据运算器

运算器：对二进制数进行运算的部件。它在控制器的控制下执行程序中的指令,完成各种算术运算、逻辑运算、比较运算、移位运算以及字符运算等。运算器的组成：算术逻辑部件（ALU）完成加、减、乘、除等四则运算以及与、或、非、移位等逻辑运算；寄存器用来暂存参加运算的操作数或中间结果，常用的寄存器有累加寄存器、暂存寄存器、标志寄存器和通用寄存器等。运算器的主要技术指标：运算速度，其单位是MIPS（百万指令/秒），通常是按照一定的频度执行各类指令的统计值。存储器

存储器：用来存储数据和程序的部件。存储单位：“位”（bit）、“字节”（byte）、“字”和“字长”存储容量：存储器所包含的存储单元的总数，其单位为KB

（1KB＝210＝1024B）。(1M=1024KB,1GB=1024MB,1T=1024G)存储器的分类：内存储器：又称为主存储器，简称为内存或主存，用来存放现行程序的指令和数据。包括随机存取存储器（RAM）和只读存储器（ROM）等。外存储器：又称为辅助存储器，简称为外存或辅存，用来存放需要长期保存的信息。内存和外存的比较内存直接同CPU进行数据交换，存取速度快，容量小。内存的存取速度直接影响计算机的运算速度。（在计算机的性能指标中内存通常是指RAM的容量）外存（辅存）：计算机把外存数据调到内存，才能和CPU进行数据交换。容量大，速度慢。内存属于易失性存储器，外存是非易失性存储器存储单元地址整个内存分成若干个存储单元，一般一个单元存一个字节。为了能有效地进行数据存取，每个单元必须有唯一的编号（地址）来标识。控制器

控制器：是指挥计算机的各个部件按照指令的功能要求协调工作的部件。控制器的组成：程序计数器（PC）：用来对程序中的指令进行计数，使控制器能依次读取指令；指令寄存器（IR）：在指令执行期间暂时保存正在执行的指令。指令译码器（ID）：用来识别指令的功能，分析指令的操作要求。时序控制电路：用来生成时序信号，以协调在指令执行周期内各部件的工作。微操作控制电路：用来产生各种控制操作命令。输入/输出设备

输入/输出设备：简称为I/O设备，是外部与计算机交换信息的渠道。输入设备：用于输入程序、数据、操作命令、图形、图像以及声音等信息。常用的输入设备有键盘、鼠标器、扫描仪、光笔、数字化仪以及语音输入装置等。输出设备：用于显示或打印程序、运算结果、文字、图形、图像等，也可以播放声音。常用的输出设备有显示器、打印机、XY绘图仪以及声音播放装置等。计算机的指令系统

指令：能被计算机识别并执行的二进制代码，它规定了计算机能完成的某一种操作。指令系统：一台计算机能执行的所有指令的集合。指令的格式：一条指令由操作码和地址码组成。操作码规定了该指令进行的操作种类；地址码给出了操作数、结果以及下一条指令的地址。指令的分类：数据传送型指令数据处理型指令输入输出型指令硬件控制指令指令的执行过程

取指令：即按照指令计数器中的地址，从内存储器中取出指令，并送往指令寄存器中。分析指令：即对指令寄存器中存放的指令进行分析，由操作码确定执行什么操作，由地址码确定操作数的地址。执行指令：即根据分析的结果，由控制器发出完成该操作所需要的一系列控制信息，去完成该指令所要求的操作。上述步骤完成后，指令计数器加1，为执行下一条指令做好准备。如果遇到转移指令，则将转移地址送入指令计数器。计算机组织与系统结构领域的一些主要技术

精简指令集技术（RISC）高速缓冲存储技术（cache）虚拟存储技术指令流水线技术并行处理技术程序设计语言

机器语言：由计算机的指令系统组成，使用机器语言编写的程序计算机能够直接理解并执行，但编程和理解都十分的困难。汇编语言：使用“助忆符”来表示指令的操作码，并使用存储单元或寄存器的名字表示地址码，以便于记忆和书写。高级程序设计语言：是一种与机器的指令系统无关、表达形式更接近于被描述的问题的程序设计语言，便于程序的编写。使用高级程序设计语言编写的程序称为源程序，它必须经过程序设计语言翻译系统的处理后才能执行。面向过程程序设计语言面向对象程序设计语言程序设计

程序设计：是一个使用程序设计语言产生一系列的指令以告诉计算机该做什么的过程。广义的程序设计：需求分析总体设计详细设计编码测试运行与维护结构化程序设计

结构化程序设计：采用自顶向下逐步求精的设计方法和单入口单出口的控制成分（顺序、分支和循环）。

TFTF条件AAB（a）顺序结构（b）选择型分支结构（c）循环结构AB条件良好的程序设计风格

标识符：按意命名、保留字用大写字母、使用统一的缩写规则。表达式：使用括号、使用库函数、条件化简、函数与过程模块化：模块的独立性（高内聚、低耦合）、模块的规模适中。程序行的排列格式：排列格式美观、层次分明、使用统一的缩进格式，同一嵌套深度并列的语句对齐。注释：添加必要的注释，以说明程序、过程和语句等的功能及注意事项。算法

算法：是由一系列规则组成的过程，这些规则确定了一个操作的顺序，以便能在有限步骤内得到特定问题的解。算法的性质：确定性通用性有限性算法的描述工具：自然语言流程图决策表算法描述语言评价算法的优劣时间复杂度T(n)实际上是表示当问题的规模n充分大时，该程序运行时间的一个数量级。空间复杂度运行时所占用的空间的大小易理解性结构好，易理解，易修改等。欧几里德算法（Euclid’sAlgorithm）例2-32〗若给定两个正整数m和n，试写出求它们的最大公因子的算法。 该算法的步骤用文字表述如下： 第1步：读入两个正整数m和n（设m>n）。 第2步：求m和n的余数r＝mod（m,n）。 第3步：用n的值取代m，用r的值取代n。 第4步：判别r的值是否为零，如果r＝0，则m为最大公因子；否则返回第2步。 第5步：输出m的值，即为最大公因子。欧几里德算法（算法描述语言表示）PROCEDUREEuclid； BEGINREAD（m,n）;REPEAT;r:=MOD（m,n）;m:=n;n:=r;UNTILr＝0; WRITE(m)

END欧几里德算法（流程图表示）m=nBEGINREADm，nr=mod(m,n)n=rWRITEmr≠0ENDYN数据结构

数据：描述客观事物的数、字符以及所有能输入到计算机并被计算机程序处