N進位這麼好玩，你知道嗎？

知識 06-14

N進位這麼好玩，你知道嗎？

【一個傳統小遊戲】

設計四張卡片：

第一張寫有 1， 3， 5， 7， 9，11，13，15

第二張寫有 2， 3， 6， 7，10，11，14，15

第三張寫有 4， 5， 6， 7，12，13，14，15

第四張寫有 8， 9，10，11，12，13，14，15

某甲心裡想一個0-15間的整數，告訴你此數共在哪些卡片里有。你將這些卡片的第一個數加起來，就得到某甲心裡想的那個數。

這個遊戲很多人見過，但未必都知道其背後的數學道理就是二進位。解釋如下：

第一張卡片中是0-15間所有二進位表示為xxx1的數，而其第一個數是0001。第二張卡片中是0-15間所有二進位表示為xx1x的數，而其第一個數是0010。後兩張類推。

例如，某甲心裡想的數是13，這個數的二進位表示是1101，因此它在第一、三、四張卡片里有，而且正等於0001 + 0100 + 1000。

【幾個IT相關的二進位問題】

1.在美國的公司剛剛工作不久的一天，一位計算機專業的小夥子跑來找我，說他新裝的VB6是有BUG的，讓我看看。他的即時窗口裡顯示： 3.0 – 2.99 = 0.00999999999999979。

我告訴他有一個文件叫IEEE754，可以解惑，他堅持讓我說。於是我告訴他：double 數型有64個二進位位，其中第1位是表示正負符號的，第2至12位是表示帶偏移的指數的，後52位是表示「小數」的。2.99無法用二進位精確表示，所以才造成他看到的結果。這是 double 與生俱來的，不是VB6的BUG。

2.不久，公司一位波蘭女孩找我，說公司讓她編的「四捨五入」函數會出現工作異常。

我看了代碼，發現她所寫的round( r, n ) 函數，基本上等於是 floor( r*10^n + 0.5 ) / 10^n。這代碼里也有double之二進位存儲產生的問題。

例如，round(1.005, 2)=1.01。但是，1.005不能用double精確表示，它的表示約為1.0049999999999998。因此，以上代碼計算的「r*10^2 + 0.5」約等於100.999999999998，取整後為100。結果，其代碼給出的答案是1.00，錯了。

3.在做偏微分方程的迭代求解時，我發現迭代N次後的結果在debug模式與release模式下不一致。仔細分析代碼，發現類似1.0 + 0.25*DBL_EPSILON + 0.25*DBL_EPSILON 的計算式，在兩種模式之下的計算結果分別為1.0與1.0+DBL_EPSILON。原因在於後一種模式默認某種「優化」計算……不細說。

還有其他問題，很多都牽涉到double在計算機內部的二進位表示。了解IEE754的規定，才能夠找到問題所在以及解決辦法。這個知識點對IT高手不是問題，但相對入門級的新手很有用。

【用三進位證明( 0, 1 )中的實數不可數】

首先，把( 0, 1 )中的實數用三進位表示；其次，用反證法，假設( 0, 1 )中的實數是可數個。

由於是可數個數，因此可以將所有這些數寫成數列x(n)。

構造一個三進位小數y：其第一位小數取數與x(1)的第一位不同，且不取2；從第二位小數開始，第n位取不同於x(n)的第n位，且與y已經取得的前一位不同——例如，設x(10)為2，y 的第9位已經取0，則y 的第10位取1。

不難證明，此y是( 0, 1 )中的實數，且不等於數列x(n)中的任何一個。也就是說，數列x(n)不可能包括全部( 0, 1 )中的實數。

這證明，( 0, 1 )中的實數是不可數個，也就是說：不可能把( 0, 1 )中的實數一一對應到自然數集上。

【康威十三進位數】

文不對題一下，我們只考慮使用十一進位，康威十三進位數留給好奇者去探索。

用A記10，用十一進位表示所有( 0, 1 )中的實數。

在所有這些十一進位表示的( 0, 1 )中的實數里，考慮A僅出現有限次的那些數。對一個這種數x，去掉其最後出現的A之前的所有數字，把A改成「0.」，則得到一個新的小數y。把y解讀為十進位小數，則我們構造了一個從( 0, 1 )到( 0, 1 )的映射。

關鍵是，這個映射中，( 0, 1 )內的每一個數都有無窮多個原像。也就是說( 0, 1 )可以映滿( 0, 1 )無窮多次。