第二章 計算機算術

• 數據表示決定了計算機所執行操作的類型，數據從一個位置傳到另一個位置的方法，
  以及對存儲元件的特性要求。
• 浮點運算是非常重要的，因為它的實現決定了計算機執行復雜圖形變換和圖像處理的速度，
  而且浮點運算對計算的準確度也有很重要的影響。
• 計算機如何進行加減乘除運算

2.1 數據是什么

數據是?各種各樣的信息，如數字、文本、計算機程序、音樂、圖像、符號、運動圖像、DNA密碼，等等。
實際上，信息可以是能夠被計算機存儲和處理的任何事物。

2.1.1 位與字節

計算機內存儲和處理信息的最小單位是位(bit，或比特)。一個比特的值可以是0或1，
它是?不可分的。

數字計算機將信息以?一組或一串比特?(稱作?字)的形式保存在存儲器中。
例如，串01011110表示一個8位的字。

計算機通過高低電壓兩個等級來存儲0和1的狀態

目前人們還不能制造出價格便宜的、能夠可靠地區分出十個不同電壓等級的電路，
只能制造出便宜的、能夠區分我們稱之為0和1的兩個電壓等級的電路。

計算機通常不會每次只對一個二進制位進行操作，它們會對一組二進制位進行操作。

• 8個二進制位為一個?字節?(byte)。

一般來講，計算機能夠?同時處理的位數越多，速度就會越快。
隨著計算機的速度越來越快，價格越來越低，一臺計算機一次能處理的位的組數也越來越多。

2.1.2 位模式

Figure :

上圖描述了如何用1位、2位、3位和4位得到一個二進制的值序列。

一個n位的字將得到$2^n$條不同的路徑或位模式。

信息表示

一個n位的字將得到$2^n$不同的位模式。

一個n位的二進制字什么也表示不了; 二進制1和0組成的串?沒有任何內在含義。

怎樣解釋一個特定的二進制數只取決于程序員賦予它何種含

• 指令: 字長為32位或更長的計算機用一個字來表示cpu能夠完成的操作。
  8位或16位計算機用多個字表示一條指令。其二進制編碼與功能之間的關系由設計者決定
• 數量: 一個字或多個字都可以用來表示數量。
  
  數可被表示為多種格式(如BCD整數、無符號二進制整數、有符號二進制整數、二進制浮點數、
  整數復數、浮點復數、雙精度整數，等等)。
• 字符: 字符是一個叫作“字母表”的集合中的元素。
• ISO 7位字符碼或ASCII碼(美國信息交換標準代碼)是在計算機工業中應用
  得非常廣泛的一種編碼，

• Figure :
  • 用7位表示一個字符，一共可以表示 $2^7=128$ 個不同的字符。
  • 其中有96個字符是可打印字符。
  • 其余32個是不可打印的，用于完成回車、退格、換行等特殊功能。
• 因為計算機都是面向字節的，它通?？梢酝ㄟ^在最高位前補0的方法將7位ASCII碼
  轉換為8位
  • ASCII碼表的?列號作為編碼的高3位，行號作為編碼的低4位
    • 例如: 字符"Z"二進制編碼為 101 1010
• • 擴展ASCII編碼
    • 最高位為0: 表示標準ASCII碼
    • 最高位是1: 表示新的字符
• 圖像、聲音和視覺: 數字計算機處理大量表示聲音、靜態圖像和視頻的數據。
  • 組成照片的基本單位是像素(picture element)，
    每個像素的大小可以是 8 位(單色)或 24 位(三基)。
  • 視頻作為?一串靜態圖像?依次傳輸，每秒發送60次（60次/s)
  • 聲音通過波形信號采樣

2.2 數字

2.2.1 位置計數法

按照位置記數法，一個n位的整數N的形式表示:

• 這里$a_i (i=0,1....,n-1)$是與b的i次冪相乘的系數(此處b為基數)。

用小數點將整數部分和小數部分分開，可以對位置記數法進行擴展，使其能表示實數。

一個用基數b的位置記數法表示的數的值被定義為:.

在計算機主要關注下列四種數制

• 十進制位置記數法不能精確地表示所有小數
• 同樣，二進制也不能精確地表示所有小數

2.3 二進制運算

二進制算術運算的規則與十進制基本相同; 唯一的區別在于，十進制算術運算以10為基數，
每位有10個數字，而二進制運算以2為基數，每位只有2個數字。

Figure :

兩個位相加可能產生?進位?或?借位

二進制加法示例

二進制減法示例

• 小數減去大數時，用大數減去小數，結果取負

二進制乘法示例

兩個n位字相乘，將產生一個2n位的積

計算機不是按照上述規則進行計算的。

表示范圍、精度、準確性和誤差

• 表示范圍(Range): 一個數所能表示的最大值和最小值的差就是它的表示范圍。MAX-MIN
• 精度(Precision): 數的精度是數據表示得有多好的衡量標準之一
• 準確度(Accuracy): 數的表示值與其的真實值之間的差
• 誤差(Error): 誤差 = 真實值 - 測量值

2.4 有符號數

負數可以用很多種不同的方式表示，但計算機設計者選擇了3種方法

• 符號及值表示法
• 二進制補碼表示法
• 移碼表示法。

每種方法都有其各自的優點和缺點。

2.4.1 符號及值表示法

一個n位字可以表示從 $0～2^{n-1}$ 共 $2^n$ 個可能的值。
例如，一個8位的字可以表示 $0,1,2,\cdots,254,255$ 共256個數

如果要表示負數，一種方法是用它的?最高位表示符號。

• 符號位為?0表示正數
• 符號位為?1表示負數。

有符號數的值為: $(-1)^S \times M$

• S: 符號位的值
• M: 數值部分的值

Figure :

n位有符號的表示范圍為 $-(2^{n-1}-1)$ 至 $+(2^{n-1}-1)$。

確定是0有兩種表示方法；例如在8位有符號數中，0的表示：
$00000000=+0$ 以及 $10000000=-0$

2.4.2 二進制補碼

補數概念

補數的定義: 是對于給定的進位制，相加后能使自然數a的位數增加1的最小的數

設 n 位 b 進制數 a，規定如下

b進制數a的關于基數的補數(b的補數): $b^n - a$

b進制數a的關于減基數的補數(b - 1的補數，簡稱減補數、儕補數): $b^n - a - 1$

在N進制下，求數a的補數的計算方式

對于N進制的自然數 $a=a_ra{r-1}a{r-2}\cdots a_1a_0$
規定 數b的各位 $b_i=(N+1)+a_i$為，稱數b為 a關于 N+1 的補數

在十進制下 求數 2304671 的補數。

• 令N=9時，自然數 2304671 對應的補數為 7695328
• 當N=10時，自然數 2304671 對應的補數為 7695328+1=7695329

在二進制下，求1的補數只需簡單地將0與1相互替換。求二補數(即補碼)，只需要將1的補數加1

• 二進制的 101010110 對應的1的補數是 010101001。
• 二進制的 101010110 對應的2補數是 010101001 + 1 = 010101010。

微處理器使用二進制補碼系統表示有符號整數，因為它可以將?減法運算 轉換為對 減數的補數的加法運算。

例如：用7加上5的補數就可以完成運算7減去5。

一個數與它的補數之和是一個常數

在n位二進制算術中，數P的補數為Q且 $|P| + |Q| =2^n$

補碼: 一個n位二進制數N的補碼定義為 $2^n - N$；

當8位二進制數 $N=5=00000101$，
補碼 $[N]_補=2^8-N=100000000-00000101=11111011$

首先，對于二進制數來說，只要定好了位長，
進行反碼（1的補數）和補碼（2的補數）
其實是一件很簡單的事情。在純二進制的表示下，
只有0和1，別無他物。0111(4位)的反碼就是1000，
補碼就是1001（反碼加1）。所謂正負、符號這些人賦予的意義都不存在，
只有二進制數和這些簡單操作

在計算機中表示負數，如果用最高位表示符號這種“原碼”方式，
雖然有利于人的閱讀，但?不利于其本身的計算。
所以系統內部就?把負數統一用“其對應正數的補碼”來表示，
而正數自己不用改變。這樣變換后，正數雖然形式上沒有變，
但與原碼相比，含義卻變了，因為?符號位已經不再是符號位了，

此時的?正數和負數?都在一致的“補碼編碼空間”中。 。

由于原碼空間到補碼空間的轉化，只需要對負數進行，正數是不用
發生任何變化

正數在計算機“補碼編碼空間”中的表示和原碼一致。
但這絕?不等價于?“對正數進行補碼運算，結果是其本身”。

下面來看計算機中補碼的運算過程：首先我們將4個數 +5，
-5，+7和 -7 以補碼形式表示

• +5 = 00000101
• -5 = 11111011
• +7 = 00000111
• -7 = 11111001

下面計算 7 - 5

結果為9位二進制數100000010。如果忽略最左邊一位(也叫“進位位”)，
結果為00000010 = +2，這正是我們所希望看到的結果。

下面計算5 - 7

結果為11111110(進位位為0)。我們預期的結果為-2;
即$2^8 - 2=10000000-00000010 = 11111110$ 。
再一次得到了所需要的結果。

考慮n位二進制算術運算 $Z=X-Y$，我們用X加上Y的補數來完成這一運算。
Y的補碼為 $2^n - Y$，則有 $Z=X+(2^n-Y)=2^n+(X-Y)$。

也就是說，我們得到了所需要的結果，X-Y，
以及位于最左邊的一個并不需要的進位(即 $2^n$)，而這個?進位被丟棄了。

一個數連續兩次求補碼得到本身

補碼的特點

補碼是一個真正的互補系統，因為 $+X+(-X)=0$。

補碼0被表示為00…0，是唯一的。

補碼的?最高位為符號位。

• 符號位為0，則該數為正
• 符號位為1，則該數為負。

n位二進制補碼數的表示范圍為 $-2^{n-1} ~ 2^{n-1}-1$。
對于n=8，補碼表示范圍為-128～~127。共有$2^8=256$個不同的數

補碼加法和減法使用同樣的硬件完成，因為補碼減法由被減數加上減數的補數實現。

運算溢出: 5位有符號二進制補碼數的表示范圍為 -16～+15

如果兩個正數相加且結果大于15，會超出5位二進制補碼的表示范圍

如果兩個負數相加且結果小于-16，也會超出5位二進制補碼的表示范圍

2.5 乘法簡介

2.5.1 移位運算

先介紹?二進制補碼數的算術移位運算

• 二進制補碼左移一位等價于將該數乘2。
  • 十進制數39的二進制表示為00100111,
    左移一位得到01001110，對應于十進制數78。
  • 有符號二進制補碼數11100011表示十進制數–29,
    左移一位之后的結果是11000110，表示十進制數-58。

• 二進制數右移一位相當于它除以2。
  • 00001100(十進制數12)右移一位得到00000110(十進制數6)。
    
    
    
    注意，00001101(即13)右移一位也會得到00000110，也是6;
    這是因為移出的?最低位被丟棄?了。
  • 為了在移位時保持二進制補碼數的?符號不變，右移時應該復制符號位。
    
    
    考慮11100010(即-30), 右移一位同時保持符號位不變將得到11110001，
    等價于-15。

2.5.2 無符號二進制乘法

人們手動計算乘法過程

數字計算機并沒有實現上面的算法，因為這種算法要求計算機存儲n個部分積，
然后將它們同時相加。

一種更好的技術是每得到一個部分積時就做一次加法。

一個計算兩個n位無符號二進制數相乘的算法。

算法示例

2.5.3 快速乘法

通過?移位和加法?實現的乘法速度很慢。實際的計算機采用了多種方法加快乘法運算的速度。
例如，構造專門的?邏輯陣列直接得到兩個數的積?而不必對操作數移位。

與負數相乘

Figure :

使用移位和加法等速度相對較快的操作以避免使用乘法?？紤]P乘以10和P乘以9

• $10P=2\times (2 \times 2 \times P + P)$: 即將P左移兩次，加上P，再將和左移一次。
• $9P=2\times 2 \times 2 \times P + P$: 即將P左移三次,加上P得到結果。

借組查找表實現，將兩個數相乘所有可能的積都保存在一個只讀存儲器內,
只需要進行簡單查找表就可以確定乘積。

• 占用空間太大
• 減少查找表的大小
• 假設要計算兩個16位數A與B的乘積。
• 可以將16位數A拆分為兩個8位數$A_u$和$A_l$，
• 如果A=1111000010101010，則$A_u=11110000$，$A_l=10101010$。
• A可被表示為$A_u x 256 + A$, 同理B也可以這樣表示

• Figure :

2.5.4 除法

二進制除法和十進制出發計算類似

計算機實現的除法算法--恢復余數除法

唯一需要修改的就是除數與部分被除數的比較方法。
人們用心算進行比較，而計算機必須做減法并檢測結果的符號位。
如果減法的?結果為正，則商1，
但若?結果為負，則應商О?并將?部分被除數與除數相加，
將其?恢復為原先的值

Figure :

恢復余數除法示例

Figure :

計算機實現的除法算法--不恢復余數除法

部分被除數減去除數之后，將檢測新的部分被除數的符號位。

• 若為?負，則商左移1位，商的最低位補0，并將部分被除數?加上?除數的二分之一。
• 若為?正?，則商左移1位，商的最低位補1，并將部分被除數?減去?除數的二分之一。

Figure :

不恢復余數除法示例

2.6 浮點數

浮點數即為實數，稱為浮點數的原因是小數點在數中?位置不固定。

浮點數存儲分成?兩部分：數值和小數點在數值中的位置

使用科學計數法來表示浮點數，科學計數法的好處是可以表示很大或者很小的數。

• 在十進制運算中，科學計數法表示的數字被寫成 $尾數×10^{指數}$ 的形式，
• 二進制浮點數則被表示為 $尾數×2^{指數}$ 的形式。

其中?尾數表示值;?指數表示小數點在數值中的位置

計算機中浮點數運算結果?一般是不確定的。不同芯片對浮點數的出來可能是不同的。

由于浮點數被定義為兩個值的積，浮點數的表示并不唯一，需要對其進行規格化。

規格化

為了使表示法的固定部分統一，科學計數法（用于十進制）和浮點表示法（用于二進制)
都在?小數點左邊使用了唯一的非零數碼，這稱為?規范化?。
十進制系統中的數碼可能是1～9，而二進制只能是1.

偏置指數(余碼系統)：指數使用n位表示；給指數加上一個常熟，使得最小負指數為0

• 這個常數為: $2^{n-1} - 1$

下圖給出了?4位指數?的偏置指數對應關系。

2.6.1 IEEE浮點數

IEEE 754浮點數標準提供了3種浮點數表示

• 32位單精度浮點數
• 64位雙精度浮點數
• 128位四精度浮點數

一個32位IEEE 754單精度浮點數可以被表示為下面的二進制位串:
S EEEEEEEE 1.MMMMMMMMMMMMMMMMMMMMMMM

• S為符號位，指明這個數是正數還是負數
• E為8位偏置指數，指出了小數點的位置，表示尾數擴大或縮小 $2^E$倍
• M是23位小數尾數。
  • 尾數最前的那個1被省掉了

32位IEEE754浮點數結構

• S位為符號位，決定了數的符號。若S=0，該數為正數,若S=1，則該數為負。
• 指數E將浮點數的尾數擴大或縮小2的E次方倍,并且它的偏置值為127。
• 非零的IEEE 754標準的浮點數可表示為: $X=(-1)^S\times 2^{E-B}\times 1.F$
  • S: 符號位
  • E: 偏置值為B的指數
  • F: 尾數的小數部分(實際為1.F)

• 浮點數0表示為: $S=0 E=0 F=0000...000$

IEEE754浮點數格式

• 非數(Not a Number, NaN): 是IEEE 754標準的一個重要概念。
  NaN是IEEE 754標準提供的一個專門符號，
  代表IEEE 754標準格式所?不能表示的數。
  NaN 的使用和定義是與系統相關的,
  可以用NaN來表示所需要表達的任何信息。

Figure :

十進制轉為二進制浮點數示例

二進制浮點數轉為十進制數

浮點數的特點

接近0的浮點數: 指數為2位;；尾數為2位的浮點數系統

Figure :

浮點數0附近有一塊?禁止區，其中的浮點數都是?非規格化的，
因此無法被表示為IEEE標準格式。這個數的指數和起始位都是0的區域，也可用來表示浮點數。
不過，這些數都是非規格化的，其?精度比規格化數的精度低，會導致?漸進式下溢。

IEEE標準的其他特點

• 缺省的舍入應該?向最近的值舍入。
  
  如果一個數與兩個最近的可表示的值的?距離相等，則選擇?最低位為0的作為舍入值;
  也就是說,?向偶數值舍入。
  
  標準要求必須提供(向0舍入,向正無窮大舍入,向負無窮大舍入)3種舍入模式。
  ?
• 規定了4種比較結果，分別是?等于、小于、大于?和?無序
  • 無序,用于一個操作數是NaN數的情形。

• 規定了5種異常。異?；蛑袛嗍且环N強制計算機進行專門處理機制。

IEEE標準定義的異常有:

• 操作數不合法——當程序員試圖使用一些不合法的操作數
  (如 NaN 數，與無窮大數相加或相減時,或求負數的平方根)時,會引發這種異常。
  
  ?
• 除數為0——當除數為0(因為結果為無窮大)時,會引發這種異常。
  ?
• 上溢——當結果比最大浮點數還大時會引發這種異常。
  
  處理上溢的方法有?終止計算?或?飽和運算(用最大值作為結果)等。
  
  ?
• 下溢——當結果比最小浮點數還小時會引發這種異常;
• 結果不準確——當某個操作產生?舍入錯誤?時會引發這種異常。

2.7 浮點數運算

浮點數時不能直接進行加法運算。

浮點數加法的計算步驟: 先對階數，尾數相加，結果規格化。

第1步，找出指數較小的那個數。
第2步，使兩個數的指數相同。對于指數小的那個數，指數加幾，就將尾數右移幾位。
第3步，尾數相加(或相減)。
第4步，如果有必要，將結果規格化(后規格化)。

Figure :

因為?指數?有時與?尾數?位于同一個字中，在加法過程開始之前必須將它們分離開(解壓縮)。

如果兩個指數的差大于p+1，這里p為尾數的位數，較小的那個數由于太小而無法影響較大的數，
結果實際上就等于較大的那個數。

結果規格化時會檢查指數，看它是否比最小指數小或比最大指數大，
以分別檢測指數下溢或上溢。指數下溢會導致結果為0，
而指數上溢會造成錯誤，可能會要求操作系統介入處理。

舍入與截斷誤差

因為浮點運算可能引起尾數位數的增加，因此需要能夠保持尾數位數不變的方法。
最簡單的技術叫作截斷(truncation)。

截斷會產生?誘導誤差(induced error)(即誤差是由施加在數上的操作計算所引起的)，
誘導誤差是偏置的，因為?截斷后的數總是比截斷前的小。

舍入(rounding)是一種更好的減少數的位數的技術。
如果丟棄的位的值?大于?剩余數?最低位?的一半，則將剩余數的最低位加1。

• 舍入更加精確并會引起?非偏置的誤差。
• 截斷總會使結果變小，帶來系統性誤差，
• 舍入的主要不足在于它需要對結果進行一個?額外的算術操作

舍入機制

• 最簡單的舍入機制是截斷或向0舍入。
• “向最近的數舍入”方法，會選擇?距離該數最近?的那個浮點數作為結果。
• “向正或負無窮大舍入”方法，會選擇?正或負無窮大方向上最近?的有效浮點數作為結果。

當要舍入的數位于兩個連續浮點數的正中時，IEEE舍入機制會選擇最低位為0的點(即向偶數舍入)。

2.8 浮點數與程序員

整數操作時精確、可重復的，浮點數操作是不精確的。

考慮表達式 $z = x^2-y^2$，x、y、z都是實數。
可以將表達式視作 $x^2-y^2$ 或 $(x+y)(x-y)$ 計算，整數運算得到相同結果，
但浮點數運算可能得到不同結果。

IEEE要求加、減、乘和除運算結果能夠?精確計算，并用向偶數舍入的方法將結果舍入為最近的浮點數。

2.8.1 誤差傳播

舍入造成的生成誤差(generated error)或通過計算鏈傳播的傳播誤差(propagated error)
都會被引人浮點運算。

2.8.2 生成數學函數

考慮使用泰勒公式來求一些高級函數在某點的值。