零. 課程要點(diǎn)：

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

如果沒學(xué)過基礎(chǔ)邏輯電路偿荷，應(yīng)該是有專門的一門課《數(shù)字邏輯電路》，那門課里有更詳細(xì)的介紹。因?yàn)楸容^注重邏輯推理，據(jù)大學(xué)的數(shù)電老師說率拒，自從教了這門課，反正他打橋牌就沒怎么輸過禁荒。在計(jì)算機(jī)系統(tǒng)基礎(chǔ)這門課里只是引用一些邏輯部件俏橘，更重要的是理解C語言中各類運(yùn)算是怎么通過電路實(shí)現(xiàn)的，由此可能存在怎樣的溢出問題圈浇，這才是我們學(xué)習(xí)的重點(diǎn)寥掐。

另外靴寂，推薦大家一本書《編碼：隱匿在計(jì)算機(jī)軟硬件背后的語言》，可以看成是“如何一步步搭建一臺(tái)計(jì)算機(jī)”召耘，但是卻一點(diǎn)都不晦澀難懂百炬，非常生動(dòng)有趣哦。

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

1. 與門污它，或門剖踊，非門，異或門

   
   
   門電路

2. 多路選擇器

   
   
   多路選擇器
3. 一位加法器（全加器）
   低位進(jìn)位為C_in衫贬，和為F德澈，高位進(jìn)位為C_out
   
   一位加法器
4. n位加法器
   由n個(gè)全加器構(gòu)成，例：A=1001固惯，B=1100梆造，則F=0101，C_out=1
   n位加法器能實(shí)現(xiàn)無符號(hào)的整數(shù)加葬毫，但無法用于帶符號(hào)整數(shù)加镇辉，無法判斷是否溢出
   
   n位加法器
5. n位帶標(biāo)準(zhǔn)加法器
   溢出標(biāo)志OF=C_nC_n-1
   進(jìn)位/借位標(biāo)志CF=C_outC_in
   符號(hào)標(biāo)志SF=F_n-1
   零標(biāo)志ZF=1當(dāng)且僅當(dāng)F=0
   
   n位帶標(biāo)志加法器
6. n位整數(shù)加/減運(yùn)算器
   [A-B]_補(bǔ) = [A]_補(bǔ) + [-B]_補(bǔ) = [A]_補(bǔ) + + 1
   
   n位整數(shù)加減運(yùn)算器
7. 算術(shù)邏輯部件（ALU）
   實(shí)現(xiàn)基本算術(shù)運(yùn)算與邏輯運(yùn)算，核心電路是帶標(biāo)志加法器贴捡，操作控制端ALU_op決定操作的類型忽肛。
   
   ALU

二. C語言中的運(yùn)算

• 算術(shù)運(yùn)算：無符號(hào)數(shù)、帶符號(hào)數(shù)烂斋、浮點(diǎn)數(shù)的加減乘除余運(yùn)算屹逛。
• 按位運(yùn)算：按位與，或汛骂，取反罕模，異或，主要用于“掩碼”操作香缺。
• 移位運(yùn)算：邏輯左/右移，算術(shù)左/右移歇僧，主要用于提取部分信息图张，或擴(kuò)大/縮小2的倍數(shù)。
• 邏輯運(yùn)算：與诈悍，或祸轮，非。主要用于關(guān)系表達(dá)式侥钳。
• 位擴(kuò)展和位截?cái)噙\(yùn)算：主要用于類型轉(zhuǎn)換适袜。

& 如何判斷邏輯移位還是算術(shù)移位，怎么移位舷夺？

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

• 若X為無符號(hào)數(shù)售貌，則為邏輯移位。
  a. 邏輯左移：高位移出疫萤，低位補(bǔ)0颂跨，若高位移出的是1，則發(fā)生溢出扯饶！如：197 = 1100 0101 << 2 = 0001 0100 = 20恒削。這是因?yàn)?位無符號(hào)數(shù)可以表示0~255，高位為1尾序，表示數(shù)值大于等于128钓丰，左移代表乘上2的倍數(shù)，超過了最大可表示范圍每币，所以結(jié)果肯定是溢出的携丁。
  b. 邏輯右移：低位移出，高位補(bǔ)0脯爪，不會(huì)溢出则北，但可能發(fā)生有效數(shù)據(jù)丟失。197 = 1100 0101 >> 1 = 0110 0010 = 98痕慢，精確的值應(yīng)該是98.5尚揣，這里發(fā)生了有效數(shù)據(jù)的丟失。

• 若X為帶符號(hào)數(shù)掖举，則為算術(shù)移位快骗。
  a. 算術(shù)左移：高位移出，低位補(bǔ)0塔次，若移出的位不等于新的符號(hào)位方篮，則發(fā)生溢出！如：-81 = 1010 1111 << 1 = 0101 1110 = 94励负。擴(kuò)大和縮小倍數(shù)不應(yīng)該改變符號(hào)位藕溅，所以符號(hào)位發(fā)生了變化，結(jié)果肯定是溢出的继榆。
  b. 算術(shù)右移：低位移出巾表，高位補(bǔ)符，不會(huì)溢出略吨，但可能發(fā)生有效數(shù)據(jù)丟失集币。如：-81 = 1010 1111 >> 1 = 1101 0111 = -41，精確的值應(yīng)該是40.5翠忠，這里發(fā)生了有效數(shù)據(jù)的丟失鞠苟。

& 類型轉(zhuǎn)換時(shí)如何進(jìn)行位擴(kuò)展和位截?cái)啵?/h6>

• 位擴(kuò)展：短轉(zhuǎn)長(zhǎng)
  a. 無符號(hào)數(shù)：0擴(kuò)展，如：-32768 = 0x80 00 -> 0x00 00 80 00
  b. 帶符號(hào)數(shù)：符號(hào)擴(kuò)展，如：-32768 = 0x80 00 -> 0xFF FF 80 00
  想想為什么帶符號(hào)數(shù)位擴(kuò)展要進(jìn)行符號(hào)擴(kuò)展当娱？我們求負(fù)數(shù)補(bǔ)碼對(duì)應(yīng)的真值時(shí)吃既，從右往左第一個(gè)1之后按位取反，所以符號(hào)擴(kuò)展不影響真值趾访。

• 位截?cái)啵洪L(zhǎng)轉(zhuǎn)短
  強(qiáng)行將高位丟棄态秧，可能發(fā)生溢出。如：int i = 32768 = 0x00 00 80 00扼鞋，則(short) i = 0x80 00 = -32768申鱼。

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

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

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

• 無符號(hào)加法溢出判斷條件：進(jìn)位標(biāo)志CF=C_outC_in=1
  做加法操作時(shí)，C_in=0云头，所以CF=C_out0=C_out捐友，所以對(duì)于無符號(hào)數(shù)加法，只需要看最高位是否產(chǎn)生進(jìn)位溃槐。也確實(shí)如此匣砖，兩個(gè)無符號(hào)數(shù)相加，最高位進(jìn)位了昏滴，說明和超過了最大可表示范圍（即溢出）猴鲫，但由于位數(shù)有限，所以這個(gè)進(jìn)位被舍棄了谣殊，值反而變小了拂共，也就是產(chǎn)生了溢出。如：156 + 123 = 1001 1101 + 0111 1011 = 0001 1000 = 24 ( = 279 - 255)姻几。

• 帶符號(hào)加法溢出判斷條件：溢出標(biāo)志OF=C_nC_n-1=1
  最高位的進(jìn)位和次高位的進(jìn)位不同時(shí)則產(chǎn)生溢出宜狐，或者說兩個(gè)加數(shù)的符號(hào)位相同但與和符號(hào)位不同，只是這個(gè)表達(dá)式看起來不是太好理解蛇捌。我們分類來討論一下：
  a. 一個(gè)正數(shù)和一個(gè)負(fù)數(shù)相加抚恒，肯定不會(huì)溢出。最高位相加肯定是1络拌，如果次高位進(jìn)位C_n-1為1俭驮，那么最高位也要向前進(jìn)位，因此OF=11=0春贸，同理如果次高位進(jìn)位C_n-1為0混萝，那么最高位也無需向前進(jìn)位，因此OF=00=0祥诽，都不會(huì)產(chǎn)生溢出譬圣。
  b. 兩個(gè)正數(shù)相加瓮恭，最高位都是0雄坪，那么C_n肯定是為0，發(fā)生溢出的情況只有C_n-1為1，即OF=01=1维哈，此時(shí)符號(hào)位改變了绳姨，結(jié)果確實(shí)產(chǎn)生了溢出。如：107 + 46 = 0110 1011 + 0010 1110 = 1001 1001 = -103阔挠。
  c. 兩個(gè)負(fù)數(shù)相加飘庄，最高位都是1，那么C_n肯定是為1购撼，發(fā)生溢出的情況只有C_n-1為0跪削，即OF=10=1，此時(shí)符號(hào)位改變了迂求，結(jié)果確實(shí)產(chǎn)生了溢出碾盐。-107 + (-46) = 1001 0101 + 1101 0010 = 0101 0111 = 87。

• 無符號(hào)減法溢出判斷條件：借位標(biāo)志CF=C_outC_in=1
  做減法操作時(shí)（用同一個(gè)運(yùn)算部件揩局，減法轉(zhuǎn)換成加法）毫玖，C_in=1，所以CF=C_out1=C_out取反凌盯，所以對(duì)于無符號(hào)數(shù)減法付枫，如果最高位沒有產(chǎn)生進(jìn)位，則表示溢出驰怎。這個(gè)不太好理解阐滩。可以轉(zhuǎn)換成加法思考砸西，兩個(gè)無符號(hào)數(shù)相減叶眉，其實(shí)都是轉(zhuǎn)換成加法，只是原來是直接相加芹枷，現(xiàn)在是加上減數(shù)的按位取反+1衅疙，只要加法結(jié)果溢出了，說明結(jié)果就是超過了可表示的范圍鸳慈，所以判斷條件是一樣的饱溢。如：35 - B = 0010 0011 + + 1 = 0010 0100 + B^'，B^'也視作一個(gè)無符號(hào)數(shù)走芋，那么如果這個(gè)結(jié)果溢出（即CF=1）绩郎，那么說明結(jié)果超出無符號(hào)數(shù)可表示范圍。

• 帶符號(hào)減法溢出判斷條件：溢出標(biāo)志OF=C_nC_n-1=1
  最高位的進(jìn)位和次高位的進(jìn)位不同時(shí)則產(chǎn)生溢出翁逞，或者說兩個(gè)加數(shù)的符號(hào)位相同但與和符號(hào)位不同（用同一個(gè)運(yùn)算部件肋杖，減法轉(zhuǎn)換成加法），同加法分類討論：
  a. 兩個(gè)正數(shù)相減挖函，或者兩個(gè)負(fù)數(shù)相減状植，肯定不會(huì)溢出。（理由同帶符號(hào)加法中一個(gè)正數(shù)和一個(gè)負(fù)數(shù)相加情況）
  b. 一個(gè)正數(shù)減一個(gè)負(fù)數(shù)，同兩個(gè)正數(shù)相加津畸，用OF=1判斷振定；
  c. 一個(gè)負(fù)數(shù)減一個(gè)正數(shù)，同兩個(gè)負(fù)數(shù)相加肉拓，用OF=1判斷后频；

注：其實(shí)所謂的產(chǎn)生溢出，無非就是最后運(yùn)算的結(jié)果超出了當(dāng)前類型能表示的范圍暖途，所以同樣兩個(gè)數(shù)相加減卑惜，當(dāng)成無符號(hào)數(shù)或有符號(hào)數(shù)，溢出結(jié)果就可能不同驻售。另外雖然我們上面進(jìn)行了分類討論残揉，但是對(duì)于輸入到整數(shù)加減運(yùn)算器中的兩個(gè)數(shù)，計(jì)算機(jī)可不管你是無符號(hào)數(shù)還是帶符號(hào)數(shù)芋浮，一律都按同樣的方式進(jìn)行運(yùn)算抱环，然后把標(biāo)志位存下來，至于你要拿這個(gè)結(jié)果當(dāng)無符號(hào)數(shù)還有符號(hào)數(shù)纸巷，或者判斷是否借位/溢出镇草，都是你的事，這一點(diǎn)要記在心里瘤旨。

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

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

• 無符號(hào)數(shù)：若高n位全0存哲，則不溢出因宇，否則溢出。這是因?yàn)閷?duì)于無符號(hào)數(shù)祟偷，兩數(shù)相乘結(jié)果不能超過低n位可表示范圍察滑，即高n位必須為0。如：25 = 5 x 5 = 0101 x 0101 = 0001 1001 = 1001 = 9 (= 25 - 16)修肠。
• 帶符號(hào)數(shù)：若高n位全0或全1贺辰，且等于低n位的最高位，（或者或高n+1位全0或全1）嵌施，則不溢出饲化，否則溢出。（這個(gè)結(jié)論怎么推理出來的吗伤，之后再補(bǔ)充）

需要注意計(jì)算機(jī)硬件是不判溢出的吃靠，僅保留2n位乘積，供軟件使用足淆，所以程序需進(jìn)行一些防溢出的處理巢块。

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

& 整數(shù)除法運(yùn)算中的截?cái)嗵幚?/h6>

對(duì)于整數(shù)除法外，因?yàn)樯痰慕^對(duì)值不可能比被除數(shù)的絕對(duì)值大掺涛，所以不會(huì)發(fā)生溢出庭敦，只有一種例外：帶符號(hào)整數(shù)的-2^n-1/-1 = 2^n-1，記得我們介紹補(bǔ)碼時(shí)曾說過補(bǔ)碼能增加表示一個(gè)最小負(fù)數(shù)嗎?不過它沒有對(duì)應(yīng)的正數(shù)薪缆，所以如果對(duì)它除-1秧廉，就發(fā)生溢出了。

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

整數(shù)除法是有可能不能整除的修陡，那就必須采用朝零舍入的截?cái)喾绞健?/p>

• 無符號(hào)數(shù)，帶符號(hào)正整數(shù)：移出的低位直接丟棄可霎。那就是說小數(shù)直接不要了魄鸦，朝0舍入。如：3.5 = 14/4 = 0000 1110 >> 2 = 0000 0011 = 3癣朗。
• 帶符號(hào)負(fù)整數(shù)：先加上偏移量 2^k-1号杏，然后再右移k位，低位截?cái)?/strong>斯棒。為什么要這么做呢盾致？我的理解是補(bǔ)碼的小數(shù)直接不要了，其實(shí)是朝無窮大方向舍入（why荣暮？之后再補(bǔ)充）庭惜，那么要移出k位，只要這k位不為0穗酥，我先加上k個(gè)1护赊，那么肯定會(huì)向前進(jìn)個(gè)位惠遏，因此最后的結(jié)果會(huì)再加1，變成朝零舍入骏啰。如：-3.5 = -14/4 = 1111 0010 >> 2 = 1111 1100 = -4节吮，這個(gè)和帶符號(hào)正整數(shù)出發(fā)得到的數(shù)值部分不一致。因此應(yīng)該先加上偏移量2²-1 = 3判耕，即(-14 + 2²-1)/4 = (1111 0010 + 0000 0011) >> 2 = 1111 1101 = -3透绩。

& 浮點(diǎn)數(shù)運(yùn)算

若兩個(gè)規(guī)格化浮點(diǎn)數(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 （假設(shè)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)

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

舉例說明如何計(jì)算浮點(diǎn)數(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) （對(duì)階，小階向大階看齊草丧，尾數(shù)右移）
= 0.001 x 2^-1 （尾數(shù)加減）
= 1.000 x 2^-4 （規(guī)格化狸臣，左規(guī)：左移一位，階碼減1昌执，判斷是否有階碼溢出）
= 0.0625 （是否需要考慮舍入烛亦；如果尾數(shù)是0，則需將階碼也置0懂拾，表示0）

在尾數(shù)右移的過程中此洲，可能會(huì)發(fā)生超出規(guī)定位數(shù)的情況，可以在尾數(shù)右邊放一個(gè)保護(hù)位和一個(gè)舍入位委粉，用來保護(hù)對(duì)階時(shí)右移的位或中間結(jié)果呜师，當(dāng)左規(guī)時(shí)被移入尾數(shù)中，作為舍入判斷的依據(jù)贾节。
舉個(gè)例子：（假設(shè)尾數(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 （舍入進(jìn)位） = 0.625 （結(jié)果比上面更精確）
IEEE 754舍入的方式主要有就近舍入（舍入為最近可表示的數(shù)）汁汗，正向舍入（+∞方向）博脑，負(fù)向舍入（-∞方向）谷浅，和朝0方向舍入（正數(shù)floor意系，負(fù)數(shù)ceil）

C語言中有float和double類型的浮點(diǎn)數(shù)悬襟，分別對(duì)應(yīng)IEEE 754單精讀浮點(diǎn)數(shù)格式和雙精度浮點(diǎn)數(shù)格式，那么在類型強(qiáng)制轉(zhuǎn)換的時(shí)候可能會(huì)有什么問題速警？（這就是為什么我們要學(xué)習(xí)數(shù)據(jù)在計(jì)算機(jī)中真正的存儲(chǔ)形式）

• 從int轉(zhuǎn)換為float時(shí)专筷，不會(huì)發(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ā)生截?cái)啵?/li>
• 從float轉(zhuǎn)換為int時(shí)忿墅，可能發(fā)生溢出扁藕，int沒有小數(shù)，數(shù)據(jù)可能會(huì)向0方向被截?cái)?/li>
• 從int轉(zhuǎn)換為double時(shí)疚脐，能保留精確值（double尾數(shù)為52+1位）
• 從double轉(zhuǎn)換為int時(shí)亿柑，可能發(fā)生溢出，int沒有小數(shù)棍弄，數(shù)據(jù)可能會(huì)向0方向被截?cái)?/li>
• 從float轉(zhuǎn)換位double時(shí)望薄，能保留精確值（double有效位數(shù)更多）
• 從double轉(zhuǎn)換為float時(shí)疟游，可能發(fā)生溢出，也可能有數(shù)據(jù)被舍入（有效尾數(shù)變少）

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