計(jì)算機(jī)科學(xué)導(dǎo)論課件第2章-第三版

進(jìn)位制的概念不同進(jìn)制間的轉(zhuǎn)換計(jì)算機(jī)中的二進(jìn)制四則運(yùn)算一切都是邏輯（Logic）計(jì)算機(jī)中的存儲(chǔ)談0與1的美

1/TP

第2章神奇的0與1第1節(jié)進(jìn)位制的概念

2十進(jìn)制（Decimal)二進(jìn)制（Binary）八進(jìn)制（Octonary）與十六進(jìn)制（Hexadecimal）

基數(shù)（Base）與位權(quán)（Weight）十進(jìn)制（Decimal）

3十進(jìn)制的整數(shù)391，觀察可發(fā)現(xiàn)該數(shù)具有2個(gè)性質(zhì):每一位都介于0~9之間；這個(gè)數(shù)可以分解成為39110=3×102+9×101+1×100。逢十向高位進(jìn)一我們通常用數(shù)的右下標(biāo)，表明它的進(jìn)位制，例如39110就表示一個(gè)十進(jìn)制數(shù)391。有的書(shū)也用(391)10表示同樣的意義。在這本書(shū)里，我們約定如果一個(gè)數(shù)不加下標(biāo)就默認(rèn)它是十進(jìn)制數(shù)。二進(jìn)制（Binary）

4二進(jìn)制是逢二進(jìn)位，二進(jìn)制的數(shù)是由0或1組成的。十進(jìn)制中的0、1、2、3、4，在二進(jìn)制中對(duì)應(yīng)的用0、1、10、11、100來(lái)表示。計(jì)算機(jī)采用的是二進(jìn)制在計(jì)算機(jī)的世界里，二進(jìn)制數(shù)的1位稱(chēng)為1比特（bit），把連續(xù)的8個(gè)比特稱(chēng)為一個(gè)字節(jié)（byte）。二進(jìn)制只有兩個(gè)十進(jìn)制數(shù)8(=23)用二進(jìn)制表示需要3個(gè)比特，十進(jìn)制數(shù)4096(=212)用二進(jìn)制表示需要12個(gè)比特。

二進(jìn)制數(shù)的長(zhǎng)度隨著數(shù)值增大快速增長(zhǎng)。因?yàn)槎M(jìn)制只有兩個(gè)可用的數(shù)，較大的數(shù)就需要用很多位比特來(lái)表示。八進(jìn)制（Octonary）與十六進(jìn)制（Hexdecimal）

5八進(jìn)制數(shù)的一位數(shù)表示0~7之間的數(shù)值，逢八進(jìn)位，八進(jìn)制的數(shù)是由0~7組成的。十六進(jìn)制數(shù)的一位數(shù)表示0~15之間的數(shù)值，逢十六進(jìn)位，而人類(lèi)世界的十進(jìn)制數(shù)位只能表示0~9因此在十六進(jìn)制中，我們用A、B、C、D、E、F分別代表十進(jìn)制的10、11、12、13、14、15。進(jìn)制基數(shù)進(jìn)位原則基本符號(hào)二進(jìn)制（Bin）八進(jìn)制（Oct）十進(jìn)制（Dec）十六進(jìn)制（Hex）281016逢2進(jìn)1逢8進(jìn)1逢10進(jìn)1逢16進(jìn)10,10,1,2,3,4,5,6,70,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F基數(shù)（Base）與位權(quán)（Weight）

6如果某一個(gè)進(jìn)制采用R個(gè)基本符號(hào)，我們就稱(chēng)它為基R進(jìn)制，R稱(chēng)為進(jìn)制的“基數(shù)（base）”。例如二進(jìn)制的基數(shù)是2，十進(jìn)制的基數(shù)是10。進(jìn)制中每一位的單位值稱(chēng)為“位權(quán)（weight）”。在整數(shù)部分，最低位的位權(quán)為R0，第i位的位權(quán)為Ri；對(duì)于小數(shù)部分，小數(shù)點(diǎn)向右第j位的位權(quán)R-j。在十進(jìn)制中，個(gè)位的位權(quán)是100，百位的位權(quán)是102，所以數(shù)7在個(gè)位時(shí)，它的值是7，在百位時(shí)它的值就是700=7×102。在二進(jìn)制中，最低位的位權(quán)是1=20，所以數(shù)1在最低位的值是1=1×20。小數(shù)是同樣的道理。第2節(jié)不同進(jìn)制間的轉(zhuǎn)換

7二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)R進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)十進(jìn)制數(shù)轉(zhuǎn)換為R進(jìn)制數(shù)二、八、十六進(jìn)制的巧妙轉(zhuǎn)換進(jìn)制轉(zhuǎn)換

8任何整數(shù)都可用各種進(jìn)制表示如何證明？最簡(jiǎn)單的證明方式就是任意R進(jìn)制的數(shù)，都可以轉(zhuǎn)換成十進(jìn)制的形式：R1進(jìn)制十進(jìn)制R2進(jìn)制二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)

9把一個(gè)二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)的時(shí)候，基本方法是用某位的數(shù)值（0或者1）乘以該位的位權(quán)。可以利用查表的方法輔助理解。例如下表：B110110101二進(jìn)制位權(quán)282726252423222120十進(jìn)制值25612864321684211101101012

=1×28+1×27+0×26+1×25+1×24+0×23+1×22+0×21+1×20=256+128+32+16+4+1=437二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)

10計(jì)算機(jī)并不是用查表的方式來(lái)轉(zhuǎn)換進(jìn)制的，實(shí)際上，計(jì)算機(jī)里的進(jìn)制轉(zhuǎn)換是通過(guò)一定的“算法”完成的。請(qǐng)回顧二進(jìn)制數(shù)的組成：1101101012=1×28+1×27+0×26+1×25+1×24+0×23+1×22+0×21+1×20將二進(jìn)制數(shù)的每一位都用一個(gè)符號(hào)替代，例如第i位記為ai，那么n+1位二進(jìn)制數(shù)A就可以表示為A=anan-1…a1a0。那么，二進(jìn)制數(shù)A轉(zhuǎn)換為十進(jìn)制數(shù)的算法就是:A=an×2n+an-1×2n-1+…+a1×21+a0×20程序示例-二到十進(jìn)制的轉(zhuǎn)換

11程序定義了一個(gè)變量d來(lái)存放轉(zhuǎn)換后的十進(jìn)制數(shù)值，并把d的初始化值設(shè)為0。在“for”循環(huán)中實(shí)現(xiàn)對(duì)二進(jìn)制數(shù)每一位數(shù)值和位權(quán)的乘積和累加。函數(shù)len(b)獲得的是字符串b的長(zhǎng)度，例如len("1010")=4。字符串b其實(shí)是一個(gè)數(shù)組，b[0]表示數(shù)組的第一個(gè)單元，存放的是二進(jìn)制數(shù)的最高位，位權(quán)為2len(b)-i-1。

b[len(b)-1]表示數(shù)組的最后一個(gè)單元。第6行語(yǔ)句計(jì)算位權(quán)#<程序2.1：2-to-10進(jìn)制轉(zhuǎn)換>b=input(“Pleaseenterabinarynumber:”)d=0;foriinrange(0,len(b)):ifb[i]=='1':weight=2**(len(b)-i-1)d=d+weight;print(d)程序示例-改進(jìn)后二到十進(jìn)制的轉(zhuǎn)換

12計(jì)算機(jī)中執(zhí)行指數(shù)運(yùn)算往往比單純的加減乘除運(yùn)算要復(fù)雜得多，因此也比較費(fèi)時(shí)。為了更快地完成進(jìn)制轉(zhuǎn)換，對(duì)前面的python程序進(jìn)行了改進(jìn)。首先算出二進(jìn)制數(shù)最高位的位權(quán)，即weight=2**(len(b)-1)。在隨后的for循環(huán)中，不需要重復(fù)計(jì)算2的i次方冪了，而是用整數(shù)除法，即weight=weight//2，得到每一位的位權(quán)。第8行中的“//”是整數(shù)除法#<程序2.2：改進(jìn)后的2-to-10進(jìn)制轉(zhuǎn)換>b=input(“Pleaseenterabinarynumber:”)d=0;weight=2**(len(b)-1);foriinrange(0,len(b)):ifb[i]=='1':d=d+weight;weight=weight//2;print(d)R進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)

13把前頁(yè)的進(jìn)制轉(zhuǎn)換算法推廣到把R進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)的算法。R進(jìn)制中各位的位權(quán)是以R為底的冪。對(duì)于一個(gè)R進(jìn)制數(shù)A=anan-1…ai…a1a0而言，它的一個(gè)數(shù)位ai乘以該位的位權(quán)就得到該位的值，把每一位的值加起來(lái)就得到R進(jìn)制數(shù)A在十進(jìn)制中的值：A=anan-1…ai…a1a0=an×Rn+an-1×Rn-1+…+ai×Ri+…+a1×R1+a0×R0，其中n和i為正整數(shù)，且0≤i＜n，Ri是第i位的權(quán)。數(shù)如前面所說(shuō)，在R進(jìn)制中的數(shù)使用0~(R-1)個(gè)數(shù)符號(hào)來(lái)表示，因此，數(shù)ai應(yīng)滿(mǎn)足0≤ai＜R。通過(guò)這個(gè)算法，計(jì)算機(jī)就能很容易地對(duì)各種進(jìn)制進(jìn)行轉(zhuǎn)換。例如將八進(jìn)制數(shù)10238轉(zhuǎn)換為十進(jìn)制數(shù)的例子：(1023)8=1×83+0×82+2×81+3×80=51210+1610+310=(531)10。即八進(jìn)制數(shù)1023的數(shù)值等于十進(jìn)制數(shù)531的數(shù)值。R進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)

14小數(shù)的進(jìn)制轉(zhuǎn)換算法與整數(shù)的轉(zhuǎn)換算法基本相同。將基數(shù)為R的小數(shù)轉(zhuǎn)換為十進(jìn)制，只要將各個(gè)數(shù)位數(shù)與相應(yīng)位權(quán)的乘積相累加，就可以得到相對(duì)應(yīng)的十進(jìn)制數(shù)。當(dāng)從R進(jìn)制轉(zhuǎn)換到十進(jìn)制時(shí)，可以把小數(shù)點(diǎn)作為起點(diǎn)，分別向左右兩邊進(jìn)行，即對(duì)其整數(shù)部分和小數(shù)部分分別轉(zhuǎn)換。寫(xiě)Python程序時(shí)，可以利用一個(gè)Python自帶的字符函數(shù)partition()來(lái)找出小數(shù)點(diǎn)前面的字串和小數(shù)點(diǎn)后面的字串。例如：輸入一個(gè)二進(jìn)制小數(shù)，并將其分解為整數(shù)部分字符串和小數(shù)部分字符串的實(shí)際操作結(jié)果為：>>>bin=”1101.01”>>>(x,t,y)=bin.partition(‘.’)#結(jié)果是x=’1101’,t=’.’,y=’01’十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)

15將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)就是要把這個(gè)數(shù)分解為若干二進(jìn)制位權(quán)的和，十進(jìn)制數(shù)的大小一定處于兩個(gè)二進(jìn)制位權(quán)之間。例如通過(guò)下表將十進(jìn)制數(shù)437轉(zhuǎn)換為二進(jìn)制數(shù)：首先選擇不大于437的最大的位權(quán)，即28=256。于是，437就分解為256+181兩個(gè)數(shù)和。然后再選擇不大于181的最大位權(quán)，即27=128。于是，437就分解為256+128+53......以此類(lèi)推,可得出437=256+128+32+16+4+1。查看表2.5的二進(jìn)制位權(quán)值，得到437的二進(jìn)制為1101101012。十進(jìn)制值2561286432168421二進(jìn)制位權(quán)282726252423222120B110110101十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)

16計(jì)算機(jī)不用查表的方法，用算法把十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)。基本思想是先求出轉(zhuǎn)換后二進(jìn)制數(shù)的最低位，然后依次算出高位。輸入一個(gè)十進(jìn)制數(shù)x，輸出x的二進(jìn)制數(shù)。其算法步驟如下：將x除以2；記錄所得的余數(shù)r（必然是0或1）；用得到的商作為新的被除數(shù)x；重復(fù)步驟1到3，直到x為0。倒序輸出每次除法得到的余數(shù)，所得的0、1字符串就是x的二進(jìn)制數(shù)。十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)-例子

17例如將十進(jìn)制數(shù)19轉(zhuǎn)換為二進(jìn)制數(shù)的步驟為：19/2=9余1，代表二進(jìn)制的最低位是1；以此類(lèi)推，9/2=4余14/2=2余02/2=1余01/2=0余1按逆序輸出的結(jié)果是1910=100112。程序示例-十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)

18用while循環(huán)實(shí)現(xiàn)算法的第1到第4步，只要商不為0，就繼續(xù)循環(huán)。用變量r=x%2計(jì)算x被2除所得的余數(shù)。用運(yùn)算x=x//2獲得x被2整除所得的商。用運(yùn)算Rs=[r]+Rs獲得一個(gè)列表結(jié)構(gòu)（list）Rs，并把余數(shù)r加入列表的頭部。第9~10行的“for”循環(huán)是從最高位到最低位依次輸出結(jié)果。#<程序2.3：整數(shù)的10-to-2進(jìn)制轉(zhuǎn)換>x=int(input("Pleaseenteradecimalnumber:"))r=0;Rs=[];while(x!=0): r=x%2 x=x//2 Rs=[r]+Rsforiinrange(0,len(Rs)):print(Rs[i],end='‘)程序示例-列表（List）的涵義

19列表是一組按順序排列的元素的集合。和字符串一樣，Python的列表也通過(guò)索引（index）引用其中的元素。從列表的最左端開(kāi)始，依次是L[0]，L[1]，L[2]......?？梢园蚜斜硐胂蟪梢淮错樞蚓幪?hào)的盒子在前面十進(jìn)制到二進(jìn)制數(shù)的轉(zhuǎn)換程序中，Rs=[r]+Rs這個(gè)運(yùn)算把[r]作為一個(gè)列表元素加入列表Rs的頭部。例如對(duì)于列表Rs=[1,1,1]，執(zhí)行運(yùn)算Rs=[0]+Rs后，Rs的內(nèi)容就變成了[0,1,1,1]。0122090501234567L程序示例-用遞歸把十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)

20遞歸方式的基本概念就是問(wèn)題的結(jié)果是由小問(wèn)題的結(jié)果構(gòu)建而成的。不管輸入給函數(shù)的數(shù)（叫做參數(shù)）是什么，算法都一樣。定義函數(shù)convert(x)，輸入一個(gè)十進(jìn)制整數(shù)x，輸出x對(duì)應(yīng)的二進(jìn)制整數(shù)。首先判斷這個(gè)十進(jìn)制數(shù)是否小于2，小于2可以直接返回結(jié)果。否則就用r=x%2計(jì)算此時(shí)x除以2的余數(shù)，并計(jì)算x除以2的商。然后再次調(diào)用函數(shù)convert(x)，對(duì)新的x作同樣的計(jì)算，并記錄此次的余數(shù)。#<程序2.4：整數(shù)的10-to-2進(jìn)制轉(zhuǎn)換-遞歸>defconvert(x):ifx<2:return([x])r=x%2;return(convert(x//2)+[r])num=int(input("Pleaseenteradecimalnumber:"))Rs=convert(num)foriinrange(0,len(Rs)):print(Rs[i],end=''十進(jìn)制數(shù)轉(zhuǎn)換為R進(jìn)制數(shù)

21十進(jìn)制整數(shù)x轉(zhuǎn)換為R進(jìn)制整數(shù)的算法稱(chēng)為“除R取余法”，其算法如下：輸入：十進(jìn)制整數(shù)x；輸出：x的R進(jìn)制整數(shù)。將x除以R；記錄所得余數(shù)r（其中，0≤r＜R-1）；用得到的商作為新的被除數(shù)x；重復(fù)步驟1到3，直到x為0。倒序輸出每次除法得到的余數(shù)，就是要求的R進(jìn)制數(shù)。十進(jìn)制數(shù)轉(zhuǎn)換為R進(jìn)制數(shù)

22把十進(jìn)制小數(shù)轉(zhuǎn)換為R進(jìn)制小數(shù)的方法和整數(shù)的進(jìn)制轉(zhuǎn)換方法類(lèi)似，稱(chēng)為“乘R取整法”，其算法如下：輸入：十進(jìn)制小數(shù)x；輸出：x的R進(jìn)制小數(shù)。將x除以R；R乘以x的小數(shù)部分；取乘積的整數(shù)部分作為轉(zhuǎn)換后R進(jìn)制數(shù)的小數(shù)點(diǎn)后第1位；乘積的小數(shù)部分作為新的x；重復(fù)步驟1-3，直到乘積為0，或已得到足夠精度的小數(shù)為止。輸出所得到的R進(jìn)制小數(shù)。二、八、十六進(jìn)制的巧妙轉(zhuǎn)換

2323=81，24=161

八進(jìn)制數(shù)的一位可以表示為二進(jìn)制數(shù)的三位，十六進(jìn)制數(shù)的一位可以表示為二進(jìn)制數(shù)的四位?！叭灰徊⒎ā保阂匀粸橐粋€(gè)單元?jiǎng)澐侄M(jìn)制數(shù)，每個(gè)單元可以獨(dú)立地轉(zhuǎn)換為一個(gè)八進(jìn)制數(shù)位?！八奈灰徊⒎ā保阂运奈粸橐粋€(gè)單元?jiǎng)澐侄M(jìn)制數(shù)，每個(gè)單元可以獨(dú)立地轉(zhuǎn)換為一個(gè)十六進(jìn)制數(shù)位。在轉(zhuǎn)換時(shí)要注意二進(jìn)制數(shù)的高位0位數(shù)不足時(shí)需要補(bǔ)足。

例如：11000102=0011000102=1428，注意最左邊單元的位數(shù)不足，前端補(bǔ)了2個(gè)0。小結(jié)

24R進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)時(shí)，將各位數(shù)與它的位權(quán)乘積相累加，即一個(gè)二進(jìn)制數(shù)anan-1...a1a0在十進(jìn)制中的值A(chǔ)=an×Rn+an-1×Rn-1+…+a1×R1+a0×R0。十進(jìn)制整數(shù)轉(zhuǎn)換成R進(jìn)制整數(shù)：可用十進(jìn)制整數(shù)連續(xù)地除以R，每次除法獲得的余數(shù)即為相應(yīng)R進(jìn)制數(shù)一位，最后按逆序輸出結(jié)果。此方法稱(chēng)為“除R取余法”。十進(jìn)制小數(shù)轉(zhuǎn)換成R進(jìn)制小數(shù)：可用十進(jìn)制的小數(shù)連續(xù)地乘以R，用得到的整數(shù)部分組成R進(jìn)制的小數(shù)，最后按順序輸出結(jié)果。此法稱(chēng)為“乘R取整法”。對(duì)于二進(jìn)制數(shù)和八進(jìn)制數(shù)、十六進(jìn)制數(shù)之間的轉(zhuǎn)換，有簡(jiǎn)便快速的“三位一并法”和“四位一并法”。第3節(jié)計(jì)算機(jī)中的二進(jìn)制四則運(yùn)算

25中央處理器(CPU)及其位數(shù)無(wú)符號(hào)整數(shù)與加法乘法與除法帶符號(hào)整數(shù)的減法小數(shù)—浮點(diǎn)數(shù)中央處理器及其位數(shù)

26中央處理器(CentralProcessingUnit，即CPU)是進(jìn)行各種運(yùn)算的硬件，是一個(gè)非常小的集成電路芯片，通過(guò)引腳(pin)與外部連接并交換數(shù)據(jù)。每一根引腳一次只能傳輸0或1的一個(gè)比特。引腳的數(shù)量就是CPU的位數(shù)，32位CPU就有32根數(shù)據(jù)引腳。CPU一次只能夠處理有限數(shù)位的二進(jìn)制數(shù)?，F(xiàn)在的計(jì)算機(jī)一般能一次能處理32個(gè)或64個(gè)比特的數(shù)據(jù)，計(jì)算機(jī)能直接處理的最大的二進(jìn)制整數(shù)是232或264。如何表示正整數(shù)與負(fù)整數(shù)？計(jì)算機(jī)通常把整數(shù)分為兩類(lèi)：無(wú)符號(hào)整數(shù)(unsignedinteger)，表示的是非負(fù)整數(shù)，n位計(jì)算機(jī)能表示[0,2n-1]范圍內(nèi)的所有整數(shù)；帶符號(hào)整數(shù)(signedinteger)，可以表示正整數(shù)、負(fù)整數(shù)和0，因此需要占用一個(gè)比特位來(lái)表示整數(shù)的正負(fù)符號(hào)，所能表示的正整數(shù)范圍就會(huì)變小。中央處理器及其位數(shù)

27無(wú)符號(hào)整數(shù)與加法

28對(duì)于無(wú)符號(hào)整數(shù)，n個(gè)比特所能表示的最大數(shù)是2n。用8個(gè)比特位表示的最大整數(shù)是28。8個(gè)比特能夠表示[0,255]之間的所有二進(jìn)制整數(shù)。000000002表示0，000000012表示1，111111112表示255。在二進(jìn)制加法中遵循“逢二進(jìn)位”的法則，即兩數(shù)對(duì)應(yīng)的位相加與前一位的進(jìn)位的和，大于1則產(chǎn)生進(jìn)位，把小于等于1的部分記為兩數(shù)相加后該位的值。無(wú)符號(hào)整數(shù)與加法—溢出

29溢出（overflow）：無(wú)符號(hào)整數(shù)加法的一種異常情況，即兩個(gè)整數(shù)相加的和的位數(shù)大于這兩個(gè)數(shù)的位數(shù)。例如對(duì)于只能處理8位整數(shù)的計(jì)算機(jī)而言，這個(gè)二進(jìn)制加法的和造成了溢出：從算術(shù)上看，“137+136=17”的結(jié)果顯然是錯(cuò)誤的。而在計(jì)算機(jī)中產(chǎn)生這類(lèi)錯(cuò)誤的原因是兩數(shù)相加的和超過(guò)了CPU所能處理的最大無(wú)符號(hào)整數(shù)28，即255。溢出發(fā)生時(shí)，CPU會(huì)報(bào)錯(cuò)。舍棄實(shí)際結(jié)果（錯(cuò)誤）乘法與除法

30二進(jìn)制的乘法和除法的運(yùn)算規(guī)則和十進(jìn)制的運(yùn)算規(guī)則是一樣的。二進(jìn)制乘法是由基本的二進(jìn)制加法和移位操作所完成的當(dāng)兩個(gè)二進(jìn)制數(shù)的位數(shù)之和大于或等于計(jì)算機(jī)所能處理的位數(shù)n時(shí)，乘法的結(jié)果很可能超過(guò)n位，也就是出現(xiàn)溢出。絕大部分計(jì)算機(jī)系統(tǒng)都有處理溢出的機(jī)制，這里不再作深入討論。乘法與除法

31二進(jìn)制除法是由基本的二進(jìn)制減法和移位操作完成從最高位開(kāi)始，在被除數(shù)中取和除數(shù)同樣多的位數(shù)，所得數(shù)值減去除數(shù)，直至所得的余數(shù)小于除數(shù)，這個(gè)余數(shù)和被除數(shù)中的剩余位數(shù)拼接成新的數(shù)，取其中和除數(shù)同樣多的位數(shù)，并減去除數(shù)......重復(fù)這個(gè)過(guò)程直到被除數(shù)的最后一位。帶符號(hào)數(shù)的減法

32減法其實(shí)可以看作對(duì)負(fù)數(shù)的加法

如何在計(jì)算機(jī)的世界里表示負(fù)數(shù)?在帶符號(hào)數(shù)的運(yùn)算中，計(jì)算機(jī)用1個(gè)比特表示該整數(shù)的符號(hào)，把一半的數(shù)定義為負(fù)數(shù)。十進(jìn)制數(shù)無(wú)符號(hào)整數(shù)帶符號(hào)整數(shù)對(duì)應(yīng)方式(1)帶符號(hào)整數(shù)對(duì)應(yīng)方式(2)25511111111-128-125411111110-127-2…………12810000000-1-1281270111111112712712601111110126126…………0000000000000000000000000帶符號(hào)數(shù)的減法-對(duì)應(yīng)方式(1)

33將上面的式子轉(zhuǎn)換成十進(jìn)制后，竟然出現(xiàn)了-1+1=-2的結(jié)果，同樣地：出現(xiàn)了-127+1=-128的結(jié)果。顯然采取對(duì)應(yīng)方式(1)來(lái)表示負(fù)數(shù)會(huì)造成計(jì)算錯(cuò)誤。帶符號(hào)數(shù)的減法-對(duì)應(yīng)方式(2)

34上面加法的最終結(jié)果產(chǎn)生溢出，最高位的進(jìn)位自然丟失，如果將結(jié)果轉(zhuǎn)換回十進(jìn)制數(shù)即為0，結(jié)果正確。驗(yàn)證-1+2=1的二進(jìn)制加法，結(jié)果也正確。計(jì)算機(jī)用第(2)種對(duì)應(yīng)方式表示負(fù)數(shù)，也就是所謂的補(bǔ)碼(2'scomplement)帶符號(hào)數(shù)的減法-補(bǔ)碼與真值

35使用補(bǔ)碼的情況下，在一個(gè)n位的CPU中，對(duì)于任意一個(gè)正整數(shù)x，

它的負(fù)數(shù)-x所對(duì)應(yīng)的無(wú)符號(hào)十進(jìn)制整數(shù)是2n-x。在補(bǔ)碼表示中，一個(gè)帶符號(hào)整數(shù)的二進(jìn)制數(shù)值被稱(chēng)為“真值”真值的最高位通常用來(lái)表示這個(gè)帶符號(hào)整數(shù)的符號(hào)：0表示是正數(shù)，1表示負(fù)數(shù)。十進(jìn)制數(shù)補(bǔ)碼真值255-111111111254-211111110………128-128100000001271270111111112612601111110………00000000000000000負(fù)數(shù)-x的補(bǔ)碼通過(guò)正整數(shù)x的反碼加1得到。

例如在8位的CPU中，7轉(zhuǎn)變?yōu)?7是000001112111110002，然后加1，得到-7=111110012。由-7的帶符號(hào)二進(jìn)制負(fù)數(shù)計(jì)算獲得正整數(shù)7的過(guò)程是：111110012000001102，再加1，則得到000001112=7。反碼（1‘scomplement）按位取反，原來(lái)是0的位變?yōu)?，原來(lái)是1的位變?yōu)?帶符號(hào)數(shù)的減法-補(bǔ)碼與反碼

360110按位取反按位取反按位取反帶符號(hào)數(shù)的減法-補(bǔ)碼

37

回顧：

用負(fù)數(shù)的加法表示帶符號(hào)整數(shù)的減法用補(bǔ)碼表示帶符號(hào)整數(shù)，包括負(fù)整數(shù)、正整數(shù)和0一個(gè)帶符號(hào)整數(shù)的二進(jìn)制數(shù)值被稱(chēng)為“真值”一個(gè)二進(jìn)制數(shù)值的反碼就是對(duì)它“按位取反”十進(jìn)制整數(shù)-x的補(bǔ)碼=十進(jìn)制整數(shù)x的真值的反碼+1問(wèn)題：

補(bǔ)碼表示的帶符號(hào)數(shù)如何做加法？是否存在異常情況，例如溢出？

帶符號(hào)數(shù)的減法-補(bǔ)碼的加法

38

在用補(bǔ)碼方式表示n位帶符號(hào)整數(shù)時(shí)，最大數(shù)是2n-1-1，最小數(shù)是-2n-1由于在計(jì)算機(jī)中存在位數(shù)的限制，整數(shù)溢出的問(wèn)題是不可避免的。例1：

因?yàn)?20+30=150>127，超過(guò)了8位補(bǔ)碼能夠表示的最大值，導(dǎo)致溢出。例2：由于最高位（第8位）的進(jìn)位丟失，使得(-120)+(-30)的結(jié)果竟然成為正數(shù)106。超出了8位補(bǔ)碼能夠表示的最小值，因而導(dǎo)致溢出。帶符號(hào)數(shù)的減法-補(bǔ)碼的加法

39

在使用n位補(bǔ)碼的計(jì)算機(jī)中，帶符號(hào)數(shù)的加法會(huì)產(chǎn)生以下3種情況：正溢出(Positiveoverflow)：兩個(gè)正數(shù)x和y相加，如果結(jié)果的最高位是1，就代表溢出。例如120+30=011110002+000111102=100101102，第八位為1，說(shuō)明出現(xiàn)正溢出。不產(chǎn)生溢出。即一正一負(fù)相加的情況。負(fù)溢出(Negativeoverflow)：兩個(gè)負(fù)數(shù)相加，最高位（第n位）為0則代表溢出。例如，(-120)+(-30)=100010002+111000102=1011010102，第8位為0，說(shuō)明出現(xiàn)負(fù)溢出。小數(shù)—浮點(diǎn)數(shù)

40在計(jì)算機(jī)中整數(shù)以外的其他數(shù)（帶小數(shù)的數(shù)）被稱(chēng)為浮點(diǎn)數(shù)(Floatingnumber)浮點(diǎn)運(yùn)算的規(guī)則和整數(shù)的運(yùn)算規(guī)則相同計(jì)算機(jī)使用類(lèi)似科學(xué)記數(shù)的方法表示浮點(diǎn)數(shù)，包括指數(shù)e和尾數(shù)m以及帶符號(hào)數(shù)的符號(hào)位s二進(jìn)制浮點(diǎn)數(shù)1.011×2010在計(jì)算機(jī)中存為：現(xiàn)代計(jì)算機(jī)常用單精度浮點(diǎn)數(shù)（32位）和雙精度（64位）浮點(diǎn)數(shù)。浮點(diǎn)運(yùn)算比整數(shù)運(yùn)算更為復(fù)雜，世界上的超級(jí)電腦都是按照浮點(diǎn)運(yùn)算性能排名的。小數(shù)—浮點(diǎn)數(shù)

41大家在做浮點(diǎn)數(shù)運(yùn)算時(shí)，有時(shí)會(huì)遇到精度丟失的問(wèn)題，即結(jié)果與預(yù)期有偏差。為什么會(huì)出現(xiàn)這種狀況？

真正的原因要從計(jì)算機(jī)保存浮點(diǎn)數(shù)的原理說(shuō)起。計(jì)算機(jī)是以二進(jìn)制的方式存儲(chǔ)數(shù)字的。在前面的學(xué)習(xí)中，我們學(xué)會(huì)了如何將十進(jìn)制小數(shù)轉(zhuǎn)換為二進(jìn)制。但是在使用中我們會(huì)發(fā)現(xiàn)，有些十進(jìn)制的小數(shù)我們無(wú)法用二進(jìn)制小數(shù)準(zhǔn)確表示。比如十進(jìn)制小數(shù)0.6，如果我們不限制位數(shù)，小數(shù)點(diǎn)后的位數(shù)將會(huì)是無(wú)窮的。所以我們只能通過(guò)不斷增加二進(jìn)制的長(zhǎng)度來(lái)提高精確度。工業(yè)界為了有統(tǒng)一的標(biāo)準(zhǔn)，這就出現(xiàn)了IEEE二進(jìn)制浮點(diǎn)數(shù)算術(shù)標(biāo)準(zhǔn)（IEEE754）。在此標(biāo)準(zhǔn)下，一個(gè)浮點(diǎn)數(shù)最多是用64位來(lái)存放，所以會(huì)有精確度的損失。小數(shù)—浮點(diǎn)數(shù)

42根據(jù)IEEE754的規(guī)定，每個(gè)二進(jìn)制浮點(diǎn)數(shù)都有以下幾個(gè)部分組成：符號(hào)位s，指數(shù)e和尾數(shù)m。一個(gè)浮點(diǎn)數(shù)a表示為±m(xù)×2e，其中，符號(hào)位s=0如果a為正數(shù)，否則是1。尾數(shù)m是表示形如1.ddd...ddd的數(shù)（每一位d是0或1），我們不需要存儲(chǔ)m最前面的1（小數(shù)點(diǎn)前一定是1）和小數(shù)點(diǎn)，所以尾數(shù)m部分只存儲(chǔ)小數(shù)點(diǎn)后的那些d值，而精準(zhǔn)度則是取決于能存儲(chǔ)多少位d值。注意，指數(shù)e可以為正也可以為負(fù)數(shù)，IEEE754不用補(bǔ)碼方式，它用其特殊方式來(lái)表示正負(fù)指數(shù)值。以1.0112×22為例，這是個(gè)正數(shù)，所以符號(hào)位s是0，尾數(shù)m存儲(chǔ)011部分，指數(shù)e則是2。小數(shù)—浮點(diǎn)數(shù)

43現(xiàn)代計(jì)算機(jī)中通常用32位或64位存放浮點(diǎn)數(shù)，分別叫作單精度和雙精度浮點(diǎn)數(shù)。IEEE754的單精度浮點(diǎn)數(shù)共32位，其中23位表示尾數(shù)，8位表示指數(shù)，1位表示符號(hào)數(shù)。這里要特別說(shuō)明一下，IEEE754中規(guī)定，指數(shù)部分的正負(fù)是通過(guò)中間數(shù)的偏移來(lái)表示的。單精度浮點(diǎn)數(shù)的指數(shù)部分是由8位組成，那么它的中間數(shù)的真值是127（01111111），也就是真值127代表指數(shù)0，真值126(01111110)代表指數(shù)-1，真值128(10000000)代表指數(shù)1，真值129(10000001)代表指數(shù)2，以此類(lèi)推。例如二進(jìn)制浮點(diǎn)數(shù)1.011×22以單精度的形式在計(jì)算機(jī)中的存儲(chǔ)如下圖所示。小數(shù)—浮點(diǎn)數(shù)

44注意，二進(jìn)制浮點(diǎn)數(shù)整數(shù)部分的1是默認(rèn)不存儲(chǔ)的，而是只存放尾數(shù)的小數(shù)部分。如果小數(shù)部分不足23位，則在不足的位補(bǔ)0。因?yàn)?01.1是正數(shù)，所以符號(hào)位是0，101.1的指數(shù)部分是2，表示為01111111+2，即10000001。最后的尾數(shù)部分填入小數(shù)部分011，不足23位的地方補(bǔ)0即可。如果指數(shù)是負(fù)數(shù)時(shí)，例如二進(jìn)制浮點(diǎn)數(shù)1.011×2-2，同樣是單精度浮點(diǎn)數(shù)時(shí)，它的指數(shù)部分就可以表示為01111111-2，即01111101。IEEE754同樣也為雙精度浮點(diǎn)數(shù)制定了標(biāo)準(zhǔn)，雙精度浮點(diǎn)數(shù)共64位。和單精度浮點(diǎn)數(shù)一樣，由符號(hào)位，指數(shù)和尾數(shù)三部分組成。不同的是尾數(shù)部分由52位組成，指數(shù)e變成了11位，相應(yīng)的中間數(shù)也變?yōu)榱?1111111111。本書(shū)介紹了浮點(diǎn)數(shù)的基本表示法，有些IEEE754特殊數(shù)的表示法則不作介紹。浮點(diǎn)數(shù)的運(yùn)算也有其特別之處，這部分內(nèi)容將在計(jì)算機(jī)系統(tǒng)的相關(guān)課程中討論，本書(shū)不深入講解。顯然，浮點(diǎn)運(yùn)算比整數(shù)運(yùn)算更為復(fù)雜。一般較好的計(jì)算機(jī)都有專(zhuān)門(mén)的浮點(diǎn)運(yùn)算單元。浮點(diǎn)運(yùn)算通常是對(duì)計(jì)算機(jī)性能的一大考驗(yàn)。世界上的超級(jí)計(jì)算機(jī)都是按照浮點(diǎn)運(yùn)算性能排名的。小數(shù)—浮點(diǎn)數(shù)

45為什么IEEE754的指數(shù)部分不采用補(bǔ)碼，而用中間數(shù)的偏移來(lái)表示正負(fù)？這是為了方便兩個(gè)指數(shù)做大小比較和計(jì)算兩指數(shù)的差距。以二個(gè)浮點(diǎn)數(shù)做加法或比較大小為例，首先要比較指數(shù)大小，更正指數(shù)值使得二個(gè)小數(shù)點(diǎn)對(duì)齊，用IEEE754的指數(shù)存放法，二指數(shù)的差距可以簡(jiǎn)單地用他們的真值算出來(lái)，例如，兩個(gè)浮點(diǎn)數(shù)的指數(shù)為3和-1，那么IEEE754會(huì)分別存放真值127+3=130和127-1=126。從真值中就可以辨別130大于126，并且他們的差距是130–126=4。這使得浮點(diǎn)運(yùn)算的硬件比較容易實(shí)現(xiàn)。小結(jié)

46無(wú)符號(hào)整數(shù)只能表示非負(fù)整數(shù)，帶符號(hào)整數(shù)可以表示正整數(shù)、零和負(fù)整數(shù)帶符號(hào)整數(shù)的補(bǔ)碼編碼方法（真值、反碼）對(duì)于n位計(jì)算機(jī)，無(wú)符號(hào)整數(shù)能表示的最大值是2n-1，最小值是0；而帶符號(hào)整數(shù)的補(bǔ)碼所能表示的最大值是2n-1-1，最小值是-2n-1。四則運(yùn)算都可以用加法完成。一切都是加法。在計(jì)算機(jī)中，我們只需要一種實(shí)現(xiàn)加法的硬件就能完成所有的四則運(yùn)算。在無(wú)符號(hào)整數(shù)的加法中，只可能產(chǎn)生一種溢出，可以通過(guò)結(jié)果s與加數(shù)x的關(guān)系判斷是否溢出。在帶符號(hào)整數(shù)的加法中，可能出現(xiàn)正溢出和負(fù)溢出兩種情況，正溢出是指兩個(gè)正整數(shù)相加的和成為負(fù)數(shù)，負(fù)溢出是指兩個(gè)負(fù)整數(shù)相加的和成為正數(shù)。計(jì)算機(jī)通常把浮點(diǎn)數(shù)分為符號(hào)位、指數(shù)、尾數(shù)3個(gè)部分存放第4節(jié)一切都是邏輯（Logic）

47什么是邏輯運(yùn)算電路實(shí)現(xiàn)邏輯用邏輯做加法加法與控制語(yǔ)句什么是邏輯運(yùn)算

48在計(jì)算機(jī)中沒(méi)有真正做加法運(yùn)算的電路，因?yàn)殡娮釉荒堋坝?jì)算”結(jié)果計(jì)算機(jī)里面的電子元件就像是一道道閘門(mén)，門(mén)的“開(kāi)”與“關(guān)”對(duì)應(yīng)邏輯的“0”與“1”兩種狀態(tài)，決定了電路的導(dǎo)通或斷開(kāi)基本運(yùn)算是由0與1的邏輯運(yùn)算衍生而來(lái)，這也就是計(jì)算機(jī)的電子電路能夠?qū)崿F(xiàn)二進(jìn)制計(jì)算的原因什么是邏輯運(yùn)算-邏輯變量與運(yùn)算符

49邏輯運(yùn)算是對(duì)邏輯變量和邏輯運(yùn)算符號(hào)的組合序列所作的邏輯推理。邏輯運(yùn)算的變量只有兩個(gè)，它們代表兩種對(duì)立的邏輯狀態(tài)。真—假、是—否、有—無(wú)

1—0邏輯運(yùn)算的基本運(yùn)算：與（AND）：代表邏輯運(yùn)算的乘法，運(yùn)算符號(hào)是“∧”或（OR）：代表邏輯運(yùn)算的加法，運(yùn)算符號(hào)是“∨”非（NOT）：代表邏輯上的否定，運(yùn)算符號(hào)是“﹁”“與”和“或”都操作兩個(gè)邏輯變量，而“非”只操作一個(gè)邏輯變量邏輯變量A的“非”是在A上面加一短橫表示，即?。钭鳌癆bar”）邏輯運(yùn)算的結(jié)果也只能是0或1，代表邏輯推理上的“真”或“假”。什么是邏輯運(yùn)算-真值表

50為了運(yùn)算方便，把邏輯變量和邏輯運(yùn)算的結(jié)果列在一張表里這張表稱(chēng)為真值表（Truthtable）ABāANDOR00100011011000111011A為1并且B為1時(shí)，AANDB的運(yùn)算結(jié)果才為1A或B中的任何一個(gè)為1，AORB的結(jié)果即為1A和B都為0時(shí)，AORB的運(yùn)算結(jié)果才為0A或B中的任何一個(gè)為0，AANDB的結(jié)果即為0什么是邏輯運(yùn)算-運(yùn)算優(yōu)先級(jí)

51

在邏輯運(yùn)算中，“非”運(yùn)算的優(yōu)先級(jí)最高，“與”、“或”運(yùn)算的優(yōu)先級(jí)相同。例如計(jì)算邏輯式﹁A∨B時(shí)，首先計(jì)算﹁A，然后再進(jìn)行“或”運(yùn)算，相當(dāng)于計(jì)算(﹁A)∨B。而不是先算A∨B，再做非運(yùn)算。邏輯式(﹁A)∨B和邏輯式﹁(A∨B)的含義完全不同。如果用自然語(yǔ)言表述，我們把前一個(gè)式子念作“非A和B的或”，把后一個(gè)式子念作“A或B的非”。有了基本邏輯運(yùn)算的真值表和運(yùn)算規(guī)則，就可以正確地完成邏輯運(yùn)算。電路實(shí)現(xiàn)邏輯

52計(jì)算機(jī)電路中用晶體管實(shí)現(xiàn)邏輯。晶體管是以半導(dǎo)體材料為基礎(chǔ)的元件，例如各種半導(dǎo)體材料制成的二極管、三極管、場(chǎng)效應(yīng)管、可控硅等?，F(xiàn)在計(jì)算機(jī)芯片制造者已經(jīng)可以用大規(guī)模生產(chǎn)的方式在幾個(gè)平方毫米的半導(dǎo)體晶片上實(shí)現(xiàn)數(shù)百萬(wàn)個(gè)晶體管。晶體管發(fā)明者JohnBardeen,WilliamShockley,WalterBrattain幾種不同封裝大小的晶體管電路實(shí)現(xiàn)邏輯-晶體管

53我們可以通過(guò)控制晶體管的電源來(lái)控制它們開(kāi)或關(guān)的狀態(tài)

圖示為一個(gè)三極管稱(chēng)為三極管是因?yàn)樗蠨、S和G三個(gè)引腳D端代表高電壓，通常都是5VG端代表輸入信號(hào)。晶體管就像一個(gè)開(kāi)關(guān)一樣：當(dāng)G輸入是高電壓的時(shí)候，代表輸入邏輯G=1，晶體管導(dǎo)通；當(dāng)G輸入是低電壓的時(shí)候，代表輸入邏輯G=0，晶體管就不通。S端接地，也就是0V電路實(shí)現(xiàn)邏輯-非門(mén)

54輸入電壓經(jīng)過(guò)“非門(mén)”后，輸出的結(jié)果正好與輸入相反。比如輸入電壓1，圖里的晶體管導(dǎo)通，輸出電壓的線路就接地了，只好輸出0；而輸入電壓0，圖里的晶體管斷開(kāi)，輸出電壓的線路就變成了高電壓，只好輸出1。電路實(shí)現(xiàn)邏輯-與門(mén)

55把兩個(gè)晶體管的輸入電壓A和B串聯(lián)起來(lái)可以實(shí)現(xiàn)與門(mén)。只有輸入電壓A和B同時(shí)為1時(shí)，這條電路才會(huì)導(dǎo)通，最后經(jīng)過(guò)非門(mén)得到的輸出結(jié)果是1。非門(mén)的電路表示符號(hào)是圖中帶小圓點(diǎn)的三角形。電路實(shí)現(xiàn)邏輯-或門(mén)

56把兩個(gè)晶體管的輸入電壓A和B并聯(lián)起來(lái)可以實(shí)現(xiàn)或門(mén)。只有當(dāng)輸入電壓A和B同時(shí)為0時(shí)，這條電路才會(huì)成為斷開(kāi)的狀態(tài)，最后經(jīng)過(guò)非門(mén)得到的輸出電壓是0；在A或B中的任意個(gè)電極輸入電壓1，這條路都會(huì)導(dǎo)通，最終經(jīng)過(guò)非門(mén)的輸出結(jié)果也就會(huì)變成1。用邏輯做加法

57二進(jìn)制數(shù)的加法在計(jì)算機(jī)里是由每一個(gè)比特位的加法組成的而每一位的的加法都需要3個(gè)輸入，并產(chǎn)生2個(gè)輸出3個(gè)輸入分別是兩個(gè)相加位和一個(gè)由相鄰低位產(chǎn)生的進(jìn)位2個(gè)輸出分別是一個(gè)相加得到的二進(jìn)制數(shù)位和一個(gè)進(jìn)位半加器(Halfadder)

：兩個(gè)輸入，沒(méi)有進(jìn)位C作為輸入全加器(Fulladder)

：三個(gè)輸入用邏輯做加法-半加器

58半加器的輸入是兩個(gè)1位的二進(jìn)制數(shù)A和B，它們的值是0或1；經(jīng)過(guò)加法器的運(yùn)算之后，給出兩個(gè)1位的輸出，一個(gè)是加法所產(chǎn)生的低位，稱(chēng)為“和”（sum）；另一個(gè)是加法所產(chǎn)生的進(jìn)位（carry）。A=0，B=0，Sum=0，Carry=0，即和為0且沒(méi)有進(jìn)位；A=0，B=1，Sum=1，Carry=0，即和為1且沒(méi)有進(jìn)位；A=1，B=0，Sum=1，Carry=0，即和為1且沒(méi)有進(jìn)位；A=1，B=1，Sum=0，Carry=1，即和為0且進(jìn)位為1；用邏輯做加法-半加器

59A=0，B=0，Sum=0，Carry=0A=0，B=1，Sum=1，Carry=0A=1，B=0，Sum=1，Carry=0A=1，B=1，Sum=0，Carry=1ABSumCarry0000011010101101半加器的真值表用邏輯做加法-半加器

60觀察真值表發(fā)現(xiàn)：Carry：只有當(dāng)輸入A和B同時(shí)為1時(shí)，Carry的值才可能為1

Carry=A∧BSum：Sum為1的情況在真值表里出現(xiàn)了兩次1）A為0且B為1時(shí)，Sum為1，這個(gè)邏輯關(guān)系可以表示為A∧﹁B=1；2）A為1,且B為0時(shí)，Sum為1，這個(gè)邏輯關(guān)系可以表示為﹁A∧B=1。這兩種情況中只要有一種情況成立，Sum即為1。

Sum=(A∧﹁B)∨(﹁A∧B)。ABSumCarry0000011010101101半加器的真值表：用邏輯做加法-半加器

61為了方便起見(jiàn)，我們常在寫(xiě)邏輯算式時(shí)省略邏輯與的符號(hào)，并且用“+”和“bar”代替邏輯或和相應(yīng)變量的非運(yùn)算。例如：Carry=A∧B，Sum=(A∧﹁B)∨(﹁A∧B)改寫(xiě)為Carry=AB，Sum=。我們可以根據(jù)這種邏輯運(yùn)算的符號(hào)畫(huà)出圖示的電路設(shè)計(jì)圖：用邏輯做加法-全加器

62實(shí)現(xiàn)多位加法需要全加器，只要在半加器的基礎(chǔ)上做一個(gè)小小改進(jìn)，就可以得到全加器。半加器的沒(méi)有進(jìn)位輸入，而全加器需要輸入低位的進(jìn)位，全加器如下圖所示：3個(gè)輸入：A和B是兩個(gè)加數(shù)，Ci是從下一位獲得的進(jìn)位。兩個(gè)輸出：給上一位的進(jìn)位Co，以及兩數(shù)相加的和在該位的值Sum。用邏輯做加法-全加器

63全加器的真值表：ABCiSumCo0000000110010100110110010101011100111111觀察真值表發(fā)現(xiàn)：Carry：只要A、B、Ci中有任意兩個(gè)輸入的值是1，不管余下的一個(gè)輸入值是多少，Co一定會(huì)是1。

Co=AB+ACi+BCi

Sum：有4種情況會(huì)使得Sum的取值為1，這四種情況中只要有一種情況成立，Sum即為1。

Sum=ABCi+ABCi+ABCi+ABCi。程序示例-全加器

64程序直接使用Python中的邏輯運(yùn)算符表達(dá)了全加器的邏輯算式。程序的三個(gè)輸入是加數(shù)a、被加數(shù)b，和進(jìn)位c；兩個(gè)輸出分別是Sum和向左鄰位的進(jìn)位Carry。程序中的“and”是邏輯與的運(yùn)算符，“or”是邏輯或的運(yùn)算符，“not”是邏輯非的運(yùn)算符。反斜杠“\”表示一個(gè)長(zhǎng)語(yǔ)句在下一行的繼續(xù)，這是Python語(yǔ)言為了便于大家使用而提供的一個(gè)語(yǔ)句連接符號(hào)。#<程序:全加器>defFA(a,b,c):#FulladderCarry=(aandb)or(bandc) or(aandc)Sum=(aandbandc)or(aand (notb)and(notc))\ or((nota)andband(notc))\ or((nota)and(notb)andc)returnCarry,Sum用邏輯做加法-漣波進(jìn)位加法器

65漣波進(jìn)位加法器(Ripple-carryadder)：把多個(gè)1位全加器串聯(lián)起來(lái)，組成一個(gè)多位的加法器。串聯(lián)方式中，每個(gè)全加器計(jì)算一位加法，只需要簡(jiǎn)單地將一個(gè)全加器輸出的進(jìn)位連接到與其左鄰的全加器的輸入進(jìn)位。如果要計(jì)算第i位的值，必須先計(jì)算出第0到i-1位的所有加法。最右端的全加器執(zhí)行最低位的加法，它進(jìn)位輸入C0通常置為常量0。也可以直接用一個(gè)半加器執(zhí)行最低位的加法。程序示例-程序：完整的加法器

66兩個(gè)輸入x和y，分別代表被加數(shù)和加數(shù)；有兩個(gè)輸出，分別是進(jìn)位Carry和存放加法結(jié)果的列表L。兩個(gè)while循環(huán)在位數(shù)較少的數(shù)前面補(bǔ)0，直到兩個(gè)數(shù)的位數(shù)相同。for循環(huán)從二進(jìn)制數(shù)的最低位開(kāi)始，調(diào)用全加器函數(shù)FA(x[i],y[i],Carry)對(duì)輸入的每一位依次做加法。用Python實(shí)現(xiàn)的加法器利用了Python語(yǔ)言所定義的列表的性質(zhì)，沒(méi)有位數(shù)限制。如果換成用硬件電路設(shè)計(jì)的加法器，就會(huì)受到各種硬件資源的制約。1.#<程序：完整的加法器CarryRippleadder>2.defadd(x,y):3.whilelen(x)<len(y):x=[False]+x4.whilelen(y)<len(x):y=[False]+y5.L=[];Carry=False6.foriinrange(len(x)-1,-1,-1):7.Carry,Sum=FA(x[i],y[i],Carry)8.L=L+[Sum]9.return(Carry,L)用邏輯做加法-乘法器

67前面說(shuō)過(guò)，乘法可以用加法和移位操作實(shí)現(xiàn)，那么請(qǐng)看使用漣波進(jìn)位加法器組成的乘法器：程序示例-程序：乘法器

68兩個(gè)輸入x和y，分別代表被加數(shù)和程序for循環(huán)所產(chǎn)生的乘法過(guò)程的部分和存放在列表S中。在每一次循環(huán)中，判斷y的當(dāng)前位是否為1，為1就在當(dāng)前結(jié)果S上加被乘數(shù)x，即“C,S=add(S,x)”。如果S和x的加法產(chǎn)生進(jìn)位，就將其加入列表S，即“ifC==True:S=[C]+S”。每完成一位乘法，加法器就需要把被乘數(shù)x向左移1位。這個(gè)程序把左移被加數(shù)x的方法在x的后面增加一個(gè)元素False，即“x=x+[False]”。。1.#<程序：乘法器>2.defmultiplier(x,y):#求x*y3.S=[];4.foriinrange(len(y)-1,-1,-1):5.ify[i]==True6.C,S=add(S,x)#加法7.ifC==True:S=[C]+S8.x=x+[False] #移位9.return(S)加法與控制語(yǔ)句

69對(duì)于計(jì)算機(jī)而言，所有的控制語(yǔ)句對(duì)控制條件的判斷都可以轉(zhuǎn)變成加法，即變成加法器上的最基本的操作。ifbin[i]==str(1):weight=2**(len(bin)-i-1)dec=dec+weight;可以讓上面程序里的if語(yǔ)句判斷條件變成是計(jì)算機(jī)可以執(zhí)行的減法運(yùn)算：bin[i]-str(1)如果它結(jié)果為0，則if語(yǔ)句的判斷條件成立，因此可以接著執(zhí)行后續(xù)語(yǔ)句；否則，如果判斷條件不成立，程序?qū)⒅苯犹D(zhuǎn)到print(dec)語(yǔ)句。用加法電路可以實(shí)現(xiàn)所有的運(yùn)算，包括減法運(yùn)算，所以可以用加法電路實(shí)現(xiàn)程序的控制語(yǔ)句。小結(jié)

70我們體認(rèn)到計(jì)算機(jī)世界里的0與1不僅僅組成了二進(jìn)制數(shù)，而且和邏輯中的“真”與“假”建立了對(duì)應(yīng)關(guān)系。這種對(duì)應(yīng)關(guān)系讓計(jì)算機(jī)有能力通過(guò)邏輯運(yùn)算實(shí)現(xiàn)最基本的加法運(yùn)算，進(jìn)而實(shí)現(xiàn)所有的數(shù)值運(yùn)算，以及控制語(yǔ)句的判斷條件。構(gòu)成計(jì)算機(jī)的電子電路所能做“計(jì)算”其實(shí)都是邏輯運(yùn)算。0與1把其他所有進(jìn)制的數(shù)轉(zhuǎn)換為計(jì)算機(jī)中的電子電路所能表達(dá)和運(yùn)算的二進(jìn)制數(shù)。也為我們打通了數(shù)值計(jì)算和邏輯運(yùn)算之間的界限，使我們看到二者通融的本質(zhì)。在計(jì)算機(jī)中，一切都是邏輯，一切都?xì)w功于神奇的0與1！第5節(jié)計(jì)算機(jī)中的存儲(chǔ)

71數(shù)據(jù)的存儲(chǔ)形式存儲(chǔ)設(shè)備數(shù)據(jù)的存儲(chǔ)形式

72計(jì)算機(jī)用二進(jìn)制數(shù)的組合來(lái)表達(dá)所有需要保持的信息，這些二進(jìn)制數(shù)的組合按照一定的規(guī)則存放就形成了計(jì)算機(jī)里的數(shù)據(jù)。二進(jìn)制數(shù)的數(shù)值0或1的存儲(chǔ)方式跟隨著物理介質(zhì)的特性不同而不同，基本是利用物理材料的電信號(hào)、磁信號(hào)之類(lèi)的狀態(tài)來(lái)存儲(chǔ)0或1。這些載體就稱(chēng)為存儲(chǔ)介質(zhì)。存儲(chǔ)介質(zhì)和輔助數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)讀寫(xiě)的電路、設(shè)備等組合在一起，構(gòu)成了存儲(chǔ)設(shè)備，例如我們常用的內(nèi)存、磁盤(pán)、U盤(pán)等。數(shù)據(jù)的存儲(chǔ)形式

73在計(jì)算機(jī)內(nèi)部，各種信息都是以二進(jìn)制編碼的形式存儲(chǔ)的。在二進(jìn)制編碼中，指定不同數(shù)量的0或1形成的不同的組合表示不同的意義。編碼往往用到一大串0或1，必須要按照一定規(guī)則對(duì)這些信息進(jìn)行分割和識(shí)別才能獲得有用的信息。計(jì)算機(jī)普通把單位信息分成以下三種：位(或稱(chēng)為“比特”，bit)：一個(gè)1或一個(gè)0即一個(gè)位。字節(jié)(Byte)：一個(gè)字節(jié)由8位二進(jìn)制數(shù)組成（1Byte=8bit）。字(Word)：字是字節(jié)的組合，CPU可以用“字”為單位來(lái)讀寫(xiě)數(shù)據(jù)。大部分CPU的字長(zhǎng)是32位（4個(gè)字節(jié)）或64位（8個(gè)字節(jié)）。數(shù)據(jù)的存儲(chǔ)形式

74字節(jié)是信息存儲(chǔ)中常用的基本單位。計(jì)算機(jī)的存儲(chǔ)器（包括內(nèi)存與外存）通常也是以多少字節(jié)來(lái)表示它的容量。常用的單位有：KB(Kilobyte)：K代表210

，1KB=210B=1024B；MB(Megabyte)：M代表220，1MB=1024KB；GB(Gigabyte)：G代表230

，1GB=1024MB；TB(Terabyte)：T代表240

，1TB=1024GB；PB(Petabyte)：P代表250

，1PB=1024TB；EB(Exabyte)

：E代表260

，1EB=1024PB。這些符號(hào)在不同場(chǎng)合有不統(tǒng)一的定義。通常在談容量時(shí)用的是二進(jìn)制的一套定義方法；在談?wù)撚?jì)算機(jī)性能時(shí)常用的是單位制；而談速度的時(shí)用的是十進(jìn)制的一套定義。例如網(wǎng)絡(luò)傳輸就是用的十進(jìn)制。數(shù)據(jù)的存儲(chǔ)形式—符號(hào)的編碼方式

75ASCII碼：

美國(guó)信息交換標(biāo)準(zhǔn)碼，AmericanStandardCodeforInformationInterchange10個(gè)數(shù)、大小寫(xiě)英文字母和專(zhuān)用字符等95種可打印字符和33個(gè)控制字符使用1個(gè)字節(jié)中的7位二進(jìn)制數(shù)來(lái)表示一個(gè)字符，最多可表示128個(gè)字符Python函數(shù)ord()和chr()分別在字符和對(duì)應(yīng)的ASCII碼數(shù)值之間進(jìn)行轉(zhuǎn)換GBK字符集：即國(guó)家標(biāo)準(zhǔn)擴(kuò)展字符集，指明了計(jì)算機(jī)中如何表示漢字。目前的GBK中用兩個(gè)字節(jié)代表一個(gè)漢字，所以GBK字符集最多表示216=65536個(gè)漢字，目前表示了21886個(gè)漢字。統(tǒng)一字符編碼Unicode：國(guó)際上普遍適用的統(tǒng)一字符編碼UnicodeUnicode只有一個(gè)字符集，字符有兩個(gè)字節(jié)的確定編碼，即UCS-2Unicode對(duì)于不同的計(jì)算機(jī)系統(tǒng)平臺(tái)有不同的實(shí)現(xiàn)方式，即常說(shuō)的Unicode轉(zhuǎn)換格式（UnicodeTransformationFormat，簡(jiǎn)稱(chēng)為UTF），例如UTF-8、UTF-16LE等數(shù)據(jù)的存儲(chǔ)形式

76在計(jì)算機(jī)內(nèi)部，漢字編碼和字符編碼是共存的，而對(duì)不同的信息有不同的處理方式，那我們應(yīng)該如何區(qū)分它們呢？方法之一就是ASCII碼所用字節(jié)最高位置為“0”，而對(duì)于雙字節(jié)的國(guó)標(biāo)碼，將兩個(gè)字節(jié)的最高位都置成“1”，然后由軟件（或硬件）根據(jù)字節(jié)最高位來(lái)判斷。計(jì)算機(jī)里用二進(jìn)制編碼的形式存儲(chǔ)各種信息，僅僅用0和1就可以表示世間所有的數(shù)、數(shù)學(xué)符號(hào)、漢字、英文、拉丁文和其他各種語(yǔ)言文字。然而，這些組織方式和編碼都是邏輯上的概念，都是形式上的組織方式，與真實(shí)計(jì)算機(jī)里存放數(shù)據(jù)的寄存器、緩存、內(nèi)存和磁盤(pán)等等看上去毫無(wú)關(guān)聯(lián)！所以接下來(lái)就要講解計(jì)算機(jī)是用物理設(shè)備表達(dá)與存儲(chǔ)0與1的相關(guān)內(nèi)容。存儲(chǔ)設(shè)備—存儲(chǔ)層次

77存儲(chǔ)設(shè)備：存放0和1組成的二進(jìn)制信息的物理載體稱(chēng)為存儲(chǔ)介質(zhì)，存儲(chǔ)介質(zhì)加上配套電路等組件就組成了存儲(chǔ)設(shè)備?，F(xiàn)在計(jì)算機(jī)里常用的存儲(chǔ)設(shè)備以下幾類(lèi)：寄存器(Register)高速緩存(Cache)內(nèi)存(Mainmemory)外存(Storage)圖示是目前計(jì)算機(jī)系統(tǒng)最基礎(chǔ)的存儲(chǔ)層次：速度越快價(jià)格越高容量越小，離CPU越近；速度越慢價(jià)格越低容量越大，離CPU越遠(yuǎn)。存儲(chǔ)設(shè)備—寄存器

78寄存器(Register)：處于CPU內(nèi)部，和算術(shù)邏輯單元(ArithmeticLogicUnit,ALU)直接相連寄存器讀寫(xiě)數(shù)據(jù)的速度（訪問(wèn)速度）是數(shù)百皮秒（1皮秒=10-12秒），非常接近ALU的計(jì)算速度。因?yàn)楹馨嘿F，所以寄存器的容量極小，通常只有數(shù)百個(gè)字節(jié)的大小。普通運(yùn)算時(shí)需要將數(shù)據(jù)先放到CPU中的寄存器里，然后ALU對(duì)寄存器的值做計(jì)算，再存回寄存器里。存儲(chǔ)設(shè)備—高速緩存

79高速緩存(Cache)：通常是由靜態(tài)隨機(jī)存儲(chǔ)器（StaticRandomAccessMemory，SRAM）制成，它是一種較快速的存儲(chǔ)介質(zhì)，而且不需要刷新電路即能保存它內(nèi)部存儲(chǔ)的數(shù)據(jù)。速度比寄存器慢，容量比寄存器大，比寄存器要便宜些。實(shí)際計(jì)算機(jī)里的Cache可以分作1到3級(jí)，通常1級(jí)Cache的訪問(wèn)速度是1~2納秒（ns），容量是64KB。其后兩級(jí)的速度在5~20ns之間，容量在256KB~4MB之間。存儲(chǔ)設(shè)備—內(nèi)存

80內(nèi)存：又叫主存，內(nèi)存通常由動(dòng)態(tài)隨機(jī)訪問(wèn)存儲(chǔ)器（DynamicRandomAccessMemory,DRAM）制成它比SRAM要便宜許多，容量也要大得多。內(nèi)存的速度在50~100ns之間，現(xiàn)在常用的內(nèi)存容量都在幾百M(fèi)B到數(shù)GB之間。有的高端計(jì)算機(jī)或者其他特殊用途的地方（例如大型數(shù)據(jù)庫(kù)）的內(nèi)存甚至?xí)玫綌?shù)十GB到數(shù)TB的DRAM。程序普通執(zhí)行時(shí)的信息，包括程序指令和很多用到的數(shù)據(jù)都存放在內(nèi)存中。存儲(chǔ)設(shè)備—外存

81外存：外存一般指比內(nèi)存速度更慢容量更大的存儲(chǔ)器外存的一個(gè)顯著特征是數(shù)據(jù)斷電后不丟失，而當(dāng)前以上三種存儲(chǔ)在斷電后都會(huì)丟失數(shù)據(jù)。通常就是我們所說(shuō)的硬盤(pán)?，F(xiàn)在常用的外存有磁盤(pán)（Mageneticdisk）和固態(tài)硬盤(pán)（也叫SSD），比DRAM要便宜許多。外存的訪問(wèn)速度可能是微秒級(jí)（比如Flashmemory）、毫秒級(jí)（磁盤(pán)），容量一般都是GB或TB級(jí)別。存儲(chǔ)設(shè)備—緩存的概念

82有2個(gè)單位叫做A和B（A可想成是CPU，B可想成是存儲(chǔ)單元或另一臺(tái)電腦等），A和B有段距離，而A要對(duì)存在B的數(shù)據(jù)塊X做1000次左右的計(jì)算。從A到B讀取數(shù)據(jù)要花1秒時(shí)間，而在A里面每次做計(jì)算僅花1微秒（相對(duì)秒級(jí)，微妙可以忽略不計(jì)）。有二種方案：方案一：每次計(jì)算A都從B中讀數(shù)據(jù)，做1000次就要花1000秒以上。方案二：先把數(shù)據(jù)塊X讀取到A中“緩存”起來(lái)，然后在A在它的緩存內(nèi)做快速計(jì)算，算完后A將結(jié)果從緩存再存回B。這樣總共不過(guò)花近似2秒的時(shí)間罷了。方案二比方案一要快非常多。這就是現(xiàn)在計(jì)算系統(tǒng)所用的概念—充分利用靠近CPU的存儲(chǔ)層次作“緩存”。存儲(chǔ)設(shè)備—顯存

83顯存（Videomemory）：全稱(chēng)是顯示存儲(chǔ)器，專(zhuān)門(mén)用來(lái)存儲(chǔ)要顯示的圖像數(shù)據(jù)。圖像數(shù)據(jù)數(shù)量巨大，更新速度極快，如果用內(nèi)存來(lái)存放這些數(shù)據(jù)可能大幅降低系統(tǒng)性能。顯存的材料一般和內(nèi)存一樣，都是DRAM，大小也比較相近，低端的只有數(shù)百M(fèi)B，中高端的配置都在GB級(jí)別。像素點(diǎn)（Pixel）：即顯示器上顯示畫(huà)面的一個(gè)個(gè)很小的點(diǎn)，當(dāng)畫(huà)面的分辨率是1024×768時(shí)，就代表有1024×768這么多的像素點(diǎn)。每個(gè)像素點(diǎn)都用4至64位的數(shù)據(jù)來(lái)控制它的亮度和色彩，各類(lèi)色彩不過(guò)就是紅綠藍(lán)（RGB）三原色依照不同比率所組合而成的。存儲(chǔ)設(shè)備—顯存

84幀（frame）：像素點(diǎn)在一個(gè)瞬間構(gòu)成一幅圖形畫(huà)面。畫(huà)面的連續(xù)變換就形成了人眼看到的動(dòng)畫(huà)或視頻。

為了保持畫(huà)面流暢，要輸出和要處理的多幅幀的像素?cái)?shù)據(jù)非常多，更新也非常頻繁，所以好的計(jì)算機(jī)往往都配置專(zhuān)門(mén)的顯存來(lái)保存這些像素的數(shù)據(jù)，達(dá)到緩沖效果，再交由顯示圖像用的芯片和CPU進(jìn)行處理和調(diào)配，最后把運(yùn)算結(jié)果轉(zhuǎn)化為圖形輸出到顯示器上。幀率（Framerate）：即每秒顯示的幀數(shù)（FPS，F(xiàn)ramepersecond），也叫做和畫(huà)面的流暢度是有關(guān)系的，高的幀率可以得到更流暢、更逼真的畫(huà)面。一般來(lái)說(shuō)30fps就可以有流暢的畫(huà)面。而60fps就更為逼真和流暢了，但是高fps需要對(duì)顯卡的性能有更高的要求。存儲(chǔ)設(shè)備—用晶體管制成DRAM和SRAM

85DRAM和SRAM都是用許多晶體管組成的存儲(chǔ)結(jié)構(gòu)，一個(gè)DRAM的存儲(chǔ)單元僅僅是由一個(gè)晶體管加上一個(gè)電容組合而成，表示一個(gè)bit。電容里存儲(chǔ)的電荷數(shù)量用來(lái)表示這個(gè)bit是0或1。由于電容會(huì)一直慢慢漏電，漏電到一定程度就無(wú)法保存這個(gè)存儲(chǔ)單元的信息。所以規(guī)定每隔一定時(shí)間就刷新一次DRAM，也就是給電容充電，所以它叫動(dòng)態(tài)存儲(chǔ)單元。存儲(chǔ)設(shè)備—用晶體管制成DRAM和SRAM

86在高速緩存里，使用的是另一種更為復(fù)雜快速的存儲(chǔ)單元，也就是靜態(tài)存儲(chǔ)單元—SRAM。SRAM不需要充電，它用多達(dá)六個(gè)晶體管組成了一個(gè)循環(huán)的結(jié)構(gòu)。同樣是存儲(chǔ)一個(gè)bit，SRAM用6個(gè)晶體管