二进位

**二進制**（**binary**）在數學和數位電路中指以 2 為底數的記數系統，以 2 為基數代表系統是二進位制的。這一系統中，通常用兩個不同的數字 0 和 1 來表示。數字電子電路中，邏輯閘直接採用了二進制，因此現代的計算機和依賴計算機的裝置裡都用到二進制。每個數字稱為一個位元（二進制位）或位元（Bit，Binary digit 的縮寫）。

## 歷史

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

　

### 埃及

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

### 印度

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

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

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

### 萊布尼茨前的西方先驅

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

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

萊布尼茨關於二進位的論文全名是《論只使用符號 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}$

萊布尼茲認為易經中的卦象與二進位算術密不可分。萊布尼茲解讀了易經中的卦象，並認為這是其作為二進位算術的證據。作為親華派，萊布尼茲關注易經，並饒有興致地注意到它的卦象與從 0 到 111111 的二進位數位有某種對應，並認為這種對應反映了中國的重大成就中展現的他所崇尚的數學哲學。萊布尼茲首次接觸到易經是在與法國耶穌會傳教士白晉的聯絡中。白晉 1685 年作為傳教士前往中國。
長期以來，人們對萊布尼茨發明二進位是否受到了伏羲八卦的影響爭議頗多。認為萊布尼茨未受伏羲八卦影響獨立發明二進位的理由主要是萊布尼茨在 1679 年（與白晉首次通訊的二十多年）就撰寫了「二的級數」（De Progressione Dyadica）一文；而目前有學者傾向於認為萊布尼茨二進位的體系確源於伏羲八卦圖，原因在於 1687 年萊布尼茨看過柏應理的《這個哲學家孔子》，書中便有伏羲八卦次序圖、方點陣圖和周文王六十四卦圖。此外，萊布尼茨還閱讀過 1660 年斯比賽爾出版的《中國文史評析》，其中亦有對《易經》和八卦的介紹。
此外，萊布尼茲認為易經的卦象肯定了他所信仰的基督教的共相。一切數都可以用 0 和 1 創造出來，在萊布尼茲看來，這正象徵了基督教《聖經》所說的上帝從「無」創造「有」（creatio ex nihilo）。

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

### 後來的發展

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) 轉成二進制：

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.25_{(10)}=111011.01_{(2)}$

也可以公式來計算：

```
           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**

### 二進位化為八進位

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

八進位轉為二進位：

* 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：

　
:

就是十進位數位 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 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...$ ，其中 $\theta _{2}$ 為 Θ 函式。
* 1.0110101000001001111001100110011111110… 是 2 的平方根 ${\sqrt {2}}$ 的二進位表示，也是一個無理數。它沒有可以看出的模式。參見無理數。

## 參考資料