二進制

進位記數系統

二進制[1][2](英語:binary)在數學數位電路中指以2為底數的記數系統,以2為基數代表系統是二進位制的。這一系統中,通常用兩個不同的數字0和1來表示。數字電子電路中,邏輯門直接採用了二進制,因此現代的計算機和依賴計算機的設備裡都用到二進制。每個數字稱為一個位元(二進制位)或比特(Bit,Binary digit 的縮寫)。

歷史

現代的二進制記數系統由戈特弗里德·萊布尼茨於1679年設計,在他1703年發表的文章《論只使用符號0和1的二進制算術,兼論其用途及它賦予伏羲所使用的古老圖形的意義》[3]出現。與二進制數相關的系統在一些更早的文化中也有出現,包括古埃及古代中國古印度以及太平洋島原住民文明。其中,古代中國的《易經》尤其引起了萊布尼茨的聯想。

 

 
荷魯斯之眼各部分所代表的算術值

埃及

古埃及的計數員使用兩種不同的系統表示分數,一是埃及分數(與二進制記數系統無關),二是荷魯斯之眼分數(叫這個名字是因為很多數學史家相信這個系統所採用的符號可以排列成荷魯斯之眼,但這一點有爭議)。荷魯斯之眼分數是用來表示分數數量的穀物、液體等的二進制記數系統,在這一系統下,以赫卡特為單位的分數值表示成1/2、1/4、1/8、1/16、1/32和1/64等二進制分數的和。 這一系統的早期形式可以在埃及第五王朝(約公元前2400年)的檔案中找到,而發展完備的象形文字形式可追溯到埃及第十九王朝(約公元前1200年)。 古埃及做乘法的方式也與二進制數密切相關,約公元前1650年的萊因德數學紙草書中就能看到。這一計算方法中,要把1和乘數不斷翻倍,按被乘數的二進制表示從左列選出相應的2的冪次,並將右列的數相加。[4]

印度

印度學者平甲拉(公元前兩世紀左右)通過二進制方法來研究韻律詩[5]。他的二進制中用到的是長短音節(一個長音節相當於兩個短音節),有些像摩爾斯電碼[6]。與西方的位置表示法不同,平甲拉的系統中,二進制是從右往左書寫的。

太平洋島原住民文明

法屬玻里尼西亞的曼格雷哇島,挪威卑爾根大學的人類學家Andrea Bender和Sieghard Beller發現,在曼格雷哇人的語言上,存在著一個似乎混合了十進位和二進位的數學系統。它先於西方幾個世紀,為首個在歐亞大陸之外發展出的二進位算法[7]

萊布尼茨前的西方先驅

1605年,弗朗西斯·培根提出了一套系統,可以把26個字母化為二進制數。此外他補充道,這個思路可以用於任何事物:「只要這些事物的差異是簡單對立的,比如鈴鐺和喇叭,燈光和手電筒,以及火槍和類似武器的射擊聲」。這對二進制編碼的一般理論有重要意義[8]。(參見培根密碼

萊布尼茨和中國的《易經》

 
戈特弗里德·萊布尼茲

萊布尼茨關於二進制的論文全名是《論只使用符號0和1的二進制算術,兼論其用途及它賦予伏羲所使用的古老圖形的意義》(1703年)。類似於現代二進制計數系統,萊布尼茲的系統使用0和1。下面是萊布尼茲的二進制記數系統的一個例子:

  • 0 0 0 1 數值為 
  • 0 0 1 0 數值為 
  • 0 1 0 0 數值為 
  • 1 0 0 0 數值為 
 
伏羲先天六十四卦〈方圓四分四層圖〉(1701年萊布尼茨得自白晉的圖文,時為清康熙四十年)

萊布尼茲認為易經中的卦象與二進制算術密不可分。萊布尼茲解讀了易經中的卦象,並認為這是其作為二進制算術的證據。作為親華派,萊布尼茲關注易經,並饒有興致地注意到它的卦象與從0到111111的二進制數字有某種對應,並認為這種對應反映了中國的重大成就中展現的他所崇尚的數學哲學。萊布尼茲首次接觸到易經是在與法國耶穌會傳教士白晉的聯繫中。白晉1685年作為傳教士前往中國。

長期以來,人們對萊布尼茨發明二進制是否受到了伏羲八卦的影響爭議頗多。認為萊布尼茨未受伏羲八卦影響獨立發明二進制的理由主要是萊布尼茨在1679年(與白晉首次通信的二十多年)就撰寫了「二的級數」(De Progressione Dyadica)一文,郭書春在《古代世界數學泰斗劉徽》一書461頁指出:「中國有所謂《周易》創造了二進制的說法,至於萊布尼茨受《周易》八卦的影響創造二進制並用於計算機的傳說,更是廣為流傳。事實是,萊布尼茲先發明了二進制,後來才看到傳教士帶回的宋代學者重新編排的《周易》八卦,並發現八卦可以用他的二進制來解釋。」因此,並不是萊布尼茨看到陰陽八卦才發明二進制。梁宗巨著《數學歷史典故》一書14~18頁對這一歷史公案有更加詳盡考察。[9];而目前有學者傾向於認為萊布尼茨二進制的體系確源於伏羲八卦圖,萊布尼茨還閱讀過1660年斯比賽爾出版的《中國文史評析》,其中亦有對《易經》和八卦的介紹。[10] 萊布尼茲認為易經的卦象肯定了他所信仰的基督教的共相[11]一切數都可以用0和1創造出來,在萊布尼茲看來,這正象徵了基督教《聖經》所說的上帝從「無」創造「有」(creatio ex nihilo)。

(有一個概念)不容易傳授給異教徒:全能的上帝從無創造有。現在我們可以說,數字的起源是世上能最好展示和說明這種力量的事物,它以「一」和「零」或者說「無」的形式呈現,既樸素又簡練。

——萊布尼茨寫給魯道夫·奧古斯都公爵的信[11]

後來的發展

 
喬治·布爾

1854年,英國數學家喬治·布爾發表了一篇里程碑式的論文,其中詳細介紹了一種代數化的邏輯系統,後人稱之為布爾代數。他提出的邏輯演算在後來的電子電路設計中起基礎性作用。[12]

1937年,克勞德·香農麻省理工大學完成了其電氣工程碩士學位論文,用繼電器和開關實現了布爾代數和二進制算術運算。論文題為《繼電器與開關電路的符號分析》(A Symbolic Analysis of Relay and Switching Circuits)[13],其中香農的理論奠定了數字電路的理論基礎。香農憑這篇論文於1940年被授予美國阿爾弗雷德·諾貝爾協會美國工程師獎。哈佛大學的哈沃德·加德納稱,香農的碩士論文「可能是本世紀最重要、最著名的碩士學位論文」。

1937年11月,任職於貝爾實驗室的喬治·斯蒂比茲[14]發明了用繼電器表示二進制的裝置。它是第一台二進制電子計算機。

運算規則

四則運算

  • 加法:0+0=0,0+1=1,1+0=1,1+1=10
  • 減法:0-0=0,1-0=1,1-1=0,10-1=1
  • 乘法:0×0=0,0×1=0,1×0=0,1×1=1
  • 除法:0÷1=0,1÷1=1

拈加法

二進制的一種特殊的算法,稱為拈加法。進行拈加法時,與進行加法無異,只是不需進行進位,即是逐位XOR。與博弈論的關係,見尼姆遊戲 § 數學理論

不同進位數轉換

十進制化為二進制

整數部分,把十進制轉成二進制一直分解至商數為0。讀餘數從下讀到上,即是二進位的整數部分數字。[15]

小數部分,則用其乘2,取其整數部分的結果,再用計算後的小數部分依此重複計算,算到小數部分全為0為止,之後讀所有計算後整數部分的數字,從上讀到下。

將59.25(10) 轉成二進制:

  1. 整數部分:
    59 ÷ 2 = 29 ... 1
    29 ÷ 2 = 14 ... 1
    14 ÷ 2 =  7 ... 0
     7 ÷ 2 =  3 ... 1
     3 ÷ 2 =  1 ... 1
     1 ÷ 2 =  0 ... 1
    
  2. 小數部分:
    0.25 × 2 = 0.5 ... 0
    0.50 × 2 = 1.0 ... 1
    

所以: 

也可以公式來計算:

           59.2510 = 101*10101+1001*10100+10*1010-1+101*1010-2
                   = 101*1010+1001+10/1010+101/1010/1010
                   = 110010+1001+(10+0.1)/1010
                   = 111011+0.01
                   = 111011.01

二進制化為十進制

將1001012轉換為十進制形式如下:

1001012 = [ ( 1 ) × 25 ] + [ ( 0 ) × 24 ] + [ ( 0 ) × 23 ] + [ ( 1 ) × 22 ] + [ ( 0 ) × 2 ] + [ ( 1 ) × 1 ]
1001012 = [ 1 × 32 ] + [ 0 × 16 ] + [ 0 × 8 ] + [ 1 × 4 ] + [ 0 × 2 ] + [ 1 × 1 ]
1001012 = 3710
十進制 0 1 2 3 4 5 6 7 8 9 10
二進制 0 1 10 11 100 101 110 111 1000 1001 1010
十進制 11 12 13 14 15 16 17 18 19 20 21
二進制 1011 1100 1101 1110 1111 10000 10001 10010 10011 10100 10101
十進制 22 23 24 25 26 27 28 29 30 31 32
二進制 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 100000
十進制 33 34 35 36 37 38 39 40 41 42 43
二進制 100001 100010 100011 100100 100101 100110 100111 101000 101001 101010 101011

二進制化為八進制

把二進制化為八進制也不是很難,因為八進制以8為基數,8是2的冪(8=23),因此八進制的一位恰好需要三個二進制位來表示。八進制與二進制數之間的對應就是上面表格中十六進制的前八個數。二進制數000就是八進制數0,二進制數111就是八進制數7,以此類推。

八進制 二進制
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

八進制轉為二進制:

  • 658 = 110 1012
  • 178 = 001 1112

二進制轉八進制:

  • 1011002 = 101 1002 (三位一組) = 548
  • 100112 = 010 0112 (用零填充 (密碼學),三位一組) = 238

八進制化為十進制

遵循二進制化為十進制的方法即可。所不同的是每一位乘上一個底數為8的

  • 658 = (6 × 81) + (5 × 80) = (6 × 8) + (5 × 1) = 5310
  • 1278 = (1 × 82) + (2 × 81) + (7 × 80) = (1 × 64) + (2 × 8) + (7 × 1) = 8710

表示實數

非整數可以借負指數冪表示;只要用基數點(十進制中,就是小數點)把負指數冪表示的部分隔開即可。例如,二進制數11.012

1 × 21 (1 × 2 = 2)
1 × 20 (1 × 1 = 1)
0 × 2−1 (0 × 12 = 0)
1 × 2−2 (1 × 14 = 0.25)

就是十進制數字3.25。

所有二進分數 都對應一個「有窮」二進制數字——這一二進制表示的小數部分位數有限。其他有理數也有二進制表示,但不是有窮的,而是出現循環,即某個有限序列出現無數次。例如

  =   = 0.01010101012
  =   = 0.10110100 10110100 10110100...2

在其他基數的計數系統中,有理數的表示也是有窮或循環的。另一相似之處在於,如果我們有一個有窮表示,那麼它還會有其他的表示方式,例如幾何級數2−1 + 2−2 + 2−3 + ...的和既是1,也是0.111111...。

無限不循環二進制小數表示的是無理數。例如,

  • 0.101001000100001000001000000…有某種模式,但循環節長度不固定,所以是無理數。這個數的數值為 [16],其中 Θ函數
  • 1.0110101000001001111001100110011111110…是2的平方根 的二進制表示,也是一個無理數。它沒有可以看出的模式。參見無理數

參考資料

  1. ^ binary. 樂詞網. 國家教育研究院.  (繁體中文)
  2. ^ binary. 術語在線. 全國科學技術名詞審定委員會.  (簡體中文)
  3. ^ 法語:Explication de l'arithmétique binaire, qui se sert des seuls caractères 0 et 1 avec des remarques sur son utilité et sur ce qu'elle donne le sens des anciennes figures chinoises de Fohy
  4. ^ 没有乘法口诀表将会怎样:古巴比伦乘法和古埃及乘法. Matrix67的博客. [2016-07-08]. (原始內容存檔於2020-08-15). 
  5. ^ Sanchez, Julio; Canton, Maria P. Microcontroller programming: the microchip PIC. Boca Raton, Florida: CRC Press. 2007: 37. ISBN 978-0-8493-7189-9. 
  6. ^ Stakhov, Alexey; Olsen, Scott Anthony. The mathematics of harmony: from Euclid to contemporary mathematics and computer science. 2009. ISBN 978-981-277-582-5. 
  7. ^ Bender, Andrea; Beller, Sieghard. Mangarevan invention of binary steps for easier calculation. Proceedings of the National Academy of Sciences. 16 December 2013, 111 (4): 1322–1327. PMC 3910603 . PMID 24344278. doi:10.1073/pnas.1309160110 . 
  8. ^ Bacon, Francis. The Advancement of Learning. London: Chapter 1. 1605 [2022-12-07]. (原始內容存檔於2017-03-18). 
  9. ^ 数学科普:常识性谬误令人忧. [2011-05-10]. (原始內容存檔於2011-12-19). 
  10. ^ 參見:萊布尼茨二進制與伏羲八卦圖考.胡陽,李長鐸.上海:上海人民出版社.2006.google book頁面存檔備份,存於網際網路檔案館
  11. ^ 11.0 11.1 J.E.H. Smith. Leibniz: What Kind of Rationalist?. Springer. 2008: 415 [2016-07-14]. ISBN 978-1-4020-8668-7. (原始內容存檔於2020-07-27). 
  12. ^ Boole, George. An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities Macmillan, Dover Publications, reprinted with corrections [1958]. New York: Cambridge University Press. 2009 [1854] [2016-07-14]. ISBN 978-1-108-00153-3. (原始內容存檔於2010-05-28). 
  13. ^ Shannon, Claude Elwood. A symbolic analysis of relay and switching circuits. Cambridge: Massachusetts Institute of Technology. 1940 [2016-07-14]. (原始內容存檔於2008-07-04). 
  14. ^ 喬治·斯蒂比茲(George Stibitz ,1904-1995),美國,「數字計算機之父」。參見維基英文條目:George_Stibitz頁面存檔備份,存於網際網路檔案館
  15. ^ M Morris Mano; Michael D Ciletti. Digital design : with an introduction to the verilog hdl. 培生教育. 2013: 第22頁. ISBN 9780273764526. 
  16. ^ Sloane, N.J.A. (編). Sequence A190404 (Decimal expansion of   where T=A000217 (triangular numbers)). The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.