二进制

進位記數系統

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