第2章計(jì)算機(jī)的基礎(chǔ)知識

內(nèi)容提要計(jì)算機(jī)的運(yùn)算基礎(chǔ)命題邏輯與邏輯代數(shù)基礎(chǔ)計(jì)算機(jī)的基本結(jié)構(gòu)與工作原理程序設(shè)計(jì)基礎(chǔ)算法基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)基本要求：掌握數(shù)制間的轉(zhuǎn)換方法以及數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的表示形式理解邏輯代數(shù)、計(jì)算機(jī)的工作原理、程序設(shè)計(jì)以及算法與數(shù)據(jù)結(jié)構(gòu)的基本知識，為學(xué)習(xí)本書的以下各章和后續(xù)課程打好基礎(chǔ)十進(jìn)制

數(shù)制：按進(jìn)位的原則進(jìn)行計(jì)數(shù)稱為進(jìn)位計(jì)數(shù)制，簡稱數(shù)制。十進(jìn)制：是使用數(shù)字1、2、…

、9、0等符號來表示數(shù)值且采用“逢十進(jìn)一”的進(jìn)位計(jì)數(shù)制。位權(quán)表示法數(shù)制的特點(diǎn)： 數(shù)字的總個(gè)數(shù)等于基數(shù)。最大的數(shù)字比基數(shù)小1。每個(gè)數(shù)字都要乘以基數(shù)的冪次，該冪次由每個(gè)數(shù)字所在的位置決定。任何一個(gè)N進(jìn)制數(shù)A可表示為：A＝AnAn－1

…A1A0.A－1A－2

…A－m-m

＝∑Ai×Nii=n二進(jìn)制

二進(jìn)制：使用數(shù)字0和1等符號來表示數(shù)值且采用“逢二進(jìn)一”的進(jìn)位計(jì)數(shù)制。二進(jìn)制數(shù)制的特點(diǎn)：僅使用0和1兩個(gè)數(shù)字。最大的數(shù)字為1，最小的數(shù)字為0。每個(gè)數(shù)字都要乘以基數(shù)2的冪次，該冪次由每個(gè)數(shù)字所在的位置決定。二進(jìn)制加法和乘法運(yùn)算規(guī)則：

0＋0＝0 0×0＝0 0＋1＝1 0×1＝0 1＋0＝1 1×0＝0 1＋1＝1 1×1＝1八進(jìn)制與十六進(jìn)制

八進(jìn)制：使用數(shù)字0、1、2、3、4、5、6、7等符號來表示數(shù)值的，且采用“逢八進(jìn)一”的進(jìn)位計(jì)數(shù)制。十六進(jìn)制：使用數(shù)字0、1、2、3、4、5、6、7、8、9和A、B、C、D、E、F等符號來表示數(shù)值，其中A、B、C、D、E、F分別表示數(shù)字10、11、12、13、14、15。十六進(jìn)制的計(jì)數(shù)方法為“逢十六進(jìn)一”。數(shù)據(jù)在計(jì)算機(jī)中的表示一、基本概念二進(jìn)制編碼：任何形式的數(shù)據(jù)在計(jì)算機(jī)內(nèi)部均以0和1表示。采用二進(jìn)制的優(yōu)點(diǎn)：容易實(shí)現(xiàn)，可靠性強(qiáng)，運(yùn)算簡單，通用性強(qiáng)。二、數(shù)制及其相互轉(zhuǎn)換數(shù)制及其轉(zhuǎn)換

一、數(shù)制

1、進(jìn)位記數(shù)制2、計(jì)算機(jī)中數(shù)的表示法——二進(jìn)制十進(jìn)制（D）二進(jìn)制（B）八進(jìn)制（O）十六進(jìn)制（H）0123456789101112131415011011100101110111100010011010101111001101111011110123456710111213141516170123456789ABCDEF（1）r進(jìn)制轉(zhuǎn)化成十進(jìn)制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、不同進(jìn)制之間的轉(zhuǎn)換

原則：按權(quán)展開，相加之和。（2）十進(jìn)制轉(zhuǎn)化成r進(jìn)制

整數(shù)部分：除以r取余數(shù)，直到商為0，余數(shù)從右到左排列。小數(shù)部分：乘以r取整數(shù)，整數(shù)從左到右排列。例100.345(D)=1100100.01011(B)100(D)=144(O)=64(H)100(D)=144(O)=64(H)=1100100(B)10025022521226232100010010.34520.69021.3802

0.7602

1.5202100812818044110016604616×××××1

1.04十進(jìn)制小數(shù)轉(zhuǎn)換為非十進(jìn)制小數(shù)十進(jìn)制小數(shù)并不是都能夠用有限位的其他進(jìn)制數(shù)精確地表示,這時(shí)應(yīng)根據(jù)精度要求轉(zhuǎn)換到一定的位數(shù)為止，作為其近似值。如果一個(gè)十進(jìn)制數(shù)既有整數(shù)部分，又有小數(shù)部分，則應(yīng)將整數(shù)部分和小數(shù)部分分別進(jìn)行轉(zhuǎn)換。（4）二進(jìn)制轉(zhuǎn)化成十六進(jìn)制原則：四位一組整數(shù)部分：從右向左進(jìn)行分組。小數(shù)部分：從左向右進(jìn)行分組。

不足4位補(bǔ)零。

11

0110

1110.1101

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

0110

0100(B)（3）十六進(jìn)制轉(zhuǎn)化成二進(jìn)制

原則：一分為四

每一個(gè)十六進(jìn)制數(shù)對應(yīng)二進(jìn)制的四位。2C1D(H)：2C1D

0010

1100

0001

1101（B）后邊補(bǔ)兩個(gè)零變?yōu)?100（5）八進(jìn)制轉(zhuǎn)化成二進(jìn)制每一個(gè)八進(jìn)制數(shù)對應(yīng)二進(jìn)制的三位。(7123)O=(111

001

010

011)B(144)O=(001

100

100)B（6）二進(jìn)制轉(zhuǎn)化成八進(jìn)制整數(shù)部分：從右向左進(jìn)行分組。小數(shù)部分：從左向右進(jìn)行分組。轉(zhuǎn)化成八進(jìn)制時(shí)三位一組，不足補(bǔ)零。(1

101

101

110.110

101)B=(1556.65)O數(shù)值的表示機(jī)器數(shù)正數(shù)和負(fù)數(shù)：通常把數(shù)的最高位定義為符號位，0表示正，1表示負(fù)。機(jī)器數(shù)表示的范圍受到字長和數(shù)據(jù)類型的限制。若表示一個(gè)整數(shù)，字長為8位，最大值為01111111，即127。整數(shù)和實(shí)數(shù)整數(shù)：帶符號數(shù)和不帶符號數(shù)。不同位數(shù)和數(shù)的表示范圍實(shí)數(shù)：采用“浮點(diǎn)數(shù)”原碼、反碼和補(bǔ)碼正數(shù)：原碼、反碼和補(bǔ)碼均相同，其最高位為符號位，數(shù)值位是數(shù)的絕對值。負(fù)數(shù)原碼：符號位為1，數(shù)值位是數(shù)的絕對值。反碼：符號位不變，其余各位將原碼按位取反。補(bǔ)碼：符號位不變，其余各位將原碼按位取反，再在最低位加1形成。給定一個(gè)數(shù)的真值，求原碼、反碼和補(bǔ)碼。給定一個(gè)數(shù)的原碼、反碼和補(bǔ)碼，求數(shù)的真值。（1）原碼（假設(shè)字長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）補(bǔ)碼[X]補(bǔ)=0X，0X+7：00000111+0：000000001|X|+1，X0-7：11111001-0：00000000補(bǔ)碼加法（1）-5+4[-5]補(bǔ)：11111011[+4]補(bǔ)：+)0000010011111111[-1]補(bǔ)（2）-9+(-5)[-9]補(bǔ)：11110111[-5]補(bǔ)：+)1111101111110010[-14]補(bǔ)1（3）127+5[+127]補(bǔ)：01111111[+5]補(bǔ)：+)0000010110000100運(yùn)算結(jié)果是一個(gè)負(fù)數(shù)，溢出。

當(dāng)運(yùn)算結(jié)果超出了數(shù)的表達(dá)范圍，稱為溢出。什么情況下發(fā)生溢出？同號數(shù)相加，異號數(shù)相減，有可能產(chǎn)生溢出。

8位補(bǔ)碼所能表達(dá)的數(shù)的范圍是-128~+127；16位補(bǔ)碼所能表達(dá)的數(shù)的范圍是-32768~+32767課上作業(yè)對于二進(jìn)制數(shù)10010101和01000010，對于下列情況分別相當(dāng)于十進(jìn)制數(shù)的多少？將其看做無符號數(shù)將其看做原碼將其看做反碼將其看做補(bǔ)碼給定一個(gè)十進(jìn)制數(shù)57，將其分別轉(zhuǎn)換為八進(jìn)制和十六進(jìn)制數(shù)。定點(diǎn)小數(shù)格式

定點(diǎn)小數(shù)格式：把小數(shù)點(diǎn)固定在數(shù)值部分最高位的左邊。

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

符號位小數(shù)點(diǎn) 數(shù)值部分

數(shù)的范圍：二進(jìn)制的（m+1）位定點(diǎn)小數(shù)格式的數(shù)N，所能表示的數(shù)的范圍為｜N｜≤1－2-m。比例因子：對于絕對值大于1的數(shù)，如果直接使用定點(diǎn)小數(shù)格式將會(huì)產(chǎn)生“溢出”，需根據(jù)實(shí)際需要使用一個(gè)比例因子，將原始數(shù)據(jù)按該比例縮小，以定點(diǎn)小數(shù)格式表示，得出結(jié)果后再按該比例擴(kuò)大得到實(shí)際的結(jié)果。定點(diǎn)整數(shù)格式

定點(diǎn)整數(shù)格式：把小數(shù)點(diǎn)固定在數(shù)值部分最低位的右邊。

N0

NnNn-1......N2N1.

符號位數(shù)值部分 小數(shù)點(diǎn)

數(shù)的范圍：二進(jìn)制的（m+1）位定點(diǎn)整數(shù)格式的數(shù)N，所能表示的數(shù)的范圍為｜N｜≤2m－1。比例因子：對于絕對值大于該范圍的數(shù)，如果直接使用定點(diǎn)小數(shù)格式也將會(huì)產(chǎn)生“溢出”，需根據(jù)實(shí)際需要選擇一個(gè)比例因子進(jìn)行調(diào)整，使所表示的數(shù)據(jù)在規(guī)定的范圍之內(nèi)。浮點(diǎn)表示法(M.RE)浮點(diǎn)表示法：小數(shù)點(diǎn)的位置不固定，一個(gè)浮點(diǎn)數(shù)分為階碼和尾數(shù)兩部分。階碼：用于表示小數(shù)點(diǎn)在該數(shù)中的位置，是一個(gè)整數(shù)。尾數(shù)：用于表示數(shù)的有效數(shù)值，可以采用整數(shù)或純小數(shù)兩種形式可供選擇的一種位數(shù)分配形式：設(shè)字長為32位符號位階碼部分尾數(shù)部分

1位 8位 23位

規(guī)格化的浮點(diǎn)數(shù)：為了提高浮點(diǎn)數(shù)表示的精度通常規(guī)定其尾數(shù)的最高位必須是非零的有效位，稱為浮點(diǎn)數(shù)的規(guī)格化形式。BCD碼與ASCII碼

BCD碼：是一種二－十進(jìn)制的編碼，使用四位二進(jìn)制數(shù)表示一位十進(jìn)制數(shù)。十進(jìn)制數(shù)與BCD碼之間的轉(zhuǎn)換：可按位（或四位二進(jìn)制數(shù)組）直接進(jìn)行。ASCII(AmericanStandardsCommitteeofInformation)碼:是由美國信息交換標(biāo)準(zhǔn)委員會(huì)制定的、國際上使用最廣泛的字符編碼方案。ASCII碼的編碼方案：采用7位二進(jìn)制數(shù)表示一個(gè)字符，把7位二進(jìn)制數(shù)分為高三位（b7b6b5）和低四位（b4b3b2b1）7位ASCII編碼表：如表2-5所示，利用該表可以查找數(shù)字、運(yùn)算符、標(biāo)點(diǎn)符號以及控制符等字符與ASCII碼之間的對應(yīng)關(guān)系。西文字符ASCII：用七位二進(jìn)制表示，存儲(chǔ)時(shí)占8位，最高位是奇偶校驗(yàn)位。常用字符有128個(gè)，編碼從0到127。數(shù)字0~9，英文字母A~Z，a~z都是順序排列每個(gè)字符占一個(gè)字節(jié)，即8位二進(jìn)制位，最高位恒為0。字符的表示漢字編碼體系

漢字輸入碼：由輸入設(shè)備產(chǎn)生的漢字編碼，如區(qū)位碼、國標(biāo)碼、拼音碼、新全拼、新雙拼、五筆字型碼、簡碼、表形碼、自然碼、智能ABC漢字輸入碼等。漢字內(nèi)碼：用于計(jì)算機(jī)內(nèi)部存儲(chǔ)和處理的漢字編碼，通常由該漢字的國標(biāo)碼的兩個(gè)字節(jié)（最高位置“1”）形成。漢字字形碼：確定一個(gè)漢字字形點(diǎn)陣的編碼，用于漢字顯示和打印輸出。保留在存儲(chǔ)介質(zhì)中的全部漢字字形碼稱為字庫。漢字交換碼：用于在不同的漢字信息處理系統(tǒng)之間或與其他計(jì)算機(jī)系統(tǒng)之間進(jìn)行信息交換。漢字地址碼：表示漢字字形信息在漢字庫中的地址，用于在漢字庫中查找漢字字形信息的漢字地址碼等。數(shù)據(jù)校驗(yàn)碼

奇偶校驗(yàn)碼：在表示數(shù)據(jù)的N位代碼中增加一位奇偶校驗(yàn)位，使N＋1位中“1”的個(gè)數(shù)為奇數(shù)（奇校驗(yàn)）或偶數(shù)（偶校驗(yàn)）。海明校驗(yàn)碼：在有效信息代碼中增加校驗(yàn)位，用來校驗(yàn)代碼中“1”的個(gè)數(shù)是奇數(shù)（奇校驗(yàn)）還是偶數(shù)（偶校驗(yàn)），通過奇偶校驗(yàn)可以發(fā)現(xiàn)代碼傳輸過程中的錯(cuò)誤并自動(dòng)校正。應(yīng)用：用于計(jì)算機(jī)各部件之間信息傳輸以及計(jì)算機(jī)網(wǎng)絡(luò)的信息傳輸。漢字編碼(1)漢字輸入碼國標(biāo)區(qū)位碼、全拼、雙拼、微軟拼音、五筆字形等。(2)漢字交換碼國標(biāo)碼(GB2312－80)：我國漢字交換碼的國家標(biāo)準(zhǔn)其中：一級漢字：3755個(gè)；二級漢字：3008個(gè)。漢字分區(qū)，每個(gè)區(qū)94個(gè)漢字。

每個(gè)漢字占兩個(gè)字節(jié)，國標(biāo)碼最高位為0。

每個(gè)漢字占兩個(gè)字節(jié)，機(jī)內(nèi)碼最高位為1。區(qū)號區(qū)中位置例：漢字國標(biāo)碼漢字內(nèi)碼滬2706(0001101100000110B)1001101110000110B久3035(0001111000100011B)1001111010100011B(3)漢字內(nèi)碼漢字在設(shè)備或信息處理系統(tǒng)內(nèi)部最基本的表達(dá)形式。(4)漢字字形碼：又稱漢字字模，用于漢字的顯示或打印。漢字字形的字模數(shù)據(jù)，以點(diǎn)陣或矢量函數(shù)表示。 點(diǎn)陣：16×16、24×24、32×32、48×48。漢字字形碼占用的存儲(chǔ)空間：例：一個(gè)16╳16的漢字：16╱8

╳16=32字節(jié)一個(gè)24╳24的漢字：24╱8

╳24=72字節(jié)一個(gè)32╳32的漢字：32╱8

╳32=128字節(jié)兩個(gè)48╳48的漢字：48╱8

╳48╳2=576字節(jié)2.2邏輯代數(shù)基礎(chǔ)命題命題：有具體意義且能夠判斷真假的陳述句。命題的真值:命題所具有的值“真”(true，簡記為T)或“假”（false,簡記為F）稱為其真值。命題標(biāo)識符：表示命題的符號，該標(biāo)識符稱為命題常量。原子命題：不能分解為更為簡單的陳述句的命題；復(fù)合命題：將原子命題用連接詞和標(biāo)點(diǎn)符號復(fù)合而成的命題。連接詞“與”（∧）

“與”(∧):兩個(gè)命題A和B的“與”(又稱為A和B的“合取”)是一個(gè)復(fù)合命題，記為A∧B。當(dāng)且僅當(dāng)A和B同時(shí)為真時(shí)A∧B為真，在其他的情況下A∧B的真值均為假。

A∧B的真值表:

A

BA∧BTTTTFFFTFFFF連接詞“或”（∨）

“或”（∨）：兩個(gè)命題A和B的“或”（又稱為A和B的“析取”）是一個(gè)復(fù)合命題，記為A∨B。當(dāng)且僅當(dāng)A和B同時(shí)為假時(shí)A∨B為假，在其他的情況下A∨B的真值均為真。A∨B的真值表：A

B

A∨BTTTTFTFTTFFF連接詞“非”（┑）“非”（┑）：命題A的“非”（又稱為A的“否定”）是一個(gè)復(fù)合命題，記為┑A(chǔ)。若A為真，則┑A(chǔ)為假；若A為假，則┑A(chǔ)為真。┑A(chǔ)的真值表：

A┑A(chǔ)TFFT連接詞“異或”（⊕）“異或”（⊕）：兩個(gè)命題的A和B的“異或”（又稱為A和B的“不可兼或”）是一個(gè)復(fù)合命題，記為A⊕B。當(dāng)且僅當(dāng)A和B同時(shí)為真或者同時(shí)為假時(shí)A⊕B為假，在其他的情況下A⊕B的真值為真。A⊕B的真值表：A

B

A⊕BTTFTFTFTTFFF連接詞“條件”（→）“條件”（→）：兩個(gè)命題的A和B的“條件”是一個(gè)復(fù)合命題，記為

A→B,讀作“如果A，則B”。當(dāng)且僅當(dāng)A的真值為真，B的真值為假時(shí)，A→B為假，在其他的情況下A→B的真值均為真。A→B的真值表：A

B

A→BTTTTFFFTTFFT連接詞“雙條件”()

“雙條件”():兩個(gè)命題的A和B的“雙條件”（又稱為A當(dāng)且僅當(dāng)B）是一個(gè)復(fù)合命題，記為AB，讀作“A當(dāng)且僅當(dāng)B”。當(dāng)且僅當(dāng)A的真值與B的真值相同時(shí)，AB為真，否則AB的真值均為假。AB的真值表：A

B

ABTTTTFFFTTFFT命題公式

命題公式：由命題變元、連接詞和括號組成的合式的式子稱為命題公式。命題公式等價(jià)：如果兩個(gè)不同的命題公式P和Q，無論其命題變元取什么值它們的真值都相同，則稱該兩個(gè)命題公式等價(jià)，記為P＝Q。〖例2-25〗證明┑（A→B）與A∧┑B是等價(jià)的。

AB┑（A→B）A∧┑BTTFFTFTTFTFFFFFF命題公式的等價(jià)律

其中A、B、C等為命題變元，T表示“真”，F(xiàn)表示“假”零律：A∨F＝A A∧F＝F幺律：A∨T＝T A∧T＝A冪等律：A∨A＝A A∧A＝A求補(bǔ)律：A∨┓A＝TA∧┓A＝F交換律：A∨B＝B∨AA∧B＝B∧A命題公式的等價(jià)律（續(xù)）

結(jié)合律：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邏輯代數(shù)的等價(jià)律

零律：A＋0＝A A0＝0幺律：A＋1＝1 A1＝A冪等律：A＋A＝A AA＝A求補(bǔ)律：A＋ā＝1 A?。?邏輯代數(shù)的等價(jià)律（續(xù)）

BBBB(A+B)A(AB)交換律：A＋B＝B＋A AB＝BA結(jié)合律：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 狄－摩根定律：＝ā

＝?。p重否定律：

＝A

A邏輯函數(shù)的化簡

〖例2-27〗試將邏輯函數(shù)F＝A＋āB化簡。解：F＝A＋āB ＝（A＋?。?A＋B) （分配律） ＝1(A＋B) （求補(bǔ)律）＝A＋B （幺律）〖例2-28〗試將邏輯函數(shù)F＝AB＋A＋āB＋化簡。解：F＝AB＋A＋āB＋＝