# 第?14?章?計算機中數的表示 **目錄** + [1\. 為什么計算機用二進制計數](ch14s01.html) + [2\. 不同進制之間的換算](ch14s02.html) + [3\. 整數的加減運算](ch14s03.html) + [3.1\. Sign and Magnitude表示法](ch14s03.html#id2753623) + [3.2\. 1's Complement表示法](ch14s03.html#id2753761) + [3.3\. 2's Complement表示法](ch14s03.html#id2753996) + [3.4\. 有符號數和無符號數](ch14s03.html#id2754091) + [4\. 浮點數](ch14s04.html) ## 1.?為什么計算機用二進制計數 人類的計數方式通常是“逢十進一”，稱為十進制（Decimal），大概因為人有十個手指，所以十進制是最自然的計數方式，很多民族的語言文字中都有十個數字，而阿拉伯數字0~9是目前最廣泛采用的。 計算機是用數字電路搭成的，數字電路中只有1和0兩種狀態，或者可以說計算機只有兩個手指，所以對計算機來說二進制（Binary）是最自然的計數方式。根據“逢二進一”的原則，十進制的1、2、3、4分別對應二進制的1、10、11、100。二進制的一位數字稱為一個位（Bit），三個bit能夠表示的最大的二進制數是111，也就是十進制的7。不管用哪種計數方式，數的大小并沒有變，十進制的1+1等于2，二進制的1+1等于10，二進制的10和十進制的2大小是相等的。事實上，計算機采用如下的邏輯電路計算兩個bit的加法： **圖?14.1.?1-bit Full Adder**  圖的上半部分（出自Wikipedia）的電路稱為一位全加器（1-bit Full Adder），圖的下半部分是一些邏輯電路符號的圖例。我們首先解釋這些圖例，邏輯電路由門電路（Gate）和導線（Wire）組成，同一條導線上在某一時刻的電壓值只能是高和低兩種狀態之一，分別用0和1表示。如果兩條導線短接在一起則它們的電壓值相同，在接點處畫一個黑點，如果接點處沒有畫黑點則表示這兩條線并沒有短接在一起，只是在畫圖時無法避免交叉。導線的電壓值進入門電路的輸入端，經過邏輯運算后在門電路的輸出端輸出運算結果的電壓值，任何復雜的加減乘除運算都可以分解成簡單的邏輯運算。AND、OR和NOT運算在[第?3?節 “布爾代數”](ch04s03.html#cond.bool)中講過了，這三種邏輯運算分別用與門、或門和反相器（Inverter）實現。另外幾種邏輯運算在這里補充一下。異或（XOR，eXclusive OR）運算的真值表如下： **表?14.1.?XOR的真值表** | A | B | A XOR B | | --- | --- | --- | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | 用一句話概括就是：兩個操作數相同則結果為0，兩個操作數不同則結果為1。與非（NAND）和或非（NOR）運算就是在與、或運算的基礎上取反： **表?14.2.?NAND的真值表** | A | B | A NAND B | | --- | --- | --- | | 0 | 0 | 1 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | **表?14.3.?NOR的真值表** | A | B | A NOR B | | --- | --- | --- | | 0 | 0 | 1 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 0 | 如果把與門、或門和反相器組合來實現NAND和NOR運算，則電路過于復雜了，因此邏輯電路中通常有專用的與非門和或非門。現在我們看看上圖中的AND、OR、XOR是怎么實現兩個bit的加法的。A、B是兩個加數，C_in是低位傳上來的進位（Carry），相當于三個加數求和，三個加數都是0則結果為0，三個加數都是1則結果為11，即輸出位S是1，產生的進位C_out也是1。下面根據加法的規則用真值表列出所有可能的情況： **表?14.4.?1-bit Full Adder的真值表** | A | B | C_in | C_out | S | | --- | --- | --- | --- | --- | | 0 | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 0 | 1 | | 0 | 1 | 0 | 0 | 1 | | 0 | 1 | 1 | 1 | 0 | | 1 | 0 | 0 | 0 | 1 | | 1 | 0 | 1 | 1 | 0 | | 1 | 1 | 0 | 1 | 0 | | 1 | 1 | 1 | 1 | 1 | 請讀者對照電路圖驗證一下真值表是否正確。如果把很多個一位全加器串接起來，就成了多位加法器，如下圖所示（該圖出自Wikipedia）： **圖?14.2.?4-bit Ripple Carry Adder**  圖中的一位全加器用方框表示，上一級全加器的C_out連接到下一級全加器的C_in，讓進位像漣漪一樣一級一級傳開，所以叫做Ripple Carry Adder，這樣就可以把兩個4 bit二進制數A₃A₂A₁A₀和B₃B₂B₁B₀加起來了。在這里介紹Ripple Carry Adder只是為了讓讀者理解計算機是如何通過邏輯運算來做算術運算的，實際上這種加法器效率很低，只能加完了一位再加下一位，更實用、更復雜的加法器可以多個位一起計算，有興趣的讀者可參考[[數字邏輯基礎]](bi01.html#bibli.vhdl "Fundamentals of Digital Logic with VHDL Design")。 ## 2.?不同進制之間的換算 在十進制中，個位的1代表10⁰=1，十位的1代表10¹=10，百位的1代表10²=100，所以 123=1×10²+2×10¹+3×10⁰ 同樣道理，在二進制中，個位的1代表2⁰=1，十位的1代表2¹=2，百位的1代表2²=4，所以 (A₃A₂A₁A₀)₂=A₃×2³+A₂×2²+A₁×2¹+A₀×2⁰ 如果二進制和十進制數出現在同一個等式中，為了區別我們用(A₃A₂A₁A₀)₂這種形式表示A₃A₂A₁A₀是二進制數，每個數字只能是0或1，其它沒有套括號加下標的數仍表示十進制數。對于(A₃A₂A₁A₀)₂這樣一個二進制數，最左邊的A₃位稱為最高位（MSB，Most Significant Bit），最右邊的A₀位稱為最低位（LSB，Least Significant Bit）。以后我們遵循這樣的慣例：_LSB稱為第0位而不是第1位，所以如果一個數是32位的，則MSB是第31位_。上式就是從二進制到十進制的換算公式。作為練習，請讀者算一下(1011)₂和(1111)₂換算成十進制分別是多少。 下面來看十進制怎么換算成二進制。我們知道 13=1×2³+1×2²+0×2¹+1×2⁰ 所以13換算成二進制應該是(1101)₂。問題是怎么把13分解成等號右邊的形式呢？注意到等號右邊可以寫成 13=((((0×2+1₃)×2+1₂)×2+0₁)×2+1₀ 我們將13反復除以2取余數就可以提取出上式中的1101四個數字，為了讓讀者更容易看清楚是哪個1和哪個0，上式和下式中對應的數字都加了下標： 13÷2=6...1₀ 6÷2=3...0₁ 3÷2=1...1₂ 1÷2=0...1₃ 把這四步得到的余數按相反的順序排列就是13的二進制表示，因此這種方法稱為除二反序取余法。 計算機用二進制表示數，程序員也必須習慣使用二進制，但二進制寫起來太啰嗦了，所以通常將二進制數分成每三位一組或者每四位一組，每組用一個數字表示。比如把(10110010)₂從最低位開始每三位分成一組，10、110、010，然后把每組寫成一個十進制數字，就是(262)₈，這樣每一位數字的取值范圍是0~7，逢八進一，稱為八進制（Octal）。類似地，把(10110010)₂分成每四位一組，1011、0010，然后把每組寫成一個數字，這個數的低位是2，高位已經大于9了，我們規定用字母A~F表示10~15，這個數可以寫成(B2)₁₆，每一位數字的取值范圍是0~F，逢十六進一，稱為十六進制（Hexadecimal）。所以，八進制和十六進制是程序員為了書寫二進制方便而發明的簡便寫法，好比草書和正楷的關系一樣。 ### 習題 1、二進制小數可以這樣定義： (0.A₁A₂A₃...)₂=A₁×2^-1+A₂×2^-2+A₃×2^-3+... 這個定義同時也是從二進制小數到十進制小數的換算公式。從本節講的十進制轉二進制的推導過程出發類比一下，十進制小數換算成二進制小數應該怎么算？ 2、再類比一下，八進制（或十六進制）與十進制之間如何相互換算？ ## 3.?整數的加減運算 我們已經了解了計算機中正整數如何表示，加法如何計算，那么負數如何表示，減法又如何計算呢？本節討論這些問題。為了書寫方便，本節舉的例子都用8個bit表示一個數，實際計算機做整數加減運算的操作數可以是8位、16位、32位甚至64位的。 ### 3.1.?Sign and Magnitude表示法 要用8個bit表示正數和負數，一種簡單的想法是把最高位規定為符號位（Sign Bit），0表示正1表示負，剩下的7位表示絕對值的大小，這稱為Sign and Magnitude表示法。例如-1表示成10000001，+1表示成00000001。這樣用8個bit表示整數的取值范圍是-2⁷-1~2⁷-1，即-127~127。 采用這種表示法，計算機做加法運算需要處理以下邏輯： 1. 如果兩數符號位相同，就把它們的低7位相加，符號位不變。如果低7位相加時在最高位產生進位，說明結果的絕對值大于127，超出7位所能表示的數值范圍，這稱為溢出（Overflow）^{[[24](#ftn.id2753684)]}，這時通常把計算機中的一個標志位置1表示當前運算產生了溢出。 2. 如果兩數符號位不同，首先比較它們的低7位誰大，然后用大數減小數，結果的符號位和大數相同。 那么減法如何計算呢？由于我們規定了負數的表示，可以把減法轉換成加法來計算，要計算a-b，可以先把b變號然后和a相加，相當于計算a+(-b)。但如果兩個加數的符號位不同就要用大數的絕對值減小數的絕對值，這一步減法計算仍然是免不了的。我們知道加法要進位，減法要借位，計算過程是不同的，所以除了要有[第?1?節 “為什么計算機用二進制計數”](ch14s01.html#number.binary)提到的加法器電路之外，還要另外有一套減法器電路。 如果采用Sign and Magnitude表示法，計算機做加減運算需要處理很多邏輯：比較符號位，比較絕對值，加法改減法，減法改加法，小數減大數改成大數減小數……這是非常低效率的。還有一個缺點是0的表示不唯一，既可以表示成10000000也可以表示成00000000，這進一步增加了邏輯的復雜性，所以我們迫切需要重新設計整數的表示方法使計算過程更簡單。 ### 3.2.?1's Complement表示法 本節介紹一種二進制補碼表示法，為了便于理解，我們先看一個十進制的例子： 167-52=167+(-52)=167+(999-52)-1000+1=167+947-1000+1=1114-1000+1=114+1=115 167-52?→?減法轉換成加法?167+(-52)?→?負數取9的補碼表示?167+947?→?114進1?→?高位進的1加到低位上去，結果為115 在這個例子中我們用三位十進制數字表示正數和負數，具體規定如下： **表?14.5.?9's Complement表示法** | 數值 | 補碼表示 | | --- | --- | | -499 | 500 | | -498 | 501 | | ... | ... | | -1 | 998 | | 0 | 999 | | 0 | 0 | | 1 | 1 | | ... | ... | | 498 | 498 | | 499 | 499 | 首先-52要用999-52表示，就是947，這稱為取9的補碼（9's Complement）；然后把167和947相加，得到114進1；再把高位進的1加到低位上去，得115，本來應該加1000，結果加了1，少加了999，正好把先前取9的補碼多加的999抵消掉了。我們本來要做167-52的減法運算，結果變成做999-52的減法運算，后者顯然要容易一些，因為沒有借位。這種補碼表示法的計算規則用一句話概括就是：負數用9的補碼表示，減法轉換成加法，計算結果的最高位如果有進位則要加回到最低位上去。要驗證這條規則得考慮四種情況： 1. 兩個正數，相加得正 2. 一正一負，相加得正 3. 一正一負，相加得負 4. 兩個負數，相加得負 我們舉的例子驗證了第二種情況，另外三種情況請讀者自己驗證，暫時不考慮溢出的問題，稍后會講到如何判定溢出。 上述規則也適用于二進制：_負數用1的補碼（1's Complement）表示，減法轉換成加法，計算結果的最高位如果有進位則要加回到最低位上去_。取1的補碼更簡單，連減法都不用做，因為1-1=0，1-0=1，取1的補碼就是把每個bit取反，所以1的補碼也稱為反碼。比如： 00001000-00000100?→?00001000+(-00000100)?→?00001000+11111011?→?00000011進1?→?高位進的1加到低位上去，結果為00000100 1's Complement表示法相對于Sign and Magnitude表示法的優勢是非常明顯的：不需要把符號和絕對值分開考慮，正數和負數的加法都一樣算，計算邏輯更簡單，甚至連減法器電路都省了，只要有一套加法器電路，再有一套把每個bit取反的電路，就可以做加法和減法運算。如果8個bit采用1's Complement表示法，負數的取值范圍是從10000000到11111111（-127~0），正數是從00000000到01111111（0~127），仍然可以根據最高位判斷一個數是正是負。美中不足的是0的表示仍然不唯一，既可以表示成11111111也可以表示成00000000，為了解決這最后一個問題，我們引入2's Complement表示法。 ### 3.3.?2's Complement表示法 2's Complement表示法規定：正數不變，負數先取反碼再加1。如果8個bit采用2's Complement表示法，負數的取值范圍是從10000000到11111111（-128~-1），正數是從00000000到01111111（0~127），也可以根據最高位判斷一個數是正是負，并且0的表示是唯一的，目前絕大多數計算機都采用這種表示法。為什么稱為“2的補碼”呢？因為對一位二進制數b取補碼就是1-b+1=10-b，相當于從2里面減去b。類似地，要表示-4需要對00000100取補碼，11111111-00000100+1=100000000-00000100，相當于從2⁸里面減去4。2's Complement表示法的計算規則有些不同：減法轉換成加法，忽略計算結果最高位的進位，不必加回到最低位上去。請讀者自己驗證上一節提到的四種情況下這條規則都能算出正確結果。 8個bit采用2's Complement表示法的取值范圍是-128~127，如果計算結果超出這個范圍就會產生溢出，例如： **圖?14.3.?有符號數加法溢出**  如何判斷產生了溢出呢？我們還是分四種情況討論：如果兩個正數相加溢出，結果一定是負數；如果兩個負數相加溢出，結果一定是正數；一正一負相加，無論結果是正是負都不可能溢出。 **圖?14.4.?如何判定溢出**  從上圖可以得出結論：_在相加過程中最高位產生的進位和次高位產生的進位如果相同則沒有溢出，如果不同則表示有溢出_。邏輯電路的實現可以把這兩個進位連接到一個異或門，把異或門的輸出連接到溢出標志位。 ### 3.4.?有符號數和無符號數 前面幾節我們用8個bit表示正數和負數，講了三種表示法，每種表示法對應一種計算規則，這稱為有符號數（Signed Number）；如果8個bit全部表示正數則取值范圍是0~255，這稱為無符號數（Unsigned Number）。其實計算機做加法時并不區分操作數是有符號數還是無符號數，計算過程都一樣，比如上面的例子也可以看作無符號數的加法： **圖?14.5.?無符號數加法進位**  如果把這兩個操作數看作有符號數-126和-8相加，計算結果是錯的，因為產生了溢出；但如果看作無符號數130和248相加，計算結果是122進1，也就是122+256，這個結果是對的。計算機的加法器在做完計算之后，根據最高位產生的進位設置_進位標志_，同時根據最高位和次高位產生的進位的異或設置_溢出標志_。至于這個加法到底是有符號數加法還是無符號數加法則取決于程序怎么理解了，如果程序把它理解成有符號數加法，下一步就要檢查溢出標志，如果程序把它理解成無符號數加法，下一步就要檢查進位標志。通常計算機在做算術運算之后還可能設置另外兩個標志，如果計算結果的所有bit都是零則設置_零標志_，如果計算結果的最高位是1則設置_負數標志_，如果程序把計算結果理解成有符號數，也可以檢查負數標志判斷結果是正是負。 * * * ^{[[24](#id2753684)]} 有時候會進一步細分，把正整數溢出稱為上溢（Overflow），負整數溢出稱為下溢（Underflow），詳見`strtol(3)`。 ## 4.?浮點數 浮點數在計算機中的表示是基于科學計數法（Scientific Notation）的，我們知道32767這個數用科學計數法可以寫成3.2767×10⁴，3.2767稱為尾數（Mantissa，或者叫Significand），4稱為指數（Exponent）。浮點數在計算機中的表示與此類似，只不過基數（Radix）是2而不是10。下面我們用一個簡單的模型來解釋浮點數的基本概念。我們的模型由三部分組成：符號位、指數部分（表示2的多少次方）和尾數部分（小數點前面是0，尾數部分只表示小數點后的數字）。 **圖?14.6.?一種浮點數格式**  如果要表示17這個數，我們知道17=17.0×10⁰=0.17×10²，類似地，17=(10001)₂×2⁰=(0.10001)₂×2⁵，把尾數的有效數字全部移到小數點后，這樣就可以表示為： **圖?14.7.?17的浮點數表示**  如果我們要表示0.25就遇到新的困難了，因為0.25=1×2^-2=(0.1)₂×2^-1，而我們的模型中指數部分沒有規定如何表示負數。我們可以在指數部分規定一個符號位，然而更廣泛采用的辦法是使用偏移的指數（Biased Exponent）。規定一個偏移值，比如16，實際的指數要加上這個偏移值再填寫到指數部分，這樣比16大的就表示正指數，比16小的就表示負指數。要表示0.25，指數部分應該填16-1=15： **圖?14.8.?0.25的偏移指數浮點數表示**  現在還有一個問題需要解決：每個浮點數的表示都不唯一，例如17=(0.10001)₂×2⁵=(0.010001)₂×2⁶，這樣給計算機處理增加了復雜性。為了解決這個問題，我們規定尾數部分的最高位必須是1，也就是說尾數必須以0.1開頭，對指數做相應的調整，這稱為正規化（Normalize）。由于尾數部分的最高位必須是1，這個1就不必保存了，可以節省出一位來用于提高精度，我們說最高位的1是隱含的（Implied）。這樣17就只有一種表示方法了，指數部分應該是16+5=21=(10101)₂，尾數部分去掉最高位的1是0001： **圖?14.9.?17的正規化尾數浮點數表示**  兩個浮點數相加，首先把小數點對齊然后相加： **圖?14.10.?浮點數相加**  由于浮點數表示的精度有限，計算結果末尾的10兩位被舍去了。做浮點運算時要注意精度損失（Significance Loss）問題，有時計算順序不同也會導致不同的結果，比如11.0010000+0.00000001+0.00000001=11.0010000+0.00000001=11.0010000，后面加的兩個很小的數全被舍去了，沒有對計算結果產生任何影響，但如果調一下計算順序它們就能影響到計算結果了，0.00000001+0.00000001+11.0010000=0.00000010+11.0010000=11.0010001。再比如128.25=(10000000.01)₂，需要10個有效位，而我們的模型中尾數部分是8位，算上隱含的最高位1一共有9個有效位，那么128.25的浮點數表示只能舍去末尾的1，表示成(10000000.0)₂，其實跟128相等了。在[第?2?節 “if/else語句”](ch04s02.html#cond.ifelse)講過浮點數不能做精確比較，現在讀者應該知道為什么不能精確比較了。 整數運算會產生溢出，浮點運算也會產生溢出，浮點運算的溢出也分上溢和下溢兩種，但和整數運算的定義不同。假設整數采用8位2's Complement表示法，取值范圍是-128~127，如果計算結果是-130則稱為下溢，計算結果是130則稱為上溢。假設按本節介紹的浮點數表示法，取值范圍是-(0.111111111)₂×2¹⁵~(0.111111111)₂×2¹⁵，如果計算結果超出這個范圍則稱為上溢；如果計算結果未超出這個范圍但絕對值太小了，在-(0.1)₂×2^-16~(0.1)₂×2^-16之間，那么也同樣無法表示，稱為下溢。 浮點數是一個相當復雜的話題，不同平臺的浮點數表示和浮點運算也有較大差異，本節只是通過這個簡單的模型介紹一些基本概念而不深入討論，理解了這些基本概念有助于你理解浮點數標準，目前業界廣泛采用的符點數標準是由IEEE（Institute of Electrical and Electronics Engineers）制定的IEEE 754。 最后討論一個細節問題。我們知道，定義全局變量時如果沒有Initializer就用0初始化，定義數組時如果Initializer中提供的元素不夠那么剩下的元素也用0初始化。例如： ``` int i; double d; double a[10] = { 1.0 }; ``` “用0初始化”的意思是變量`i`、變量`d`和數組元素`a[1]~a[9]`的所有字節都用0填充，或者說所有bit都是0。無論是用Sign and Magnitude表示法、1's Complement表示法還是2's Complement表示法，一個整數的所有bit是0都表示0值，但一個浮點數的所有bit是0一定表示0值嗎？嚴格來說不一定，某種平臺可能會規定一個浮點數的所有bit是0并不表示0值，但[[C99 Rationale]](bi01.html#bibli.rationale "Rationale for International Standard － Programming Languages － C")第6.7.8節的條款25提到：As far as the committee knows, all machines treat all bits zero as a representation of floating-point zero. But, all bits zero might not be the canonical representation of zero. 因此在絕大多數平臺上，一個浮點數的所有bit是0就表示0值。