數(shù)據(jù)的表示和運算

數(shù)制與編碼

進位計數(shù)制及其相互轉(zhuǎn)換

十進制、二進制、八進制、十六進制的相互轉(zhuǎn)換

真值和機器數(shù)

真值

是指帶“+”或“-”符號的數(shù)，是機器數(shù)代表的實際值。

機器數(shù)

是指把符號“數(shù)字化”的數(shù)，其表示形式有原碼、補碼、反碼和移碼。

無符號整數(shù)：全部二進制位都是數(shù)值位，沒有符號位，第i位的位權(quán)是2的i-1次方。

n比特的無符號整數(shù)表示范圍為0-2n-1，超出則溢出，意味著該計算機無法一次處理這么多。

可以表示的最小的數(shù)全0，可以表示的最大的數(shù)全1。

加法：從最低位開始，按位相加，并往更高位進位。

減法：被減數(shù)不變，減數(shù)全部位按位取反，末尾加一，減法變加法。從最低位開始，按位相加，并往最高位進位。

編碼

BCD碼

用四位二進制代碼來表示一位10進制的數(shù)。最常見的是8421碼

ASCII碼

標(biāo)準(zhǔn)ASCII碼采用7位二進制代碼來表示通用控制字符、十進制數(shù)碼、英文大小寫字母和專用符號

漢字編碼

包括輸入編碼、漢字內(nèi)碼和漢字字形碼

校驗碼

奇偶校驗碼

在原編碼上加上一個校驗位，校驗整個校驗碼中“1”的個數(shù)是否為奇數(shù)或者偶數(shù)

奇校驗碼：整個校驗碼（有效信息位和校驗位）中“1”的個數(shù)為奇數(shù)。校驗位為0，否則為1

偶校驗碼：整個校驗碼（有效信息位和校驗位）中“1”的個數(shù)位偶數(shù)。校驗位為0，否則為1

偶校驗的硬件實現(xiàn)：各信息進行異或（模二加）運算，得到的結(jié)果為偶校驗位。異或是同0異1。

循環(huán)冗余（CRC）碼

在M為信息后面再拼接N位的校驗碼，利用模2除法校驗編碼正確性

海明校驗碼

在信息字段中插入若干位數(shù)據(jù)，用于監(jiān)督碼字里哪一位數(shù)據(jù)發(fā)生了變化，具有一位糾錯能力

定點數(shù)（帶符號整數(shù)）

表示

原碼

用機器數(shù)的最高位表示該數(shù)的符號，其余的各位表示該數(shù)的絕對值。符號位為0表示正數(shù)，符號位為1表示負數(shù)。

若機器字長n+1位，帶符號整數(shù)的原碼的表示范圍：

真值0有兩種形式，+0和-0，+0=0，0000000，-0=1，0000000

原碼中符號位不能參與運算，需要設(shè)計復(fù)雜的硬件電路才能處理

用補碼表示真值-符號位可以參與運算。

?

反碼

正數(shù)和原碼相同，負數(shù)為原碼的每位求反（不包括符號位）

帶符號整數(shù)的反碼的表示范圍：

補碼

正數(shù)和原碼相同，負數(shù)為反碼的末位加1，即負數(shù)為原碼的每位求反再加1（不包括符號位）

帶符號整數(shù)的補碼的表示范圍：

補碼加法：從最低位開始，按位相加（符號位參與運算），并往更高處進位。

移碼

補碼的符號位求反

移碼只能用來表示整數(shù)，真值0只有一種形式

帶符號整數(shù)的移碼的表示范圍：

原碼和反碼的合法表示范圍完全相同，都有兩種方法表示真值0

補碼的合法表示范圍比原碼多一個負數(shù)，只有一種方法表示真值0

常見考點：兩個數(shù)A和B進行某種運算后，是否發(fā)生溢出？

手算做題可以帶入十進制驗證，是否超出合法范圍

?

運算

移位運算

原碼和反碼的加減乘除運算

真值《-》原碼（0正1負）

原碼《-》反碼（正數(shù)相同，負數(shù)數(shù)值位取反）

原碼《-》補碼（正數(shù)相同，負數(shù)數(shù)值位取反，末尾加1）

反碼《-》補碼（正數(shù)相同，負數(shù)末尾加1）

[-x]補碼《-》[x]補碼（全部位按位取反，末尾加1）

補碼《-》移碼（符號位取反）

?

定點數(shù)（帶符號小數(shù)）

表示

原碼、反碼、補碼

運算

真值《-》原碼（0正1負）

原碼《-》反碼（正數(shù)相同，負數(shù)數(shù)值位取反）

原碼《-》補碼（正數(shù)相同，負數(shù)數(shù)值位取反，末尾加1）

反碼《-》補碼（正數(shù)相同，負數(shù)末尾加1）

[-x]補碼《-》[x]補碼（全部位按位取反，末尾加1）

補碼加減法運算方法

Nbit補碼X+Y，按位相加即可

Nbit補碼X-Y，將補碼Y全部按位取反，末位+1，得到[-Y]補，減法變加法。

?

標(biāo)志位生成

OF（溢出標(biāo)志，溢出為1，否則為0）

計算方法：OF等于最高位產(chǎn)生的進位異或次高位產(chǎn)生的進位

OF對無符號的加減法無意義

SF（符號標(biāo)志，結(jié)果為負號時為1，否則為0）

計算方法：SF=最高本位和

SF對無符號的加減法無意義

ZF（零標(biāo)志，運算結(jié)果為0時，ZF置為1，否則置為0）

計算方法：兩個數(shù)的運算結(jié)果為nbit，只有n位全為0時，ZF=1

CF（進位/借位標(biāo)志，進位借位時為1，否則置為0）

計算方法：最高位產(chǎn)生的進位異或sub，sub=1表示減法，sub=0表示加法。

CF對有符號數(shù)無意義

移位運算

算數(shù)移位

原碼：符號位不變，僅對數(shù)值位移位。右移：高位補0，低位舍棄。如果舍棄的位=0，則相當(dāng)于/2，若不=0，則會丟失精度。左移：低位補0，高位舍棄。若舍棄的位=0，則相當(dāng)于*2，若不=0，則會出現(xiàn)嚴(yán)重誤差

反碼：正數(shù)的反碼與原碼相同，正數(shù)反碼的移位運算也和原碼相同。負數(shù)的反碼數(shù)值位與原碼相反，因此負數(shù)反碼的移位運算規(guī)則如下。右移：高位補1，低位舍棄。左移：低位補1，高位舍棄。

補碼：正數(shù)的補碼和原碼相同，正數(shù)補碼的移位運算也和原碼相同。負數(shù)補碼=反碼末位+1。導(dǎo)致反碼最右邊幾個連續(xù)的1都因進位而變?yōu)?，直到進位碰到第一個0為止。負數(shù)補碼的算數(shù)移位規(guī)則如下：右移：高位補1，低位舍棄。左移，低位補0，高位舍棄。

邏輯移位

邏輯右移：高位補0，低位舍棄

邏輯左移：低位補0，高位舍棄

可以把邏輯移位看作是對無符號數(shù)的算數(shù)移位

循環(huán)移位

不帶進位位：用溢出的位補上空缺

帶進位位：移出的位放到進位位，原進位位補上空缺

兩個定點小數(shù)進行加減法時，需要先轉(zhuǎn)換為補碼

定點小數(shù)補碼的加法：從最低位開始，按位相加（符號位參與運算），并往更高位進位。

定點小數(shù)補碼的減法：被減數(shù)不變，減數(shù)全部位按位取反，末位+1，減法變加法。從最低位開始，按位相加，并往更高位進位。

位拓展時，定點小數(shù)是在末尾添0，定點整數(shù)是在符號位后填0

小數(shù)補碼加法和整數(shù)一樣，從最低位開始，按位相加（符號位參與運算），并往更高位進位。

小數(shù)補碼減法和整數(shù)一樣，被減數(shù)不變，減數(shù)全部位按位取反，末尾加1，減法變加法。從最低位開始，按位相加，并往更高位進位。

?

強制類型轉(zhuǎn)換

無符號數(shù)與有符號數(shù)：不改變數(shù)據(jù)內(nèi)容，改變解釋方式

長整數(shù)變短整數(shù)：高位截斷，保留低位

短整數(shù)變長整數(shù)：符號擴展

?

數(shù)據(jù)的存儲和排列方式

多字節(jié)數(shù)據(jù)在內(nèi)存里一定是占連續(xù)的幾個字節(jié)

01234567H中，最高有效字節(jié)（MSB）01，最低有效字節(jié)（LSB）67。

大端方式：01H 23H 45H 67H

小端方式：67H 45H 23H 01H

邊界對齊

現(xiàn)代計算機通常按字節(jié)編址，每個字節(jié)對應(yīng)一個地址。通常也支持按字、半字、字節(jié)尋址。設(shè)存儲字長為32位，一個字=32bit，半字=16bit，每次訪存只能讀寫1個字。

邊界對齊方式中，訪問一個字/半字都只需一次訪存

邊界不對齊方式中，訪問一個字/半字可能要兩次訪存

浮點數(shù)

表示

組成

階符、階碼（反映浮點數(shù)的表示范圍）、數(shù)符和尾數(shù)（反映浮點數(shù)精度）

階碼反映了浮點數(shù)的表示范圍和小數(shù)點的實際位置，尾數(shù)的數(shù)值部分的位數(shù)反映浮點數(shù)的精度。

階符的運算相當(dāng)于對尾數(shù)進行算數(shù)移位

規(guī)格化

規(guī)定尾數(shù)的最高數(shù)位必須是一個有效值

左規(guī)：尾數(shù)算數(shù)左移1位，階碼減1。直到尾數(shù)最高位是有效位。

右規(guī)：當(dāng)浮點數(shù)運算的結(jié)果尾數(shù)出現(xiàn)溢出（雙符號位為0或1）時，將尾數(shù)算數(shù)右移1位，階碼加1。

采用雙符號位，當(dāng)溢出發(fā)生時，可以挽救。更高的符號位是正確的符號位。

用原碼的表示的尾數(shù)規(guī)格化：規(guī)格化的原碼尾數(shù)，最高的數(shù)值位一定是1.正數(shù)時，最大值為0.1111...,最小值為0.100000.尾數(shù)的表示范圍為1/2《M《。

負數(shù)時，最大值為1.100000.，最小值為1.1111111.尾數(shù)的表示范圍為-（）《M《-1/2。

用補碼的表示的尾數(shù)規(guī)格化：規(guī)格化的補碼尾數(shù)，符號位與最高位數(shù)值位一定相反。正數(shù)時，最大值為0.1111...,最小值為0.100000.尾數(shù)的表示范圍為1/2《M《。

負數(shù)時，最大值為1.0111111.，最小值為1.000000.尾數(shù)的表示范圍為-《M《-1/2+。

超出最大負數(shù)和最小正數(shù)，當(dāng)作機器0，超出最大正數(shù)和負數(shù)，拋出上溢異常。

IEEE754標(biāo)準(zhǔn)

尾數(shù)用原碼表示，階碼用移碼表示

移碼=真值+偏置值

偏置值一般取2n-1，此時移碼=補碼符號位取反

階碼真值=移碼-偏移量

尾數(shù)部分隱含最高位1

短浮點數(shù)真值為

長浮點數(shù)真值為

單精度最小絕對值位E=1,M=0,最大絕對值E=254，M=1.11111

雙精度最小絕對值位E=1,M=0,最大絕對值E=2046，M=1.11111

當(dāng)階碼E全為0時，尾數(shù)不全為0時，表示非規(guī)格化小數(shù)。+-（0.xxxxxx）隱含最高位變?yōu)?，階碼真值固定位-126

階碼E全為0，尾數(shù)M全為0時，表示真值+-0

階碼E全為1，尾數(shù)M全為0時，表示無窮大

階碼E全為1，尾數(shù)M不全為0時，表示非數(shù)值“NAN”

?

運算

加減運算的步驟為對階、尾數(shù)求和、規(guī)格化、舍入和溢出判斷

加減運算

對階：小階向大階看齊

尾數(shù)相加

規(guī)格化：出現(xiàn)類似0.00114514*10，需要左規(guī)，階數(shù)-1.出現(xiàn)類似99.114514，需要右規(guī)，階數(shù)+1.

舍入：若規(guī)定只能保留幾位有效尾數(shù)，則進行舍入。舍入規(guī)則有多種，如直接砍掉，砍掉部分非0，則入1，四舍五入等。

判斷溢出：若規(guī)定階碼不能超過2位，則運算后階碼超出范圍，則溢出。尾數(shù)溢出未必導(dǎo)致整體溢出。

強制類型轉(zhuǎn)換

無損：char-int-long-double、float-double

有損：int-float（可能損失進度，float尾數(shù)的數(shù)值位有1+23位）、float-int（可能會溢出，也可能損失精度，比如小數(shù)轉(zhuǎn)整數(shù)）

Int范圍為-，float的范圍為

算數(shù)邏輯單元

一位全加器

最基本的加法單元，輸入兩位加數(shù)和地位的進位（三個輸入），輸出和以及高位的進位（兩個輸出）

本位和S=Ai異或Bi異或Ci-1

本位向高位的進位Ci=AiBi+（Ai異或Bi）Ci-1

串行加法器

只設(shè)一個全加器的加法器，串行進位

一位全加器＋進位觸發(fā)器，只能一位一位加

并行加法器

由若干個全加器構(gòu)成，使用先行進位提高加法器的運算速度

計算速度取決于進位產(chǎn)生和傳遞的速度

串行進位的并行加法器，把n個全加器串接起來，就可進行兩個n位數(shù)的相加。串行進位又稱為行波進位，每一級進位直接依賴于前一級的進位，即進位信號是逐級形成的。

第i位向更高位的進位Ci可根據(jù)被加數(shù)，加數(shù)的第1-i位，再結(jié)合C0即可確認。

ALU

一種組合邏輯電路，能夠進行多種算數(shù)運算和邏輯運算

基本邏輯運算：與和或

與：A·B

或：A+B

與非：

或非：

異或：A+B

非：