零. 課程要點：

• 了解基礎邏輯電路
• C語言中的各類運算
• 判斷溢出與數(shù)據(jù)舍入

如果沒學過基礎邏輯電路，應該是有專門的一門課《數(shù)字邏輯電路》，那門課里有更詳細的介紹。因為比較注重邏輯推理，據(jù)大學的數(shù)電老師說，自從教了這門課，反正他打橋牌就沒怎么輸過。在計算機系統(tǒng)基礎這門課里只是引用一些邏輯部件，更重要的是理解C語言中各類運算是怎么通過電路實現(xiàn)的，由此可能存在怎樣的溢出問題，這才是我們學習的重點。

另外，推薦大家一本書《編碼：隱匿在計算機軟硬件背后的語言》，可以看成是“如何一步步搭建一臺計算機”，但是卻一點都不晦澀難懂，非常生動有趣哦。

一. 數(shù)字邏輯電路

1. 與門，或門，非門，異或門

   
   
   門電路

2. 多路選擇器

   
   
   多路選擇器
3. 一位加法器（全加器）
   低位進位為C_in，和為F，高位進位為C_out
   
   一位加法器
4. n位加法器
   由n個全加器構成，例：A=1001，B=1100，則F=0101，C_out=1
   n位加法器能實現(xiàn)無符號的整數(shù)加，但無法用于帶符號整數(shù)加，無法判斷是否溢出
   
   n位加法器
5. n位帶標準加法器
   溢出標志OF=C_nC_n-1
   進位/借位標志CF=C_outC_in
   符號標志SF=F_n-1
   零標志ZF=1當且僅當F=0
   
   n位帶標志加法器
6. n位整數(shù)加/減運算器
   [A-B]_補 = [A]_補 + [-B]_補 = [A]_補 + + 1
   
   n位整數(shù)加減運算器
7. 算術邏輯部件（ALU）
   實現(xiàn)基本算術運算與邏輯運算，核心電路是帶標志加法器，操作控制端ALU_op決定操作的類型。
   
   ALU

二. C語言中的運算

• 算術運算：無符號數(shù)、帶符號數(shù)、浮點數(shù)的加減乘除余運算。
• 按位運算：按位與，或，取反，異或，主要用于“掩碼”操作。
• 移位運算：邏輯左/右移，算術左/右移，主要用于提取部分信息，或擴大/縮小2的倍數(shù)。
• 邏輯運算：與，或，非。主要用于關系表達式。
• 位擴展和位截斷運算：主要用于類型轉(zhuǎn)換。

& 如何判斷邏輯移位還是算術移位，怎么移位？

從運算符無法區(qū)分，由X的類型決定：

• 若X為無符號數(shù)，則為邏輯移位。
  a. 邏輯左移：高位移出，低位補0，若高位移出的是1，則發(fā)生溢出！如：197 = 1100 0101 << 2 = 0001 0100 = 20。這是因為8位無符號數(shù)可以表示0~255，高位為1，表示數(shù)值大于等于128，左移代表乘上2的倍數(shù)，超過了最大可表示范圍，所以結果肯定是溢出的。
  b. 邏輯右移：低位移出，高位補0，不會溢出，但可能發(fā)生有效數(shù)據(jù)丟失。197 = 1100 0101 >> 1 = 0110 0010 = 98，精確的值應該是98.5，這里發(fā)生了有效數(shù)據(jù)的丟失。

• 若X為帶符號數(shù)，則為算術移位。
  a. 算術左移：高位移出，低位補0，若移出的位不等于新的符號位，則發(fā)生溢出！如：-81 = 1010 1111 << 1 = 0101 1110 = 94。擴大和縮小倍數(shù)不應該改變符號位，所以符號位發(fā)生了變化，結果肯定是溢出的。
  b. 算術右移：低位移出，高位補符，不會溢出，但可能發(fā)生有效數(shù)據(jù)丟失。如：-81 = 1010 1111 >> 1 = 1101 0111 = -41，精確的值應該是40.5，這里發(fā)生了有效數(shù)據(jù)的丟失。

& 類型轉(zhuǎn)換時如何進行位擴展和位截斷？

• 位擴展：短轉(zhuǎn)長
  a. 無符號數(shù)：0擴展，如：-32768 = 0x80 00 -> 0x00 00 80 00
  b. 帶符號數(shù)：符號擴展，如：-32768 = 0x80 00 -> 0xFF FF 80 00
  想想為什么帶符號數(shù)位擴展要進行符號擴展？我們求負數(shù)補碼對應的真值時，從右往左第一個1之后按位取反，所以符號擴展不影響真值。

• 位截斷：長轉(zhuǎn)短
  強行將高位丟棄，可能發(fā)生溢出。如：int i = 32768 = 0x00 00 80 00，則(short) i = 0x80 00 = -32768。

& 整數(shù)加/減運算中的溢出判斷

無符號數(shù)和帶符號數(shù)加減運算都用以下部件完成：

n位整數(shù)加減運算器

• 無符號加法溢出判斷條件：進位標志CF=C_outC_in=1
  做加法操作時，C_in=0，所以CF=C_out0=C_out，所以對于無符號數(shù)加法，只需要看最高位是否產(chǎn)生進位。也確實如此，兩個無符號數(shù)相加，最高位進位了，說明和超過了最大可表示范圍（即溢出），但由于位數(shù)有限，所以這個進位被舍棄了，值反而變小了，也就是產(chǎn)生了溢出。如：156 + 123 = 1001 1101 + 0111 1011 = 0001 1000 = 24 ( = 279 - 255)。

• 帶符號加法溢出判斷條件：溢出標志OF=C_nC_n-1=1
  最高位的進位和次高位的進位不同時則產(chǎn)生溢出，或者說兩個加數(shù)的符號位相同但與和符號位不同，只是這個表達式看起來不是太好理解。我們分類來討論一下：
  a. 一個正數(shù)和一個負數(shù)相加，肯定不會溢出。最高位相加肯定是1，如果次高位進位C_n-1為1，那么最高位也要向前進位，因此OF=11=0，同理如果次高位進位C_n-1為0，那么最高位也無需向前進位，因此OF=00=0，都不會產(chǎn)生溢出。
  b. 兩個正數(shù)相加，最高位都是0，那么C_n肯定是為0，發(fā)生溢出的情況只有C_n-1為1，即OF=01=1，此時符號位改變了，結果確實產(chǎn)生了溢出。如：107 + 46 = 0110 1011 + 0010 1110 = 1001 1001 = -103。
  c. 兩個負數(shù)相加，最高位都是1，那么C_n肯定是為1，發(fā)生溢出的情況只有C_n-1為0，即OF=10=1，此時符號位改變了，結果確實產(chǎn)生了溢出。-107 + (-46) = 1001 0101 + 1101 0010 = 0101 0111 = 87。

• 無符號減法溢出判斷條件：借位標志CF=C_outC_in=1
  做減法操作時（用同一個運算部件，減法轉(zhuǎn)換成加法），C_in=1，所以CF=C_out1=C_out取反，所以對于無符號數(shù)減法，如果最高位沒有產(chǎn)生進位，則表示溢出。這個不太好理解?？梢赞D(zhuǎn)換成加法思考，兩個無符號數(shù)相減，其實都是轉(zhuǎn)換成加法，只是原來是直接相加，現(xiàn)在是加上減數(shù)的按位取反+1，只要加法結果溢出了，說明結果就是超過了可表示的范圍，所以判斷條件是一樣的。如：35 - B = 0010 0011 + + 1 = 0010 0100 + B^'，B^'也視作一個無符號數(shù)，那么如果這個結果溢出（即CF=1），那么說明結果超出無符號數(shù)可表示范圍。

• 帶符號減法溢出判斷條件：溢出標志OF=C_nC_n-1=1
  最高位的進位和次高位的進位不同時則產(chǎn)生溢出，或者說兩個加數(shù)的符號位相同但與和符號位不同（用同一個運算部件，減法轉(zhuǎn)換成加法），同加法分類討論：
  a. 兩個正數(shù)相減，或者兩個負數(shù)相減，肯定不會溢出。（理由同帶符號加法中一個正數(shù)和一個負數(shù)相加情況）
  b. 一個正數(shù)減一個負數(shù)，同兩個正數(shù)相加，用OF=1判斷；
  c. 一個負數(shù)減一個正數(shù)，同兩個負數(shù)相加，用OF=1判斷；

注：其實所謂的產(chǎn)生溢出，無非就是最后運算的結果超出了當前類型能表示的范圍，所以同樣兩個數(shù)相加減，當成無符號數(shù)或有符號數(shù)，溢出結果就可能不同。另外雖然我們上面進行了分類討論，但是對于輸入到整數(shù)加減運算器中的兩個數(shù)，計算機可不管你是無符號數(shù)還是帶符號數(shù)，一律都按同樣的方式進行運算，然后把標志位存下來，至于你要拿這個結果當無符號數(shù)還有符號數(shù)，或者判斷是否借位/溢出，都是你的事，這一點要記在心里。

& 整數(shù)乘法運算中的溢出判斷

兩個n位整數(shù)相乘，結果只取2n位乘積中的低n位，高n位可以用來判斷溢出：

• 無符號數(shù)：若高n位全0，則不溢出，否則溢出。這是因為對于無符號數(shù)，兩數(shù)相乘結果不能超過低n位可表示范圍，即高n位必須為0。如：25 = 5 x 5 = 0101 x 0101 = 0001 1001 = 1001 = 9 (= 25 - 16)。
• 帶符號數(shù)：若高n位全0或全1，且等于低n位的最高位，（或者或高n+1位全0或全1），則不溢出，否則溢出。（這個結論怎么推理出來的，之后再補充）

需要注意計算機硬件是不判溢出的，僅保留2n位乘積，供軟件使用，所以程序需進行一些防溢出的處理。

另外，整數(shù)乘法運算比較耗費時鐘周期，因此編譯器在處理變量與常數(shù)相乘時，往往用移位、加法和減法的組合來代替。如：x20 = x(16+4) = (x<<4)+(x<<2)，之前記得左移可能產(chǎn)生溢出，所以不論是否溢出，兩種運算方式結果都是一樣的。

& 整數(shù)除法運算中的截斷處理

對于整數(shù)除法外，因為商的絕對值不可能比被除數(shù)的絕對值大，所以不會發(fā)生溢出，只有一種例外：帶符號整數(shù)的-2^n-1/-1 = 2^n-1，記得我們介紹補碼時曾說過補碼能增加表示一個最小負數(shù)嗎?不過它沒有對應的正數(shù)，所以如果對它除-1，就發(fā)生溢出了。

另外，整數(shù)除法運算更耗時鐘周期，所以為了縮短運算時間，編譯器在處理一個變量與一個2的冪次形式的整數(shù)相除時，常用邏輯/算術右移運算來實現(xiàn)。如：3 = 12/4 = 0000 1100 >> 2 = 0000 0011 = 3，-3 = -12/4 = 1111 0100 >> 2 = 1111 1101 = -3。

整數(shù)除法是有可能不能整除的，那就必須采用朝零舍入的截斷方式。

• 無符號數(shù)，帶符號正整數(shù)：移出的低位直接丟棄。那就是說小數(shù)直接不要了，朝0舍入。如：3.5 = 14/4 = 0000 1110 >> 2 = 0000 0011 = 3。
• 帶符號負整數(shù)：先加上偏移量 2^k-1，然后再右移k位，低位截斷。為什么要這么做呢？我的理解是補碼的小數(shù)直接不要了，其實是朝無窮大方向舍入（why？之后再補充），那么要移出k位，只要這k位不為0，我先加上k個1，那么肯定會向前進個位，因此最后的結果會再加1，變成朝零舍入。如：-3.5 = -14/4 = 1111 0010 >> 2 = 1111 1100 = -4，這個和帶符號正整數(shù)出發(fā)得到的數(shù)值部分不一致。因此應該先加上偏移量2²-1 = 3，即(-14 + 2²-1)/4 = (1111 0010 + 0000 0011) >> 2 = 1111 1101 = -3。

& 浮點數(shù)運算

若兩個規(guī)格化浮點數(shù)為A = M_a·2^E_a，B = M_b·2^E_b，則：
A±B = (M_a ± M_b·2^-(E_a-E_b))·2^E_a （假設E_a >= E_b）
A*B = (M_a * M_b)·2^(E_a+E_b)
A/B = (M_a / M_b)·2^(E_a-E_b)

以上運算有可能出現(xiàn)幾種情況：
階碼上溢：正指數(shù)超過最大允許值（127） => +∞/-∞/溢出
階碼下溢：負指數(shù)超過最小允許值（-126） => +0/-0
尾數(shù)溢出：最高有效位有進位 => 右規(guī) （結果不一定溢出）
非規(guī)格化尾數(shù)：數(shù)值部分高位為0 => 左規(guī)
右規(guī)或?qū)﹄A時，右段有效位丟失 => 尾數(shù)舍入 （可以運算過程中添加保護位）

舉例說明如何計算浮點數(shù)加/減法：
0.5 + (-0.4375)
= 1.000 x 2^-1 + (-1.110 x 2^-2) （規(guī)格化）
= 1.000 x 2^-1 + (-0.111 x 2^-1) （對階，小階向大階看齊，尾數(shù)右移）
= 0.001 x 2^-1 （尾數(shù)加減）
= 1.000 x 2^-4 （規(guī)格化，左規(guī)：左移一位，階碼減1，判斷是否有階碼溢出）
= 0.0625 （是否需要考慮舍入；如果尾數(shù)是0，則需將階碼也置0，表示0）

在尾數(shù)右移的過程中，可能會發(fā)生超出規(guī)定位數(shù)的情況，可以在尾數(shù)右邊放一個保護位和一個舍入位，用來保護對階時右移的位或中間結果，當左規(guī)時被移入尾數(shù)中，作為舍入判斷的依據(jù)。
舉個例子：（假設尾數(shù)只有3位有效位）
0.59375 = 0.5 + 0.09375 = 1.00 x 2^-1 + 1.10 x 2^-4 = 1.00 x 2^-1 + 0.00 x 2^-1 （沒有附加位）= 1.00 x 2^-1 = 0.5
0.59375 = 0.5 + 0.09375 = 1.00 x 2^-1 + 1.10 x 2^-4 = 1.00 x 2^-1 + 0.0011 x 2^-1 （兩位附加位）= 1.0011 x 2^-1 = 1.01 x 2^-1 （舍入進位） = 0.625 （結果比上面更精確）
IEEE 754舍入的方式主要有就近舍入（舍入為最近可表示的數(shù)），正向舍入（+∞方向），負向舍入（-∞方向），和朝0方向舍入（正數(shù)floor，負數(shù)ceil）

C語言中有float和double類型的浮點數(shù)，分別對應IEEE 754單精讀浮點數(shù)格式和雙精度浮點數(shù)格式，那么在類型強制轉(zhuǎn)換的時候可能會有什么問題？（這就是為什么我們要學習數(shù)據(jù)在計算機中真正的存儲形式）

• 從int轉(zhuǎn)換為float時，不會發(fā)生溢出，但可能有數(shù)據(jù)被舍入（float尾數(shù)為23+1位）
  如：最大正數(shù)0111 ... 1111_32位 = 1.11 ... 1111_{30位小數(shù)} x 2³⁰ = 1.11 ... 1111_{23位小數(shù)} x 2³⁰（發(fā)生截斷）
• 從float轉(zhuǎn)換為int時，可能發(fā)生溢出，int沒有小數(shù)，數(shù)據(jù)可能會向0方向被截斷
• 從int轉(zhuǎn)換為double時，能保留精確值（double尾數(shù)為52+1位）
• 從double轉(zhuǎn)換為int時，可能發(fā)生溢出，int沒有小數(shù)，數(shù)據(jù)可能會向0方向被截斷
• 從float轉(zhuǎn)換位double時，能保留精確值（double有效位數(shù)更多）
• 從double轉(zhuǎn)換為float時，可能發(fā)生溢出，也可能有數(shù)據(jù)被舍入（有效尾數(shù)變少）

注：文中圖片來源于mooc官網(wǎng)