1、算法移植 浮點轉定點運算 二TraceBack：小數點的表示為了節省內存，計算機中數值型數據的小數點的位置是隱含的，且小數點的位置既可以是固定的，也可以是變化的。定點數與浮點數如果小數點的位置事先已有約定，不再改變，此類數稱為定點數。相比之下，如果小數點的位置可變，則稱為浮點數。定點數。常用的定點數有兩種表示形式：如果小數點位置約定在最低數值位的后面，則該數只能是定點整數；如果小數點位置約定在最高數值位的前面，則該數只能是定點小數。例如，假定用兩個字節存放一個定點數，則以定點方式表示的十進制整數195為：這里，(-0.6876)10=(-0.101101)2，轉換為無限循環小數，存儲時多余的位

2、被截斷。如果知道一個定點數的小數點位置約定和占用存儲空間大小，那么很容易確定其表示數的范圍。浮點數。浮點數表示法來源于數學中的指數表示形式，如193可以表示為0.193x103或1.93x102等。一般地，數的指數形式可記作：N=M xRC其中，M稱為尾數，C稱為階碼。在存儲時，一個浮點數所占用的存儲空間被劃分為兩部分，分別存放尾數和階碼。尾數部分通常使用定點小數方式，階碼則采用定點整數方式。尾數的長度影響該數的精度，而階碼則決定該數的表示范圍。同樣大小的空間中，可以存放遠比定點數取值范圍大得多的浮點數，但浮點數的運算規則比定點數更復雜。1.什么是浮點數在計算機系統的發展過程中，曾經提出過多種

3、方法表達實數。典型的比如相對于浮點數的定點數(Fixed Point Number)。【所謂的定點數，就是指小數點的位置是固定的】在這種表達方式中，小數點固定的位于實數所有數字中間的某個位置。貨幣的表達就可以使用這種方式，比如99.00或者00.99可以用于表達具有四位精度(Precision)，小數點后有兩位的貨幣值。由于小數點位置固定，所以可以直接用四位數值來表達相應的數值。SQL中的NUMBER數據類型就是利用定點數來定義的。還有一種提議的表達方式為有理數表達方式，即用兩個整數的比值來表達實數。定點數表達法的缺點在于其形式過于僵硬，固定的小數點位置決定了固定位數的整數部分和小數部分，不利

4、于同時表達特別大的數或者特別小的數。最終，絕大多數現代的計算機系統采納了所謂的浮點數表達方式。這種表達方式利用科學計數法來表達實數，即用一個尾數(Mantissa)，一個基數(Base)，一個指數(Exponent)以及一個表示正負的符號來表達實數。比如123.45用十進制科學計數法可以表達為1.2345102，其中1.2345為尾數，10為基數，2為指數。浮點數利用指數達到了浮動小數點的效果，從而可以靈活地表達更大范圍的實數。提示：尾數有時也稱為有效數字(Significand)。尾數實際上是有效數字的非正式說法。同樣的數值可以有多種浮點數表達方式，比如上面例子中的123.45可以表達為12

5、.345101，0.12345103或者1.2345102。因為這種多樣性，有必要對其加以規范化以達到統一表達的目標。規范的(Normalized)浮點數表達方式具有如下形式：d.dd.de,(0d i)其中d.dd.d即尾數，為基數，e為指數。尾數中數字的個數稱為精度，在本文中用p來表示。每個數字d介于0和基數之間，包括0。小數點左側的數字不為0。基于規范表達的浮點數對應的具體值可由下面的表達式計算而得：(d 0+d 1-1+.+d p-1-(p-1)e,(0d i)對于十進制的浮點數，即基數等于10的浮點數而言，上面的表達式非常容易理解，也很直白。計算機內部的數值表達是基于二進制的。從上面

6、的表達式，我們可以知道，二進制數同樣可以有小數點，也同樣具有類似于十進制的表達方式。只是此時等于2，而每個數字d只能在0和1之間取值。比如二進制數1001.101相當于12 3+022+021+120+12-1+02-2+12-3，對應于十進制的9.625。其規范浮點數表達為1.00110123。2.IEEE浮點數計算機中是用有限的連續字節保存浮點數的。保存這些浮點數當然必須有特定的格式，Java平臺上的浮點數類型float和double采納了IEEE 754標準中所定義的單精度32位浮點數和雙精度64位浮點數的格式。注意：Java平臺還支持該標準定義的兩種擴展格式，即float-extend

7、ed-exponent和double-extended-exponent擴展格式。這里將不作介紹，有興趣的讀者可以參考相應的參考資料。在IEEE標準中，浮點數是將特定長度的連續字節的所有二進制位分割為特定寬度的符號域，指數域和尾數域三個域，其中保存的值分別用于表示給定二進制浮點數中的符號，指數和尾數。這樣，通過尾數和可以調節的指數(所以稱為浮點)就可以表達給定的數值了。具體的格式參見下面的圖例：在上面的圖例中，第一個域為符號域。其中0表示數值為正數，而1則表示負數。第二個域為指數域，對應于我們之前介紹的二進制科學計數法中的指數部分。其中單精度數為8位，雙精度數為11位。以單精度數為例，8位的指

8、數為可以表達0到255之間的255個指數值。但是，指數可以為正數，也可以為負數。為了處理負指數的情況，實際的指數值按要求需要加上一個偏差(Bias)值作為保存在指數域中的值，單精度數的偏差值為127，而雙精度數的偏差值為1023。比如，單精度的實際指數值0在指數域中將保存為-127；而保存在指數域中的64則表示實際的指數值-63。偏差的引入使得對于單精度數，實際可以表達的指數值的范圍就變成-127到128之間(包含兩端)。我們不久還將看到，實際的指數值-127(保存為全0)以及+128(保存為全1)保留用作特殊值的處理。這樣，實際可以表達的有效指數范圍就在-127和127之間。-1270128

9、 0(全0)127255(全1)在本文中，最小指數和最大指數分別用emin和emax來表達。圖例中的第三個域為尾數域，其中單精度數為23位長，雙精度數為52位長。除了我們將要講到的某些特殊值外，IEEE標準要求浮點數必須是規范的。這意味著尾數的小數點左側必須為1，因此我們在保存尾數的時候，可以省略小數點前面這個1，從而騰出一個二進制位來保存更多的尾數。這樣我們實際上用23位長的尾數域表達了24位的尾數。比如對于單精度數而言，二進制的1001.101(對應于十進制的9.625)可以表達為1.00110123，所以實際保存在尾數域中的值為0，即去掉小數點左側的1，并用0在右側補齊。值得注意的是，對

10、于單精度數，由于我們只有24位的指數(其中一位隱藏)，所以可以表達的最大指數為224-1=16,777,215。特別的，16,777,216是偶數，所以我們可以通過將它除以2并相應地調整指數來保存這個數，這樣16,777,216同樣可以被精確的保存。相反，數值16,777,217則無法被精確的保存。由此，我們可以看到單精度的浮點數可以表達的十進制數值中，真正有效的數字不高于8位。事實上，對相對誤差的數值分析結果顯示有效的精度大約為7.22位。參考下面的示例：true value stored value-16,777,215 1.6777215 E7 16,777,216 1.6777216

11、E7 16,777,217 1.6777216 E7 16,777,218 1.6777218 E7 16,777,219 1.677722 E7 16,777,220 1.677722 E7 16,777,221 1.677722 E7 16,777,222 1.6777222 E7 16,777,223 1.6777224 E7 16,777,224 1.6777224 E7 16,777,225 1.6777224 E7-根據標準要求，無法精確保存的值必須向最接近的可保存的值進行舍入。這有點像我們熟悉的十進制的四舍五入，即不足一半則舍，一半以上(包括一半)則進。不過對于二進制浮點數而言，

12、還多一條規矩，就是當需要舍入的值剛好是一半時，不是簡單地進，而是在前后兩個等距接近的可保存的值中，取其中最后一位有效數字為零者。從上面的示例中可以看出，奇數都被舍入為偶數，且有舍有進。我們可以將這種舍入誤差理解為半位的誤差。所以，為了避免7.22對很多人造成的困惑，有些文章經常以7.5位來說明單精度浮點數的精度問題。提示：這里采用的浮點數舍入規則有時被稱為舍入到偶數(Round to Even)。相比簡單地逢一半則進的舍入規則，舍入到偶數有助于從某些角度減小計算中產生的舍入誤差累積問題。因此為IEEE標準所采用。3.實數和浮點數之間的變換現在我們已經明白了浮點數的IEEE表達方式。我們來做些實

13、數和浮點數之間的變換練習以加深理解。在這些練習中，你還會發現一些圍繞浮點數運算的令人吃驚的事實。首先我們來看看事情簡單的一面，從浮點數變換到實數。理解了浮點數的格式，做這個練習并不難。假定我們有一個32位的數據，用十六進制表示為0xC0B40000，并且我們知道它實際上是一個單精度的浮點數。為了得到該浮點數實際表達的實數，我們首先將它變換為二進制形式：C 0B 40 00 01100 0000 1011 0100 0000 0000 0000 0000接著按照浮點數的格式切分為相應的域：1 100000000符號域1意味著負數；指數域為129意味著實際的指數為2(減去偏差值127)；尾數域為0

14、1101意味著實際的二進制尾數為1.01101(加上隱含的小數點前面的1)。所以，實際的實數為：-1.0110122-(20+2-2+2-3 2-5)22-5.625從實數向浮點數變換稍微麻煩一點。假定我們需要將實數-9.625表達為單精度的浮點數格式。方法是首先將它用二進制浮點數表達，然后變換為相應的浮點數格式。首先，將小數點左側的整數部分變換為其二進制形式，9的二進制性形式為1001。處理小數部分的算法是將我們的小數部分乘以基數2，記錄乘積結果的整數部分，接著將結果的小數部分繼續乘以2，并不斷繼續該過程：0.6252=1.25 10.252=0.5 00.52=1 10當最后的結果為零時，

15、結束這個過程。這時右側的一列數字就是我們所需的二進制小數部分，即0.101。這樣，我們就得到了完整的二進制形式1001.101。用規范浮點數表達為1.00110123。因為是負數，所以符號域為1。指數為3，所以指數域為3+127=130，即二進制的。尾數省略掉小數點左側的1之后為001101，右側用零補齊。最終結果為：1 100000000最后可以將浮點數形式表示為十六進制的數據如下：1100 0001 0001 1010 0000 0000 0000 0000 C1 1A 00 00最終結果為0xC11A0000。很簡單?等等！你可能已經注意到了，在上面這個我們有意選擇的示例中，不斷的將產生

16、的小數部分乘以2的過程掩蓋了一個事實。該過程結束的標志是小數部分乘以2的結果為1，不難想象，很多小數根本不能經過有限次這樣的過程而得到結果(比如最簡單的0.1)。我們已經知道浮點數尾數域的位數是有限的，為此，浮點數的處理辦法是持續該過程直到由此得到的尾數足以填滿尾數域，之后對多余的位進行舍入。換句話說，除了我們之前講到的精度問題之外，十進制到二進制的變換也并不能保證總是精確的，而只能是近似值。事實上，只有很少一部分十進制小數具有精確的二進制浮點數表達。再加上浮點數運算過程中的誤差累積，結果是很多我們看來非常簡單的十進制運算在計算機上卻往往出人意料。這就是最常見的浮點運算的不準確問題。參見下面的

17、Java示例：System.out.print(34.6-34.0=+(34.6f-34.0f)；這段代碼的輸出結果如下：34.6-34.0=0.5999985產生這個誤差的原因是34.6無法精確的表達為相應的浮點數，而只能保存為經過舍入的近似值。這個近似值與34.0之間的運算自然無法產生精確的結果。4.特殊值通過前面的介紹，你應該已經了解的浮點數的基本知識，這些知識對于一個不接觸浮點數應用的人應該足夠了。不過，如果你興趣正濃，或者面對著一個棘手的浮點數應用，可以通過本節了解到關于浮點數的一些值得注意的特殊之處。我們已經知道，指數域實際可以表達的指數值的范圍為-127到128之間(包含兩端)。

18、其中，值-127(保存為全0)以及+128(保存為全1)保留用作特殊值的處理。本節將詳細IEEE標準中所定義的這些特殊值。浮點數中的特殊值主要用于特殊情況或者錯誤的處理。比如在程序對一個負數進行開平方時，一個特殊的返回值將用于標記這種錯誤，該值為NaN(Not aNumber)。沒有這樣的特殊值，對于此類錯誤只能粗暴地終止計算。除了NaN之外，IEEE標準還定義了0，以及非規范化數(Denormalized Number)。對于單精度浮點數，所有這些特殊值都由保留的特殊指數值-127和128來編碼。如果我們分別用emin和emax來表達其它常規指數值范圍的邊界，即-126和127，則保留的特殊

19、指數值可以分別表達為emin-1和emax+1；。基于這個表達方式，IEEE標準的特殊值如下所示：其中f表示尾數中的小數點右側的(Fraction)部分。第一行即我們之前介紹的普通的規范化浮點數。隨后我們將分別對余下的特殊值加以介紹。4.1.NaN NaN用于處理計算中出現的錯誤情況，比如0.0除以0.0或者求負數的平方根。由上面的表中可以看出，對于單精度浮點數，NaN表示為指數為emax+1=128(指數域全為1)，且尾數域不等于零的浮點數。IEEE標準沒有要求具體的尾數域，所以NaN實際上不是一個，而是一族。不同的實現可以自由選擇尾數域的值來表達NaN，比如Java中的常量Float.Na

20、N的浮點數可能表達為0000000000，其中尾數域的第一位為1，其余均為0(不計隱藏的一位)，但這取決系統的硬件架構。Java中甚至允許程序員自己構造具有特定位模式的NaN值(通過FBitsToFloat()方法)。比如，程序員可以利用這種定制的NaN值中的特定位模式來表達某些診斷信息。定制的NaN值，可以通過Float.isNaN()方法判定其為NaN，但是它和Float.NaN常量卻不相等。實際上，所有的NaN值都是無序的。數值比較操作符，=，和=在任一操作數為NaN時均返回false。等于操作符=在任一操作數為NaN時均返回false，即使是兩個具有相同位模式的NaN也

21、一樣。而操作符！=則當任一操作數為NaN時返回true。這個規則的一個有趣的結果是x！=x當x為NaN時竟然為真。可以產生NaN的操作如下所示：此外，任何有NaN作為操作數的操作也將產生NaN。用特殊的NaN來表達上述運算錯誤的意義在于避免了因這些錯誤而導致運算的不必要的終止。比如，如果一個被循環調用的浮點運算方法，可能由于輸入的參數問題而導致發生這些錯誤，NaN使得即使某次循環發生了這樣的錯誤，也可以簡單地繼續執行循環以進行那些沒有錯誤的運算。你可能想到，既然Java有異常處理機制，也許可以通過捕獲并忽略異常達到相同的效果。但是，要知道，IEEE標準不是僅僅為Java而制定的，各種語言處理異

22、常的機制不盡相同，這將使得代碼的遷移變得更加困難。何況，不是所有語言都有類似的異常或者信號(Signal)處理機制。注意：Java中，不同于浮點數的處理，整數的0除以0將拋出java.lang.ArithmeticException異常。4.2.無窮和NaN一樣，特殊值無窮(Infinity)的指數部分同樣為emax+1=128，不過無窮的尾數域必須為零。無窮用于表達計算中產生的上溢(Overflow)問題。比如兩個極大的數相乘時，盡管兩個操作數本身可以用保存為浮點數，但其結果可能大到無法保存為浮點數，而必須進行舍入。根據IEEE標準，此時不是將結果舍入為可以保存的最大的浮點數(因為這個數可能

23、離實際的結果相差太遠而毫無意義)，而是將其舍入為無窮。對于負數結果也是如此，只不過此時舍入為負無窮，也就是說符號域為1的無窮。有了NaN的經驗我們不難理解，特殊值無窮使得計算中發生的上溢錯誤不必以終止運算為結果。無窮和除NaN以外的其它浮點數一樣是有序的，從小到大依次為負無窮，負的有窮非零值，正負零(隨后介紹)，正的有窮非零值以及正無窮。除NaN以外的任何非零值除以零，結果都將是無窮，而符號則由作為除數的零的符號決定。回顧我們對NaN的介紹，當零除以零時得到的結果不是無窮而是NaN。原因不難理解，當除數和被除數都逼近于零時，其商可能為任何值，所以IEEE標準決定此時用NaN作為商比較合適。4.

24、3.有符號的零因為IEEE標準的浮點數格式中，小數點左側的1是隱藏的，而零顯然需要尾數必須是零。所以，零也就無法直接用這種格式表達而只能特殊處理。實際上，零保存為尾數域為全為0，指數域為emin-1=-127，也就是說指數域也全為0。考慮到符號域的作用，所以存在著兩個零，即+0和-0。不同于正負無窮之間是有序的，IEEE標準規定正負零是相等的。零有正負之分，的確非常容易讓人困惑。這一點是基于數值分析的多種考慮，經利弊權衡后形成的結果。有符號的零可以避免運算中，特別是涉及無窮的運算中，符號信息的丟失。舉例而言，如果零無符號，則等式1/(1/x)=x當x=時不再成立。原因是如果零無符號，1和正負無

25、窮的比值為同一個零，然后1與0的比值為正無窮，符號沒有了。解決這個問題，除非無窮也沒有符號。但是無窮的符號表達了上溢發生在數軸的哪一側，這個信息顯然是不能不要的。零有符號也造成了其它問題，比如當x=y時，等式1/x=1/y在x和y分別為+0和-0時，兩端分別為正無窮和負無窮而不再成立。當然，解決這個問題的另一個思路是和無窮一樣，規定零也是有序的。但是，如果零是有序的，則即使if(x=0)這樣簡單的判斷也由于x可能是0而變得不確定了。兩害取其輕者，零還是無序的好。4.4.非規范化數我們來考察浮點數的一個特殊情況。選擇兩個絕對值極小的浮點數，以單精度的二進制浮點數為例，比如1.0012-125和1.00012-125這兩個數(分別對應于