目錄二進制編碼理解二進制的“逢二進一”字符串的表示，從編碼到數(shù)字理解電路電報繼電器加法器異或門和半加器全加器總結(jié)乘法器順序乘法的實現(xiàn)過程并行加速方法電路并行浮點數(shù)和定點數(shù)浮點數(shù)的不精確性定點數(shù)的表示浮點數(shù)的表示浮點數(shù)的二進制轉(zhuǎn)化浮點數(shù)的加法和精度損失Kahan Summation 算法總結(jié)

二進制編碼

理解二進制的“逢二進一”

二進制和我們平時用的十進制，其實并沒有什么本質(zhì)區(qū)別，只是平時我們是“逢十進一”，這里變成了“逢二進一”而已。每一位，相比于十進制下的 0～9 這十個數(shù)字，我們只能用 0 和 1 這兩個數(shù)字。

任何一個十進制的整數(shù)，都能通過二進制表示出來。把一個二進制數(shù)，對應到十進制，非常簡單，就是把從右到左的第 N 位，乘上一個 2 的 N 次方，然后加起來，就變成了一個十進制數(shù)。當然，既然二進制是一個面向程序員的“語言”，這個從右到左的位置，自然是從 0 開始的。

比如 0011 這個二進制數(shù)，對應的十進制表示，就是

[0×2^3+0×2^2+1×2^1+1×2^0=3
]

，代表十進制的 3。

對應地，如果我們想要把一個十進制的數(shù)，轉(zhuǎn)化成二進制，使用短除法就可以了。也就是，把十進制數(shù)除以 2 的余數(shù)，作為最右邊的一位。然后用商繼續(xù)除以 2，把對應的余數(shù)緊靠著剛才余數(shù)的右側(cè)，這樣遞歸迭代，直到商為 0 就可以了。

比如，我們想把 13 這個十進制數(shù)，用短除法轉(zhuǎn)化成二進制，需要經(jīng)歷以下幾個步驟：

因此，對應的二進制數(shù)，就是 1101。

剛才我們舉的例子都是正數(shù)，對于負數(shù)來說，情況也是一樣的嗎？我們可以把一個數(shù)最左側(cè)的一位，當成是對應的正負號，比如 0 為正數(shù)，1 為負數(shù)，這樣來進行標記。

這樣，一個 4 位的二進制數(shù)， 0011 就表示為 +3。而 1011 最左側(cè)的第一位是 1，所以它就表示 -3。這個其實就是整數(shù)的原碼表示法。原碼表示法有一個很直觀的缺點就是，0 可以用兩個不同的編碼來表示，1000 代表 0， 0000 也代表 0。習慣萬事一一對應的程序員看到這種情況，必然會被“逼死”。

于是，我們就有了另一種表示方法。我們?nèi)匀煌ㄟ^最左側(cè)第一位的 0 和 1，來判斷這個數(shù)的正負。但是，我們不再把這一位當成單獨的符號位，在剩下幾位計算出的十進制前加上正負號，而是在計算整個二進制值的時候，在左側(cè)最高位前面加個負號。

比如，一個 4 位的二進制補碼數(shù)值 1011，轉(zhuǎn)換成十進制，就是

[?1×2^3+0×2^2+1×2^1+1×2^0
=?5
]

如果最高位是 1，這個數(shù)必然是負數(shù)；最高位是 0，必然是正數(shù)。并且，只有 0000 表示 0，1000 在這樣的情況下表示 -8。一個 4 位的二進制數(shù)，可以表示從 -8 到 7 這 16 個整數(shù)，不會白白浪費一位。

當然更重要的一點是，用補碼來表示負數(shù)，使得我們的整數(shù)相加變得很容易，不需要做任何特殊處理，只是把它當成普通的二進制相加，就能得到正確的結(jié)果。

我們簡單一點，拿一個 4 位的整數(shù)來算一下，比如 -5 + 1 = -4，-5 + 6 = 1。我們各自把它們轉(zhuǎn)換成二進制來看一看。如果它們和無符號的二進制整數(shù)的加法用的是同樣的計算方式，這也就意味著它們是同樣的電路。

字符串的表示，從編碼到數(shù)字

不僅數(shù)值可以用二進制表示，字符乃至更多的信息都能用二進制表示。最典型的例子就是字符串（Character String）。最早計算機只需要使用英文字符，加上數(shù)字和一些特殊符號，然后用 8 位的二進制，就能表示我們?nèi)粘Ｐ枰乃凶址?，這個就是我們常常說的ASCII 碼（American Standard Code for Information Interchange，美國信息交換標準代碼）。

ASCII 碼就好比一個字典，用 8 位二進制中的 128 個不同的數(shù)，映射到 128 個不同的字符里。比如，小寫字母 a 在 ASCII 里面，就是第 97 個，也就是二進制的 0110 0001，對應的十六進制表示就是 61。而大寫字母 A，就是第 65 個，也就是二進制的 0100 0001，對應的十六進制表示就是 41。

在 ASCII 碼里面，數(shù)字 9 不再像整數(shù)表示法里一樣，用 0000 1001 來表示，而是用 0011 1001 來表示。字符串 15 也不是用 0000 1111 這 8 位來表示，而是變成兩個字符 1 和 5 連續(xù)放在一起，也就是 0011 0001 和 0011 0101，需要用兩個 8 位來表示。

我們可以看到，最大的 32 位整數(shù)，就是 2147483647。如果用整數(shù)表示法，只需要 32 位就能表示了。但是如果用字符串來表示，一共有 10 個字符，每個字符用 8 位的話，需要整整 80 位。比起整數(shù)表示法，要多占很多空間。

這也是為什么，很多時候我們在存儲數(shù)據(jù)的時候，要采用二進制序列化這樣的方式，而不是簡單地把數(shù)據(jù)通過 CSV 或者 JSON，這樣的文本格式存儲來進行序列化。不管是整數(shù)也好，浮點數(shù)也好，采用二進制序列化會比存儲文本省下不少空間。

ASCII 碼只表示了 128 個字符，一開始倒也堪用，畢竟計算機是在美國發(fā)明的。然而隨著越來越多的不同國家的人都用上了計算機，想要表示譬如中文這樣的文字，128 個字符顯然是不太夠用的。于是，計算機工程師們開始各顯神通，給自己國家的語言創(chuàng)建了對應的字符集（Charset）和字符編碼（Character Encoding）。

字符集，表示的可以是字符的一個集合。比如“中文”就是一個字符集，不過這樣描述一個字符集并不準確。想要更精確一點，我們可以說，“第一版《新華字典》里面出現(xiàn)的所有漢字”，這是一個字符集。這樣，我們才能明確知道，一個字符在不在這個集合里面。比如，我們?nèi)粘Ｕf的 Unicode，其實就是一個字符集，包含了 150 種語言的 14 萬個不同的字符。

而字符編碼則是對于字符集里的這些字符，怎么一一用二進制表示出來的一個字典。我們上面說的 Unicode，就可以用 UTF-8、UTF-16，乃至 UTF-32 來進行編碼，存儲成二進制。所以，有了 Unicode，其實我們可以用不止 UTF-8 一種編碼形式，我們也可以自己發(fā)明一套 GT-32 編碼，比如就叫作 Geek Time 32 好了。只要別人知道這套編碼規(guī)則，就可以正常傳輸、顯示這段代碼。

同樣的文本，采用不同的編碼存儲下來。如果另外一個程序，用一種不同的編碼方式來進行解碼和展示，就會出現(xiàn)亂碼。這就好像兩個軍隊用密語通信，如果用錯了密碼本，那看到的消息就會不知所云。在中文世界里，最典型的就是“手持兩把錕斤拷，口中疾呼燙燙燙”的典故。

既然今天要徹底搞清楚編碼知識，我們就來弄清楚“錕斤拷”和“燙燙燙”的來龍去脈。

首先，“錕斤拷”的來源是這樣的。如果我們想要用 Unicode 編碼記錄一些文本，特別是一些遺留的老字符集內(nèi)的文本，但是這些字符在 Unicode 中可能并不存在。于是，Unicode 會統(tǒng)一把這些字符記錄為 U+FFFD 這個編碼。

如果用 UTF-8 的格式存儲下來，就是xefxbfxbd。如果連續(xù)兩個這樣的字符放在一起，xefxbfxbdxefxbfxbd，這個時候，如果程序把這個字符，用 GB2312 的方式進行 decode，就會變成“錕斤拷”。這就好比我們用 GB2312 這本密碼本，去解密別人用 UTF-8 加密的信息，自然沒辦法讀出有用的信息。

而“燙燙燙”，則是因為如果你用了 Visual Studio 的調(diào)試器，默認使用 MBCS 字符集?！盃C”在里面是由 0xCCCC 來表示的，而 0xCC 又恰好是未初始化的內(nèi)存的賦值。于是，在讀到?jīng)]有賦值的內(nèi)存地址或者變量的時候，電腦就開始大叫“燙燙燙”了。

了解了這些原理，相信你未來在遇到中文的編碼問題的時候，可以做到“手中有糧，心中不慌”了。

理解電路

電報

電報機本質(zhì)上就是一個“蜂鳴器 + 長長的電線 + 按鈕開關”。蜂鳴器裝在接收方手里，開關留在發(fā)送方手里。雙方用長長的電線連在一起。當按鈕開關按下的時候，電線的電路接通了，蜂鳴器就會響。短促地按下，就是一個短促的點信號；按的時間稍微長一些，就是一個稍長的劃信號。

繼電器

有了電報機，只要鋪設好電報線路，就可以傳輸我們需要的訊息了。但是這里面又出現(xiàn)了一個新的挑戰(zhàn)，就是隨著電線的線路越長，電線的電阻就越大。當電阻很大，而電壓不夠的時候，即使你按下開關，蜂鳴器也不會響。

你可能要說了，我們可以提高電壓或者用更粗的電線，使得電阻更小，這樣就可以讓整個線路鋪得更長一些。但是這個再長，也沒辦法從北京鋪設到上海吧。要想從北京把電報發(fā)到上海，我們還得想些別的辦法。

對于電報來說，電線太長了，使得線路接通也沒有辦法讓蜂鳴器響起來。那么，我們就不要一次鋪太長的線路，而把一小段距離當成一個線路，也和驛站建立一個小電報站。我們在小電報站里面安排一個電報員，他聽到上一個小電報站發(fā)來的信息，然后原樣輸入，發(fā)到下一個電報站去。這樣，我們的信號就可以一段段傳輸下去，而不會因為距離太長，導致電阻太大，沒有辦法成功傳輸信號。為了能夠?qū)崿F(xiàn)這樣接力傳輸信號，在電路里面，工程師們造了一個叫作繼電器（Relay）的設備。

事實上，這個過程中，我們需要在每一階段原樣傳輸信號，所以你可以想想，我們是不是可以設計一個設備來代替這個電報員？相比使用人工聽蜂鳴器的聲音，來重復輸入信號，利用電磁效應和磁鐵，來實現(xiàn)這個事情會更容易。

我們把原先用來輸出聲音的蜂鳴器，換成一段環(huán)形的螺旋線圈，讓電路封閉通上電。因為電磁效應，這段螺旋線圈會產(chǎn)生一個帶有磁性的電磁場。我們原本需要輸入的按鈕開關，就可以用一塊磁力稍弱的磁鐵把它設在“關”的狀態(tài)。這樣，按下上一個電報站的開關，螺旋線圈通電產(chǎn)生了磁場之后，磁力就會把開關“吸”下來，接通到下一個電報站的電路。

如果我們在中間所有小電報站都用這個“螺旋線圈 + 磁性開關”的方式，來替代蜂鳴器和普通開關，而只在電報的始發(fā)和終點用普通的開關和蜂鳴器，我們就有了一個拆成一段一段的電報線路，接力傳輸電報信號。這樣，我們就不需要中間安排人力來聽打電報內(nèi)容，也不需要解決因為線纜太長導致的電阻太大或者電壓不足的問題了。我們只要在終點站安排電報員，聽寫最終的電報內(nèi)容就可以了。這樣是不是比之前更省事了？

事實上，繼電器還有一個名字就叫作電驛，這個“驛”就是驛站的驛，可以說非常形象了。這個接力的策略不僅可以用在電報中，在通信類的科技產(chǎn)品中其實都可以用到。

比如說，你在家里用 WiFi，如果你的屋子比較大，可能某些房間的信號就不好。你可以選用支持“中繼”的 WiFi 路由器，在信號衰減的地方，增加一個 WiFi 設備，接收原來的 WiFi 信號，再重新從當前節(jié)點傳輸出去。這種中繼對應的英文名詞和繼電器是一樣的，也叫 Relay。

再比如說，我們現(xiàn)在互聯(lián)網(wǎng)使用的光纜，是用光信號來傳輸數(shù)據(jù)。隨著距離的增長、反射次數(shù)的增加，信號也會有所衰減，我們同樣要每隔一段距離，來增加一個用來重新放大信號的中繼。

有了繼電器之后，我們不僅有了一個能夠接力傳輸信號的方式，更重要的是，和輸入端通過開關的“開”和“關”來表示“1”和“0”一樣，我們在輸出端也能表示“1”和“0”了。

輸出端的作用，不僅僅是通過一個蜂鳴器或者燈泡，提供一個供人觀察的輸出信號，通過“螺旋線圈 + 磁性開關”，使得我們有“開”和“關”這兩種狀態(tài)，這個“開”和“關”表示的“1”和“0”，還可以作為后續(xù)線路的輸入信號，讓我們開始可以通過最簡單的電路，來組合形成我們需要的邏輯。

通過這些線圈和開關，我們也可以很容易地創(chuàng)建出 “與（AND）”“或（OR）”“非（NOT）”這樣的邏輯。我們在輸入端的電路上，提供串聯(lián)的兩個開關，只有兩個開關都打開，電路才接通，輸出的開關也才能接通，這其實就是模擬了計算機里面的“與”操作。

我們在輸入端的電路，提供兩條獨立的線路到輸出端，兩條線路上各有一個開關，那么任何一個開關打開了，到輸出端的電路都是接通的，這其實就是模擬了計算機中的“或”操作。

當我們把輸出端的“螺旋線圈 + 磁性開關”的組合，從默認關掉，只有通電有了磁場之后打開，換成默認是打開通電的，只有通電之后才關閉，我們就得到了一個計算機中的“非”操作。輸出端開和關正好和輸入端相反。這個在數(shù)字電路中，也叫作反向器（Inverter）。

與、或、非的電路都非常簡單，要想做稍微復雜一點的工作，我們需要很多電路的組合。不過，這也彰顯了現(xiàn)代計算機體系中一個重要的思想，就是通過分層和組合，逐步搭建起更加強大的功能。

回到我們前面看的電報機原型，雖然一個按鈕開關的電報機很“容易”操作，但是卻不“方便”操作。因為電報員要熟記每一個字母對應的摩爾斯電碼，并且需要快速按鍵來進行輸入。一旦輸錯很難糾正。但是，因為電路之間可以通過與、或、非組合完成更復雜的功能，我們完全可以設計一個和打字機一樣的電報機，每按下一個字母按鈕，就會接通一部分電路，然后把這個字母的摩爾斯電碼輸出出去。

雖然在電報機時代，我們沒有這么做，但是在計算機時代，我們其實就是這樣做的。我們不再是給計算機“0”和“1”，而是通過千萬個晶體管組合在一起，最終使得我們可以用“高級語言”，指揮計算機去干什么。

加法器

這些基本的門電路，是我們計算機硬件端的最基本的“積木”

異或門和半加器

我們看到的基礎門電路，輸入都是兩個單獨的 bit，輸出是一個單獨的 bit。如果我們要對 2 個 8 位（bit）的數(shù)，計算與、或、非這樣的簡單邏輯運算，其實很容易。只要連續(xù)擺放 8 個開關，來代表一個 8 位數(shù)。這樣的兩組開關，從左到右，上下單個的位開關之間，都統(tǒng)一用“與門”或者“或門”連起來，就是兩個 8 位數(shù)的 AND 或者 OR 的運算了。

比起 AND 或者 OR 這樣的電路外，要想實現(xiàn)整數(shù)的加法，就需要組建稍微復雜一點兒的電路了。

我們先回歸一個最簡單的 8 位的無符號整數(shù)的加法。這里的“無符號”，表示我們并不需要使用補碼來表示負數(shù)。無論高位是“0”還是“1”，這個整數(shù)都是一個正數(shù)。

我們很直觀就可以想到，要表示一個 8 位數(shù)的整數(shù)，簡單地用 8 個 bit，也就是 8 個像上一講的電路開關就好了。那 2 個 8 位整數(shù)的加法，就是 2 排 8 個開關。加法得到的結(jié)果也是一個 8 位的整數(shù)，所以又需要 1 排 8 位的開關。要想實現(xiàn)加法，我們就要看一下，通過什么樣的門電路，能夠連接起加數(shù)和被加數(shù)，得到最后期望的和。

要做到這一點，我們先來看看，我們?nèi)嗽谟嬎慵臃ǖ臅r候一般會怎么操作。二進制的加法和十進制沒什么區(qū)別，所以我們一樣可以用列豎式來計算。我們?nèi)匀皇菑淖蟮接?，一位一位進行計算，只是把從逢 10 進 1 變成逢 2 進 1。

你會發(fā)現(xiàn)，其實計算一位數(shù)的加法很簡單。我們先就看最簡單的個位數(shù)。輸入一共是 4 種組合，00、01、10、11。得到的結(jié)果，也不復雜。

一方面，我們需要知道，加法計算之后的個位是什么，在輸入的兩位是 00 和 11 的情況下，對應的輸出都應該是 0；在輸入的兩位是 10 和 01 的情況下，輸出都是 1。結(jié)果你會發(fā)現(xiàn)，這個輸入和輸出的對應關系，其實就是“異或門（XOR）”。

講與、或、非門的時候，我們很容易就能和程序里面的“AND（通常是 & 符號）”“ OR（通常是 | 符號）”和“ NOT（通常是 ! 符號）”對應起來。可能你沒有想過，為什么我們會需要“異或（XOR）”，這樣一個在邏輯運算里面沒有出現(xiàn)的形式，作為一個基本電路。其實，異或門就是一個最簡單的整數(shù)加法，所需要使用的基本門電路。

算完個位的輸出還不算完，輸入的兩位都是 11 的時候，我們還需要向更左側(cè)的一位進行進位。那這個就對應一個與門，也就是有且只有在加數(shù)和被加數(shù)都是 1 的時候，我們的進位才會是 1。

所以，通過一個異或門計算出個位，通過一個與門計算出是否進位，我們就通過電路算出了一個一位數(shù)的加法。于是，我們把兩個門電路打包，給它取一個名字，就叫作半加器（Half Adder）。

全加器

半加器可以解決個位的加法問題，但是如果放到二位上來說，就不夠用了。我們這里的豎式是個二進制的加法，所以如果從右往左數(shù)，第二列不是十位，我稱之為“二位”。對應的再往左，就應該分別是四位、八位。

二位用一個半加器不能計算完成的原因也很簡單。因為二位除了一個加數(shù)和被加數(shù)之外，還需要加上來自個位的進位信號，一共需要三個數(shù)進行相加，才能得到結(jié)果。但是我們目前用到的，無論是最簡單的門電路，還是用兩個門電路組合而成的半加器，輸入都只能是兩個 bit，也就是兩個開關。那我們該怎么辦呢？

實際上，解決方案也并不復雜。我們用兩個半加器和一個或門，就能組合成一個全加器。第一個半加器，我們用和個位的加法一樣的方式，得到是否進位 X 和對應的二個數(shù)加和后的結(jié)果 Y，這樣兩個輸出。然后，我們把這個加和后的結(jié)果 Y，和個位數(shù)相加后輸出的進位信息 U，再連接到一個半加器上，就會再拿到一個是否進位的信號 V 和對應的加和后的結(jié)果 W。

這個 W 就是我們在二位上留下的結(jié)果。我們把兩個半加器的進位輸出，作為一個或門的輸入連接起來，只要兩次加法中任何一次需要進位，那么在二位上，我們就會向左側(cè)的四位進一位。因為一共只有三個 bit 相加，即使 3 個 bit 都是 1，也最多會進一位。

這樣，通過兩個半加器和一個或門，我們就得到了一個，能夠接受進位信號、加數(shù)和被加數(shù)，這樣三個數(shù)組成的加法。這就是我們需要的全加器。

有了全加器，我們要進行對應的兩個 8 bit 數(shù)的加法就很容易了。我們只要把 8 個全加器串聯(lián)起來就好了。個位的全加器的進位信號作為二位全加器的輸入信號，二位全加器的進位信號再作為四位的全加器的進位信號。這樣一層層串接八層，我們就得到了一個支持 8 位數(shù)加法的算術單元。如果要擴展到 16 位、32 位，乃至 64 位，都只需要多串聯(lián)幾個輸入位和全加器就好了。

唯一需要注意的是，對于這個全加器，在個位，我們只需要用一個半加器，或者讓全加器的進位輸入始終是 0。因為個位沒有來自更右側(cè)的進位。而最左側(cè)的一位輸出的進位信號，表示的并不是再進一位，而是表示我們的加法是否溢出了。

看到全加器的電路設計，相信你應該明白，在整個加法器的結(jié)果中，我們其實有一個電路的信號，會標識出加法的結(jié)果是否溢出。我們可以把這個對應的信號，輸出給到硬件中其他標志位里，讓我們的計算機知道計算的結(jié)果是否溢出。而現(xiàn)代計算機也正是這樣做的。這就是為什么你在撰寫程序的時候，能夠知道你的計算結(jié)果是否溢出在硬件層面得到的支持。

總結(jié)

通過門電路來搭建算術計算的一個小功能，就好像搭樂高積木一樣。

我們用兩個門電路，搭出一個半加器，就好像我們拿兩塊樂高，疊在一起，變成一個長方形的樂高，這樣我們就有了一個新的積木組件，柱子。我們再用兩個柱子和一個長條的積木組合一下，就變成一個積木橋。然后幾個積木橋串接在一起，又成了積木樓梯。

當我們想要搭建一個摩天大樓，我們需要很多很多樓梯。但是這個時候，我們已經(jīng)不再關注最基礎的一節(jié)樓梯是怎么用一塊塊積木搭建起來的。這其實就是計算機中，無論軟件還是硬件中一個很重要的設計思想，分層。

從簡單到復雜，我們一層層搭出了擁有更強能力的功能組件。在上面的一層，我們只需要考慮怎么用下一層的組件搭建出自己的功能，而不需要下沉到更低層的其他組件。就像你之前并沒有深入學習過計算機組成原理，一樣可以直接通過高級語言撰寫代碼，實現(xiàn)功能。

在硬件層面，我們通過門電路、半加器、全加器一層層搭出了加法器這樣的功能組件。我們把這些用來做算術邏輯計算的組件叫作 ALU，也就是算術邏輯單元。當進一步打造強大的 CPU 時，我們不會再去關注最細顆粒的門電路，只需要把門電路組合而成的 ALU，當成一個能夠完成基礎計算的黑盒子就可以了。

乘法器

十進制中的 13 乘以 9，計算的結(jié)果應該是 117。我們通過轉(zhuǎn)換成二進制，然后列豎式的辦法，來看看整個計算的過程是怎樣的。

順序乘法的實現(xiàn)過程

從列出豎式的過程中，你會發(fā)現(xiàn)，二進制的乘法有個很大的優(yōu)點，就是這個過程你不需要背九九乘法口訣表了。因為單個位置上，乘數(shù)只能是 0 或者 1，所以實際的乘法，就退化成了位移和加法。

在 13×9 這個例子里面，被乘數(shù) 13 表示成二進制是 1101，乘數(shù) 9 在二進制里面是 1001。最右邊的個位是 1，所以個位乘以被乘數(shù)，就是把被乘數(shù) 1101 復制下來。因為二位和四位都是 0，所以乘以被乘數(shù)都是 0，那么保留下來的都是 0000。乘數(shù)的八位是 1，我們?nèi)匀恍枰驯怀藬?shù) 1101 復制下來。不過這里和個位位置的單純復制有一點小小的差別，那就是要把復制好的結(jié)果向左側(cè)移三位，然后把四位單獨進行乘法加位移的結(jié)果，再加起來，我們就得到了最終的計算結(jié)果。

對應到我們之前講的數(shù)字電路和 ALU，你可以看到，最后一步的加法，我們可以用上一講的加法器來實現(xiàn)。乘法因為只有“0”和“1”兩種情況，所以可以做成輸入輸出都是 4 個開關，中間用 1 個開關，同時來控制這 8 個開關的方式，這就實現(xiàn)了二進制下的單位的乘法。

至于位移也不麻煩，我們只要不是直接連線，把正對著的開關之間進行接通，而是斜著錯開位置去接就好了。如果要左移一位，就錯開一位接線；如果要左移兩位，就錯開兩位接線。

這樣，你會發(fā)現(xiàn)，我們并不需要引入任何新的、更復雜的電路，仍然用最基礎的電路，只要用不同的接線方式，就能夠?qū)崿F(xiàn)一個“列豎式”的乘法。而且，因為二進制下，只有 0 和 1，也就是開關的開和閉這兩種情況，所以我們的計算機也不需要去“背誦”九九乘法口訣表，不需要單獨實現(xiàn)一個更復雜的電路，就能夠?qū)崿F(xiàn)乘法。

為了節(jié)約一點開關，也就是晶體管的數(shù)量。實際上，像 13×9 這樣兩個四位數(shù)的乘法，我們不需要把四次單位乘法的結(jié)果，用四組獨立的開關單獨都記錄下來，然后再把這四個數(shù)加起來。因為這樣做，需要很多組開關，如果我們計算一個 32 位的整數(shù)乘法，就要 32 組開關，太浪費晶體管了。如果我們順序地來計算，只需要一組開關就好了。

我們先拿乘數(shù)最右側(cè)的個位乘以被乘數(shù)，然后把結(jié)果寫入用來存放計算結(jié)果的開關里面，然后，把被乘數(shù)左移一位，把乘數(shù)右移一位，仍然用乘數(shù)去乘以被乘數(shù)，然后把結(jié)果加到剛才的結(jié)果上。反復重復這一步驟，直到不能再左移和右移位置。這樣，乘數(shù)和被乘數(shù)就像兩列相向而駛的列車，僅僅需要簡單的加法器、一個可以左移一位的電路和一個右移一位的電路，就能完成整個乘法。

你看這里畫的乘法器硬件結(jié)構示意圖。這里的控制測試，其實就是通過一個時鐘信號，來控制左移、右移以及重新計算乘法和加法的時機。我們還是以計算 13×9，也就是二進制的 1101×1001 來具體看。

這個計算方式雖然節(jié)約電路了，但是也有一個很大的缺點，那就是慢。

你應該很容易就能發(fā)現(xiàn)，在這個乘法器的實現(xiàn)過程里，我們其實就是把乘法展開，變成了“加法 + 位移”來實現(xiàn)。我們用的是 4 位數(shù)，所以要進行 4 組“位移 + 加法”的操作。而且這 4 組操作還不能同時進行。因為下一組的加法要依賴上一組的加法后的計算結(jié)果，下一組的位移也要依賴上一組的位移的結(jié)果。這樣，整個算法是“順序”的，每一組加法或者位移的運算都需要一定的時間。

所以，最終這個乘法的計算速度，其實和我們要計算的數(shù)的位數(shù)有關。比如，這里的 4 位，就需要 4 次加法。而我們的現(xiàn)代 CPU 常常要用 32 位或者是 64 位來表示整數(shù)，那么對應就需要 32 次或者 64 次加法。比起 4 位數(shù)，要多花上 8 倍乃至 16 倍的時間。

換個我們在算法和數(shù)據(jù)結(jié)構中的術語來說就是，這樣的一個順序乘法器硬件進行計算的時間復雜度是 O(N)。這里的 N，就是乘法的數(shù)里面的位數(shù)。

并行加速方法

那么，我們有沒有辦法，把時間復雜度上降下來呢？研究數(shù)據(jù)結(jié)構和算法的時候，我們總是希望能夠把 O(N) 的時間復雜度，降低到 O(logN)。辦法還真的有。和軟件開發(fā)里面改算法一樣，在涉及 CPU 和電路的時候，我們可以改電路。

32 位數(shù)雖然是 32 次加法，但是我們可以讓很多加法同時進行?；氐竭@一講開始，我們把位移和乘法的計算結(jié)果加到中間結(jié)果里的方法，32 位整數(shù)的乘法，其實就變成了 32 個整數(shù)相加。

前面順序乘法器硬件的實現(xiàn)辦法，就好像體育比賽里面的單敗淘汰賽。只有一個擂臺會存下最新的計算結(jié)果。每一場新的比賽就來一個新的選手，實現(xiàn)一次加法，實現(xiàn)完了剩下的還是原來那個守擂的，直到其余 31 個選手都上來比過一場。如果一場比賽需要一天，那么一共要比 31 場，也就是 31 天。

加速的辦法，就是把比賽變成像世界杯足球賽那樣的淘汰賽，32 個球隊捉對廝殺，同時開賽。這樣一天一下子就淘汰了 16 支隊，也就是說，32 個數(shù)兩兩相加后，你可以得到 16 個結(jié)果。后面的比賽也是一樣同時開賽捉對廝殺。只需要 5 天，也就是 O(log2N) 的時間，就能得到計算的結(jié)果。但是這種方式要求我們得有 16 個球場。因為在淘汰賽的第一輪，我們需要 16 場比賽同時進行。對應到我們 CPU 的硬件上，就是需要更多的晶體管開關，來放下中間計算結(jié)果。

電路并行

上面我們說的并行加速的辦法，看起來還是有點兒笨。我們回頭來做一個抽象的思考。之所以我們的計算會慢，核心原因其實是“順序”計算，也就是說，要等前面的計算結(jié)果完成之后，我們才能得到后面的計算結(jié)果。

最典型的例子就是我們上一講講的加法器。每一個全加器，都要等待上一個全加器，把對應的進入輸入結(jié)果算出來，才能算下一位的輸出。位數(shù)越多，越往高位走，等待前面的步驟就越多，這個等待的時間有個專門的名詞，叫作門延遲（Gate Delay）。

每通過一個門電路，我們就要等待門電路的計算結(jié)果，就是一層的門電路延遲，我們一般給它取一個“T”作為符號。一個全加器，其實就已經(jīng)有了 3T 的延遲（進位需要經(jīng)過 3 個門電路）。而 4 位整數(shù)，最高位的計算需要等待前面三個全加器的進位結(jié)果，也就是要等 9T 的延遲。如果是 64 位整數(shù)，那就要變成 63×3=189T 的延遲。這可不是個小數(shù)字啊！

除了門延遲之外，還有一個問題就是時鐘頻率。在上面的順序乘法計算里面，如果我們想要用更少的電路，計算的中間結(jié)果需要保存在寄存器里面，然后等待下一個時鐘周期的到來，控制測試信號才能進行下一次移位和加法，這個延遲比上面的門延遲更可觀。

那么，我們有什么辦法可以解決這個問題呢？實際上，在我們進行加法的時候，如果相加的兩個數(shù)是確定的，那高位是否會進位其實也是確定的。對于我們?nèi)藖碚f，我們本身去做計算都是順序執(zhí)行的，所以要一步一步計算進位。但是，計算機是連結(jié)的各種線路。我們不用讓計算機模擬人腦的思考方式，來連結(jié)線路。

那怎么才能把線路連結(jié)得復雜一點，讓高位和低位的計算同時出結(jié)果呢？怎樣才能讓高位不需要等待低位的進位結(jié)果，而是把低位的所有輸入信號都放進來，直接計算出高位的計算結(jié)果和進位結(jié)果呢？

我們只要把進位部分的電路完全展開就好了。我們的半加器到全加器，再到加法器，都是用最基礎的門電路組合而成的。門電路的計算邏輯，可以像我們做數(shù)學里面的多項式乘法一樣完全展開。在展開之后呢，我們可以把原來需要較少的，但是有較多層前后計算依賴關系的門電路，展開成需要較多的，但是依賴關系更少的門電路。

這里畫了一個示意圖，展示了一下我們加法器。如果我們完全展開電路，高位的進位和計算結(jié)果，可以和低位的計算結(jié)果同時獲得。這個的核心原因是電路是天然并行的，一個輸入信號，可以同時傳播到所有接通的線路當中。

如果一個 4 位整數(shù)最高位是否進位，展開門電路圖，你會發(fā)現(xiàn)，我們只需要 3T 的延遲就可以拿到是否進位的計算結(jié)果。而對于 64 位的整數(shù)，也不會增加門延遲，只是從上往下復制這個電路，接入更多的信號而已。看到?jīng)]？我們通過把電路變復雜，就解決了延遲的問題。

這個優(yōu)化，本質(zhì)上是利用了電路天然的并行性。電路只要接通，輸入的信號自動傳播到了所有接通的線路里面，這其實也是硬件和軟件最大的不同。

無論是這里把對應的門電路邏輯進行完全展開以減少門延遲，還是上面的乘法通過并行計算多個位的乘法，都是把我們完成一個計算的電路變復雜了。而電路變復雜了，也就意味著晶體管變多了。

之前很多同學在我們討論計算機的性能問題的時候，都提到，為什么晶體管的數(shù)量增加可以優(yōu)化計算機的計算性能。實際上，這里的門電路展開和上面的并行計算乘法都是很好的例子。我們通過更多的晶體管，就可以拿到更低的門延遲，以及用更少的時鐘周期完成一個計算指令。

浮點數(shù)和定點數(shù)

浮點數(shù)的不精確性

那么，我們能不能用二進制表示所有的實數(shù)，然后在二進制下計算它的加減乘除呢？先不著急，我們從一個有意思的小案例來看。

你可以在 Linux 下打開 Python 的命令行 Console，也可以在 Chrome 瀏覽器里面通過開發(fā)者工具，打開瀏覽器里的 Console，在里面輸入“0.3 + 0.6”，然后看看你會得到一個什么樣的結(jié)果。

>>> 0.3 + 0.6
0.8999999999999999

不知道你有沒有大吃一驚，這么簡單的一個加法，無論是在 Python 還是在 JavaScript 里面，算出來的結(jié)果居然不是準確的 0.9，而是 0.8999999999999999 這么個結(jié)果。這是為什么呢？

在回答為什么之前，我們先來想一個更抽象的問題。通過前面的這么多講，你應該知道我們現(xiàn)在用的計算機通常用 16/32 個比特（bit）來表示一個數(shù)。那我問你，我們用 32 個比特，能夠表示所有實數(shù)嗎？

答案很顯然是不能。32 個比特，只能表示 2 的 32 次方個不同的數(shù)，差不多是 40 億個。如果表示的數(shù)要超過這個數(shù)，就會有兩個不同的數(shù)的二進制表示是一樣的。那計算機可就會一籌莫展，不知道這個數(shù)到底是多少。

40 億個數(shù)看似已經(jīng)很多了，但是比起無限多的實數(shù)集合卻只是滄海一粟。所以，這個時候，計算機的設計者們，就要面臨一個問題了：我到底應該讓這 40 億個數(shù)映射到實數(shù)集合上的哪些數(shù)，在實際應用中才能最劃得來呢？

定點數(shù)的表示

有一個很直觀的想法，就是我們用 4 個比特來表示 0～9 的整數(shù)，那么 32 個比特就可以表示 8 個這樣的整數(shù)。然后我們把最右邊的 2 個 0～9 的整數(shù)，當成小數(shù)部分；把左邊 6 個 0～9 的整數(shù)，當成整數(shù)部分。這樣，我們就可以用 32 個比特，來表示從 0 到 999999.99 這樣 1 億個實數(shù)了。

這種用二進制來表示十進制的編碼方式，叫作BCD 編碼（Binary-Coded Decimal）。其實它的運用非常廣泛，最常用的是在超市、銀行這樣需要用小數(shù)記錄金額的情況里。在超市里面，我們的小數(shù)最多也就到分。這樣的表示方式，比較直觀清楚，也滿足了小數(shù)部分的計算。

不過，這樣的表示方式也有幾個缺點。

第一，這樣的表示方式有點“浪費”。本來 32 個比特我們可以表示 40 億個不同的數(shù)，但是在 BCD 編碼下，只能表示 1 億個數(shù)，如果我們要精確到分的話，那么能夠表示的最大金額也就是到 100 萬。如果我們的貨幣單位是人民幣或者美元還好，如果我們的貨幣單位變成了津巴布韋幣，這個數(shù)量就不太夠用了。

第二，這樣的表示方式?jīng)]辦法同時表示很大的數(shù)字和很小的數(shù)字。我們在寫程序的時候，實數(shù)的用途可能是多種多樣的。有時候我們想要表示商品的金額，關心的是 9.99 這樣小的數(shù)字；有時候，我們又要進行物理學的運算，需要表示光速，也就是 3×1083×108 這樣很大的數(shù)字。那么，我們有沒有一個辦法，既能夠表示很小的數(shù)，又能表示很大的數(shù)呢？

浮點數(shù)的表示

答案當然是有的，就是你可能經(jīng)常聽說過的浮點數(shù)（Floating Point），也就是float 類型。

我們先來想一想。如果我們想在一張便簽紙上，用一行來寫一個十進制數(shù)，能夠?qū)懴露啻蠓秶臄?shù)？因為我們要讓人能夠看清楚，所以字最小也有一個限制。你會發(fā)現(xiàn)一個和上面我們用 BCD 編碼表示數(shù)一樣的問題，就是紙張的寬度限制了我們能夠表示的數(shù)的大小。如果寬度只放得下 8 個數(shù)字，那么我們還是只能寫下最大到 99999999 這樣的數(shù)字。

其實，這里的紙張寬度，就和我們 32 個比特一樣，是在空間層面的限制。那么，在現(xiàn)實生活中，我們是怎么表示一個很大的數(shù)的呢？比如說，我們想要在一本科普書里，寫一下宇宙內(nèi)原子的數(shù)量，莫非是用一頁紙，用好多行寫下很多個 0 么？

當然不是了，我們會用科學計數(shù)法來表示這個數(shù)字。宇宙內(nèi)的原子的數(shù)量，大概在 10 的 82 次方左右，我們就用 1.0×10821.0×1082 這樣的形式來表示這個數(shù)值，不需要寫下 82 個 0。

在計算機里，我們也可以用一樣的辦法，用科學計數(shù)法來表示實數(shù)。浮點數(shù)的科學計數(shù)法的表示，有一個IEEE的標準，它定義了兩個基本的格式。一個是用 32 比特表示單精度的浮點數(shù)，也就是我們常常說的 float 或者 float32 類型。另外一個是用 64 比特表示雙精度的浮點數(shù)，也就是我們平時說的 double 或者 float64 類型。

雙精度類型和單精度類型差不多，這里，我們來看單精度類型，雙精度你自然也就明白了。

單精度的 32 個比特可以分成三部分。

第一部分是一個符號位，用來表示是正數(shù)還是負數(shù)。我們一般用s來表示。在浮點數(shù)里，我們不像正數(shù)分符號數(shù)還是無符號數(shù)，所有的浮點數(shù)都是有符號的。

接下來是一個 8 個比特組成的指數(shù)位。我們一般用e來表示。8 個比特能夠表示的整數(shù)空間，就是 0～255。我們在這里用 1～254 映射到 -126～127 這 254 個有正有負的數(shù)上。因為我們的浮點數(shù)，不僅僅想要表示很大的數(shù)，還希望能夠表示很小的數(shù)，所以指數(shù)位也會有負數(shù)。

你發(fā)現(xiàn)沒，我們沒有用到 0 和 255。沒錯，這里的 0（也就是 8 個比特全部為 0） 和 255 （也就是 8 個比特全部為 1）另有它用，我們等一下再講。

最后，是一個 23 個比特組成的有效數(shù)位。我們用f來表示。綜合科學計數(shù)法，我們的浮點數(shù)就可以表示成下面這樣：

[(?1)^s×1.f×2^e
]

你會發(fā)現(xiàn)，這里的浮點數(shù)，沒有辦法表示 0。的確，要表示 0 和一些特殊的數(shù)，我們就要用上在 e 里面留下的 0 和 255 這兩個表示，這兩個表示其實是兩個標記位。在 e 為 0 且 f 為 0 的時候，我們就把這個浮點數(shù)認為是 0。至于其它的 e 是 0 或者 255 的特殊情況，你可以看下面這個表格，分別可以表示出無窮大、無窮小、NAN 以及一個特殊的不規(guī)范數(shù)。

我們可以以 0.5 為例子。0.5 的符號為 s 應該是 0，f 應該是 0，而 e 應該是 -1，也就是

[0.5=(?1)^0×1.0×2^{?1} =0.5
]

，對應的浮點數(shù)表示，就是 32 個比特。

[s=0，e=2^{?1}
]

，需要注意，e 表示從 -126 到 127 個，-1 是其中的第 126 個數(shù)，這里的 e 如果用整數(shù)表示，就是

[2^6+2^5+2^4+2^3+2^2+2^1=126，1.f=1.0
]

。

在這樣的浮點數(shù)表示下，不考慮符號的話，浮點數(shù)能夠表示的最小的數(shù)和最大的數(shù)，差不多是

[1.17×10^{?38}
]

和

[3.40×10^{38}
]

。比前面的 BCD 編碼能夠表示的范圍大多了。

浮點數(shù)的二進制轉(zhuǎn)化

我們首先來看，十進制的浮點數(shù)怎么表示成二進制。

我們輸入一個任意的十進制浮點數(shù)，背后都會對應一個二進制表示。比方說，我們輸入了一個十進制浮點數(shù) 9.1。那么按照之前的講解，在二進制里面，我們應該把它變成一個“符號位 s+ 指數(shù)位 e+ 有效位數(shù) f”的組合。第一步，我們要做的，就是把這個數(shù)變成二進制。

首先，我們把這個數(shù)的整數(shù)部分，變成一個二進制。這個我們前面講二進制的時候已經(jīng)講過了。這里的 9，換算之后就是 1001。

接著，我們把對應的小數(shù)部分也換算成二進制。小數(shù)怎么換成二進制呢？我們先來定義一下，小數(shù)的二進制表示是怎么回事。我們拿 0.1001 這樣一個二進制小數(shù)來舉例說明。和上面的整數(shù)相反，我們把小數(shù)點后的每一位，都表示對應的 2 的 -N 次方。那么 0.1001，轉(zhuǎn)化成十進制就是：

[1×2^{?1}+0×2^{?2}+0×2^{?3}+1×2{?4}=0.5625
]

和整數(shù)的二進制表示采用“除以 2，然后看余數(shù)”的方式相比，小數(shù)部分轉(zhuǎn)換成二進制是用一個相似的反方向操作，就是乘以 2，然后看看是否超過 1。如果超過 1，我們就記下 1，并把結(jié)果減去 1，進一步循環(huán)操作。在這里，我們就會看到，0.1 其實變成了一個無限循環(huán)的二進制小數(shù)，0.000110011。這里的“0011”會無限循環(huán)下去。

然后，我們把整數(shù)部分和小數(shù)部分拼接在一起，9.1 這個十進制數(shù)就變成了 1001.000110011…這樣一個二進制表示。

上一講我們講過，浮點數(shù)其實是用二進制的科學計數(shù)法來表示的，所以我們可以把小數(shù)點左移三位，這個數(shù)就變成了：

[1.0010001100110011…×2^3
]

那這個二進制的科學計數(shù)法表示，我們就可以對應到了浮點數(shù)的格式里了。這里的符號位 s = 0，對應的有效位 f=001000110011…。因為 f 最長只有 23 位，那這里“0011”無限循環(huán)，最多到 23 位就截止了。于是，f=00100011001100110011 001。最后的一個“0011”循環(huán)中的最后一個“1”會被截斷掉。對應的指數(shù)為 e，代表的應該是 3。因為指數(shù)位有正又有負，所以指數(shù)位在 127 之前代表負數(shù)，之后代表正數(shù)，那 3 其實對應的是加上 127 的偏移量 130，轉(zhuǎn)化成二進制，就是 130，對應的就是指數(shù)位的二進制，表示出來就是 10000010。

然后，我們把“s+e+f”拼在一起，就可以得到浮點數(shù) 9.1 的二進制表示了。最終得到的二進制表示就變成了：

010000010 0010 0011001100110011 001

如果我們再把這個浮點數(shù)表示換算成十進制， 實際準確的值是 9.09999942779541015625。相信你現(xiàn)在應該不會感覺奇怪了。

我在這里放一個鏈接，這里提供了直接交互式地設置符號位、指數(shù)位和有效位數(shù)的操作。你可以直觀地看到，32 位浮點數(shù)每一個 bit 的變化，對應的有效位數(shù)、指數(shù)會變成什么樣子以及最后的十進制的計算結(jié)果是怎樣的。

浮點數(shù)的加法和精度損失

搞清楚了怎么把一個十進制的數(shù)值，轉(zhuǎn)化成 IEEE-754 標準下的浮點數(shù)表示，我們現(xiàn)在來看一看浮點數(shù)的加法是怎么進行的。其實原理也很簡單，你記住六個字就行了，那就是先對齊、再計算。

兩個浮點數(shù)的指數(shù)位可能是不一樣的，所以我們要把兩個的指數(shù)位，變成一樣的，然后只去計算有效位的加法就好了。

比如 0.5，表示成浮點數(shù)，對應的指數(shù)位是 -1，有效位是 00…（后面全是 0，記住 f 前默認有一個 1）。0.125 表示成浮點數(shù)，對應的指數(shù)位是 -3，有效位也還是 00…（后面全是 0，記住 f 前默認有一個 1）。

那我們在計算 0.5+0.125 的浮點數(shù)運算的時候，首先要把兩個的指數(shù)位對齊，也就是把指數(shù)位都統(tǒng)一成兩個其中較大的 -1。對應的有效位 1.00…也要對應右移兩位，因為 f 前面有一個默認的 1，所以就會變成 0.01。然后我們計算兩者相加的有效位 1.f，就變成了有效位 1.01，而指數(shù)位是 -1，這樣就得到了我們想要的加法后的結(jié)果。

實現(xiàn)這樣一個加法，也只需要位移。和整數(shù)加法類似的半加器和全加器的方法就能夠?qū)崿F(xiàn)，在電路層面，也并沒有引入太多新的復雜性。

同樣的，你可以用剛才那個鏈接來試試看，我們這個加法計算的浮點數(shù)的結(jié)果是不是正確。

回到浮點數(shù)的加法過程，你會發(fā)現(xiàn)，其中指數(shù)位較小的數(shù)，需要在有效位進行右移，在右移的過程中，最右側(cè)的有效位就被丟棄掉了。這會導致對應的指數(shù)位較小的數(shù)，在加法發(fā)生之前，就丟失精度。兩個相加數(shù)的指數(shù)位差的越大，位移的位數(shù)越大，可能丟失的精度也就越大。當然，也有可能你的運氣非常好，右移丟失的有效位都是 0。這種情況下，對應的加法雖然丟失了需要加的數(shù)字的精度，但是因為對應的值都是 0，實際的加法的數(shù)值結(jié)果不會有精度損失。

32 位浮點數(shù)的有效位長度一共只有 23 位，如果兩個數(shù)的指數(shù)位差出 23 位，較小的數(shù)右移 24 位之后，所有的有效位就都丟失了。這也就意味著，雖然浮點數(shù)可以表示上到 3.40×10^38，下到 1.17×10^?38 這樣的數(shù)值范圍。但是在實際計算的時候，只要兩個數(shù)，差出 2^24，也就是差不多 1600 萬倍，那這兩個數(shù)相加之后，結(jié)果完全不會變化。

你可以試一下，我下面用一個簡單的 Java 程序，讓一個值為 2000 萬的 32 位浮點數(shù)和 1 相加，你會發(fā)現(xiàn)，+1 這個過程因為精度損失，被“完全拋棄”了。

public class FloatPrecision {
  public static void main(String[] args) {
    float a = 20000000.0f;
    float b = 1.0f;
    float c = a + b;
    System.out.println("c is " + c);
    float d = c - a;
    System.out.println("d is " + d);
  }
}

對應的輸出結(jié)果就是：

c is 2.0E7
d is 0.0

Kahan Summation 算法

那么，我們有沒有什么辦法來解決這個精度丟失問題呢？雖然我們在計算浮點數(shù)的時候，常?？梢匀萑桃欢ǖ木葥p失，但是像上面那樣，如果我們連續(xù)加 2000 萬個 1，2000 萬的數(shù)值都會被精度損失丟掉了，就會影響我們的計算結(jié)果。

一個常見的應用場景是，在一些“積少成多”的計算過程中，比如在機器學習中，我們經(jīng)常要計算海量樣本計算出來的梯度或者 loss，于是會出現(xiàn)幾億個浮點數(shù)的相加。每個浮點數(shù)可能都差不多大，但是隨著累積值的越來越大，就會出現(xiàn)“大數(shù)吃小數(shù)”的情況。

我們可以做一個簡單的實驗，用一個循環(huán)相加 2000 萬個 1.0f，最終的結(jié)果會是 1600 萬左右，而不是 2000 萬。這是因為，加到 1600 萬之后的加法因為精度丟失都沒有了。這個代碼比起上面的使用 2000 萬來加 1.0 更具有現(xiàn)實意義。

public class FloatPrecision {
  public static void main(String[] args) {
    float sum = 0.0f;
    for (int i = 0; i < 20000000; i++) {
    	float x = 1.0f;
    	sum += x;    	
    }
    System.out.println("sum is " + sum);   
  }	
}

對應的輸出結(jié)果是：

sum is 1.6777216E7

面對這個問題，聰明的計算機科學家們也想出了具體的解決辦法。他們發(fā)明了一種叫作Kahan Summation的算法來解決這個問題。算法的對應代碼我也放在文稿中了。從中你可以看到，同樣是 2000 萬個 1.0f 相加，用這種算法我們得到了準確的 2000 萬的結(jié)果。

public class KahanSummation {
  public static void main(String[] args) {
    float sum = 0.0f;
    float c = 0.0f;
    for (int i = 0; i < 20000000; i++) {
    	float x = 1.0f;
    	float y = x - c;
    	float t = sum + y;
    	c = (t-sum)-y;
    	sum = t;    	
    }
    System.out.println("sum is " + sum);   
  }	
}

對應的輸出結(jié)果就是：

sum is 2.0E7

其實這個算法的原理其實并不復雜，就是在每次的計算過程中，都用一次減法，把當前加法計算中損失的精度記錄下來，然后在后面的循環(huán)中，把這個精度損失放在要加的小數(shù)上，再做一次運算。

如果你對這個背后的數(shù)學原理特別感興趣，可以去看一看Wikipedia 鏈接里面對應的數(shù)學證明，也可以生成一些數(shù)據(jù)試一試這個算法。這個方法在實際的數(shù)值計算中也是常用的，也是大量數(shù)據(jù)累加中，解決浮點數(shù)精度帶來的“大數(shù)吃小數(shù)”問題的必備方案。

總結(jié)

到這里，我們已經(jīng)講完了浮點數(shù)的表示、加法計算以及可能會遇到的精度損失問題?？梢钥吹?，雖然浮點數(shù)能夠表示的數(shù)據(jù)范圍變大了很多，但是在實際應用的時候，由于存在精度損失，會導致加法的結(jié)果和我們的預期不同，乃至于完全沒有加上的情況。

所以，一般情況下，在實踐應用中，對于需要精確數(shù)值的，比如銀行存款、電商交易，我們都會使用定點數(shù)或者整數(shù)類型。

比方說，你一定在 MySQL 里用過 decimal(12,2)，來表示訂單金額。如果我們的銀行存款用 32 位浮點數(shù)表示，就會出現(xiàn)，馬云的賬戶里有 2 千萬，我的賬戶里只剩 1 塊錢。結(jié)果銀行一匯總總金額，那 1 塊錢在賬上就“不翼而飛”了。

而浮點數(shù)呢，則更適合我們不需要有一個非常精確的計算結(jié)果的情況。因為在真實的物理世界里，很多數(shù)值本來就不是精確的，我們只需要有限范圍內(nèi)的精度就好了。比如，從我家到辦公室的距離，就不存在一個 100% 精確的值。我們可以精確到公里、米，甚至厘米，但是既沒有必要、也沒有可能去精確到微米乃至納米。

對于浮點數(shù)加法中可能存在的精度損失，特別是大量加法運算中累積產(chǎn)生的巨大精度損失，我們可以用 Kahan Summation 這樣的軟件層面的算法來解決。

總結(jié)

以上是生活随笔為你收集整理的计算机组成原理——原理篇 指令和运算（下）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。