二进制

二进制（binary）在数学和数位电路中指以2为底数的记数系统，以2为基数代表系统是二进位制的。这一系统中，通常用两个不同的数字0和1来表示。数字电子电路中，逻辑门直接采用了二进制，因此现代的计算机和依赖计算机的设备里都用到二进制。每个数字称为一个位元（二进制位）或比特（Bit，Binary digit 的缩写）。

## 历史

现代的二进制记数系统由戈特弗里德·莱布尼茨于1679年设计，在他1703年发表的文章《论只使用符号0和1的二进制算术，兼论其用途及它赋予伏羲所使用的古老图形的意义》出现。与二进制数相关的系统在一些更早的文化中也有出现，包括古代的埃及、中国、印度以及太平洋岛原住民文明。其中，古代中国的《易经》尤其引起了莱布尼茨的联想。

<image>

### 埃及

古埃及的计数员使用两种不同的系统表示分数，一是埃及分数（与二进制记数系统无关），二是荷鲁斯之眼分数（叫这个名字是因为很多数学史家相信这个系统所采用的符号可以排列成荷鲁斯之眼，但这一点有争议）。荷鲁斯之眼分数是用来表示分数数量的谷物、液体等的二进制记数系统，在这一系统下，以赫卡特为单位的分数值表示成1/2、1/4、1/8、1/16、1/32和1/64等二进制分数的和。这一系统的早期形式可以在埃及第五王朝（约公元前2400年）的档案中找到，而发展完备的象形文字形式可追溯到埃及第十九王朝（约公元前1200年）。

古埃及做乘法的方式也与二进制数密切相关，约公元前1650年的莱因德数学纸草书中就能看到。这一计算方法中，要把1和乘数不断翻倍，按被乘数的二进制表示从左列选出相应的2的幂次，并将右列的数相加。

### 印度

印度学者平甲拉（公元前两世纪左右）通过二进制方法来研究韵律诗。他的二进制中用到的是长短音节（一个长音节相当于两个短音节），有些像摩尔斯电码。与西方的位置表示法不同，平甲拉的系统中，二进制是从右往左书写的。

### 太平洋岛原住民文明

在法属波利尼西亚的曼格雷哇岛，挪威卑尔根大学的人类学家Andrea Bender和Sieghard Beller发现，在曼格雷哇人的语言上，存在着一个似乎混合了十进制和二进制的数学系统。它先于西方几个世纪，为首个在欧亚大陆之外发展出的二进制算法。

### 莱布尼茨前的西方先驱

1605年，弗朗西斯·培根提出了一套系统，可以把26个字母化为二进制数。此外他补充道，这个思路可以用于任何事物：“只要这些事物的差异是简单对立的，比如铃铛和喇叭，灯光和手电筒，以及火枪和类似武器的射击声”。这对二进制编码的一般理论有重要意义。（参见培根密码）

1617年，苏格兰数学家约翰纳皮尔在其著作《Rabdologiae》（意为“筹算学”）描述了三类计算系统。其中，第六章描述了一种可以在方格棋盘上操作的二进制筹算方法。后世有学者评价此为“使用二进制算术作为计算辅助工具的开创性示例”、“在纳皮尔乏人问津的棋盘计算器中，埋藏着二进制数字系统最早期的应用之一”。

### 莱布尼茨和中国的《易经》

<image>

莱布尼茨关于二进制的论文全名是《论只使用符号0和1的二进制算术，兼论其用途及它赋予伏羲所使用的古老图形的意义》（1703年）。类似于现代二进制计数系统，莱布尼兹的系统使用0和1。下面是莱布尼兹的二进制记数系统的一个例子：

- 0 0 0 1 数值为$2^0$
- 0 0 1 0 数值为$2^1$
- 0 1 0 0 数值为$2^2$
- 1 0 0 0 数值为$2^3$

<image>

莱布尼兹认为易经中的卦象与二进制算术密不可分。莱布尼兹解读了易经中的卦象，并认为这是其作为二进制算术的证据。作为亲华派，莱布尼兹关注易经，并饶有兴致地注意到它的卦象与从0到111111的二进制数字有某种对应，并认为这种对应反映了中国的重大成就中展现的他所崇尚的数学哲学。莱布尼兹首次接触到易经是在与法国耶稣会传教士白晋的联系中。白晋1685年作为传教士前往中国。

长期以来，人们对莱布尼茨发明二进制是否受到了伏羲八卦的影响争议颇多。认为莱布尼茨未受伏羲八卦影响独立发明二进制的理由主要是莱布尼茨在1679年（与白晋首次通信的二十多年）就撰写了“二的级数”（De Progressione Dyadica）一文，郭书春在《古代世界数学泰斗刘徽》一书461页指出：“中国有所谓《周易》创造了二进制的说法，至于莱布尼茨受《周易》八卦的影响创造二进制并用于计算机的传说，更是广为流传。事实是，莱布尼兹先发明了二进制，后来才看到传教士带回的宋代学者重新编排的《周易》八卦，并发现八卦可以用他的二进制来解释。”因此，并不是莱布尼茨看到阴阳八卦才发明二进制。梁宗巨著《数学历史典故》一书14～18页对这一历史公案有更加详尽考察。而目前有学者倾向于认为莱布尼茨二进制的体系确源于伏羲八卦图，莱布尼茨还阅读过1660年斯比赛尔出版的《中国文史评析》，其中亦有对《易经》和八卦的介绍。

莱布尼兹认为易经的卦象肯定了他所信仰的基督教的共相。一切数都可以用0和1创造出来，在莱布尼兹看来，这正象征了基督教《圣经》所说的上帝从“无”创造“有”（creatio ex nihilo）。

（有一个概念）不容易传授给异教徒：全能的上帝从无创造有。现在我们可以说，数字的起源是世上能最好展示和说明这种力量的事物，它以“一”和“零”或者说“无”的形式呈现，既朴素又简练。

### 后来的发展

<image>

1854年，英国数学家乔治·布尔发表了一篇里程碑式的论文，其中详细介绍了一种代数化的逻辑系统，后人称之为布尔代数。他提出的逻辑演算在后来的电子电路设计中起基础性作用。

1937年，克劳德·香农在麻省理工大学完成了其电气工程硕士学位论文，用继电器和开关实现了布尔代数和二进制算术运算。论文题为《继电器与开关电路的符号分析》（A Symbolic Analysis of Relay and Switching Circuits），其中香农的理论奠定了数字电路的理论基础。香农凭这篇论文于1940年被授予美国阿尔弗雷德·诺贝尔协会美国工程师奖。哈佛大学的哈沃德·加德纳称，香农的硕士论文“可能是本世纪最重要、最著名的硕士学位论文”。

1937年11月，任职于贝尔实验室的乔治·斯蒂比兹发明了用继电器表示二进制的装置。它是第一台二进制电子计算机。

## 运算规则

### 四则运算

- 加法：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。读余数从下读到上，即是二进制的整数部分数字。

小数部分，则用其乘2，取其整数部分的结果，再用计算后的小数部分依此重复计算，算到小数部分全为0为止，之后读所有计算后整数部分的数字，从上读到下。

将59.25(10) 转成二进制：

- 整数部分：

```

59 ÷ 2 = 29 ... 1 29 ÷ 2 = 14 ... 1 14 ÷ 2 = 7 ... 0

```

7 ÷ 2 = 3 ... 1
3 ÷ 2 = 1 ... 1
1 ÷ 2 = 0 ... 1

```

```

- 小数部分：

```
0.25 × 2 = 0.5 ... 0
0.50 × 2 = 1.0 ... 1
```

所以：$59.25_{(10)}=111011.01_{(2)}$

也可以公式来计算：

```
           59.25<sub>10</sub> = 101*1010<sup>1</sup>+1001*1010<sup>0</sup>+10*1010<sup>−1</sup>+101*1010<sup>−2</sup>
                   = 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 × 2 = 0)｜加

1 × 2−2｜(1 × 4 = 0.25)

就是十进制数字3.25。

所有二进分数$\frac{p}{2^a}$都对应一个“有穷”二进制数字——这一二进制表示的小数部分位数有限。其他有理数也有二进制表示，但不是有穷的，而是出现循环，即某个有限序列出现无数次。例如

$\frac{1_{10}}{3_{10}}$ = $\frac{1_2}{11_2}$ = 0.0101010101…2

$\frac{12_{10}}{17_{10}}$ = $\frac{1100_2}{10001_2}$ = 0.10110100 10110100 ...2

在其他基数的计数系统中，有理数的表示也是有穷或循环的。另一相似之处在于，如果我们有一个有穷表示，那么它还会有其他的表示方式，例如几何级数2−1 + 2−2 + 2−3 + ...的和既是1，也是0.111111...。

无限不循环二进制小数表示的是无理数。例如。

- 0.101001000100001000001000000...有某种模式，但循环节长度不固定，所以是无理数。这个数的数值为$2^{-\tfrac{7}{8}}\theta_2\left(0;\tfrac{\sqrt 2}{2}\right)-1\approx 0.64163256...$

$\sum_{k>=1} (1/2)^{T(k)},\,$

其中$\theta_2$为Θ函数。

- 1.0110101000001001111001100110011111110...是2的平方根$\sqrt{2}$的二进制表示，也是一个无理数。它没有可以看出的模式。参见无理数。