二进制

進位記數系統
(重定向自二進位制

二進制[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.