# 解讀計算機編碼 :::success 人們對數學的加減運算可輕易在腦中辨識符號並理解其結果,但計算機做任何事都受限於實體資料儲存及操作方式,也就是說,計算機的實體只認得 `0` 和 `1`,卻不知道符號 `+` 和 `-` 在數學以及應用場域的意義,於是科學家和工程人員引入「補數」來表達人們認知上的正負數值,但您有沒有想過,為何「二補數」被電腦科學廣泛採用呢?背後的設計考量是什麼?本文嘗試從數學觀點去解讀編碼背後的原理,相信讀者一旦掌握後,會對電腦設計有更充分的認知。 ::: 本文改寫自 [dog250 的文章](https://blog.csdn.net/dog250/article/details/73381875),斟酌採繁體中文和台灣慣用語,並補充相關資訊 -- [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) ## 第一部分:二補數編碼 ### 數學在電腦的表現方式 數學是門高度抽象的學科,而電腦科學是這個學科的一種具體化的展現,後者顯然無法處理一些僅在抽象意義上存在的事物,比如無窮大、虛數之類的「數」。倘若我們將數學中的加法、乘法一類的運算,實作於電腦中,很快就會發現一個殘酷的事實:由於數學中的實數加法 (以及別的運算) 是建立在實數域上的,而實數域又是無限的,於是電腦僅能處理有限域的運算,因此必須給定一個範圍,一種方案是在這個範圍內保證運算的正確性,超出範圍的結果給出錯誤提示,然而這樣的計算機不是很完美,畢竟限制太多,也難以實現自動化。 人們把思路移向另一個方向:若能在有限的編碼上實現諸如實數運算那樣「無錯誤」運算,我們不需要凡事仰賴系統訊息,而是在任何情況下 (包括超出範圍) 都可得到一個「能夠自圓其說地正確」的結果,因此電腦採用在有限域上的加法運算後,再次模除操作,將結果控制在有限的範圍內。 ![](https://i.imgur.com/8RToxSi.png) > 這個時鐘計時方式使用了模數為 12 的模算數 計算機是基於模算數 ([modular arithmetic](https://en.wikipedia.org/wiki/Modular_arithmetic)) 來進行加法和乘法運算的,在實現編碼之前,必須有理論基礎。世界事物往往相對,有前就有後,有上就有下。數學也是如此,反向運算像是加法之於減法,乘法之於除法,函數之於反函數。正與反是能夠等量相消而,用等量相消的元素,稱作「反元素」:加法的反元素是負數 -x ,乘法的反元素是倒數 1/x ,函數的反元素是反函數 f^-1^ 。所謂的「元素」,視情況是指數值、是指函數、是指矩陣等等總稱。 對於加法,必須實現一個[阿貝爾群](https://en.wikipedia.org/wiki/Abelian_group),它要滿足交換率,擁有一個「零」,每個元素都存在一個「反元素」,相加後等於「零」,並結果也該在該群中,只要按照如此的規則設計一個編碼,那麼對於計算機而言就非常圓滿了,對於任何數字的加法,我們都不會得到一個「錯誤」,而是很實在的得到一個正確的結果,如果實數可表示在數軸上,那麼計算機處理的數就可以表示在一個圓環上。為了方便,以下將計算機表示數的範圍僅考慮成字節,現行計算機用 8 個位元組 (如 [x86_64](https://en.wikipedia.org/wiki/X86-64) 這樣的 64 位元硬體架構) 來表達數值的方式很常見。 :::success 模算數是個整數的算術系統,其中數字超過一定值後 (稱為「模」) 後會「捲回」到較小的數值。常見的應用是在 12 小時制,將一天分為 2 個以 12 小時計算的單位。假設現在 7 點,8 小時後會是 3 點。用一般的算術加法,會得到`7 + 8 = 15`,但在十二小時制中,超過十二小時會歸零,不存在「15 點」。類似的情形,若時鐘目前是 12 時,21 小時後會是 9 點,而非 32 點。如此模 12 的模算數系統中,12 和 12 本身同餘,也和 0 同餘,因此 12:00 的時間也可以稱為是 0:00,因為模 12 時,12 和 0 同餘。 [模算數總結](https://blog.sengxian.com/algorithms/mod-world) ::: ### 計算機為何如此編碼 用一個位元組可表示從 `00000000` 到 `11111111` 範圍內的 256 個數字,由於計算機編碼不區分有號和無號數,顧及和實數的一致性,我們將其視為有號數,這樣的話,負數和正數應該各佔一半,它們中間有一個 0,由於十進位數和二進位數僅僅是進位數的不同,不管在什麼數制下,`0` 都是不變的,那麼顯然需要將 `0` 編碼為 `00000000`。現在考慮一下這樣做的後果,8 位元二進位數的最小值被編碼為 `0`,那負數怎麼辦呢?畢竟沒有比 `0` 更小的數字了啊!想像一下,我們現在做的事為「編碼」,一個數字的編碼只是種表示方式,它真正的含義是其字面上的值,而不是編碼的值,比如說,我們可以將數字 `1` 編碼成 `0`,而將數字 `0` 編碼為 `123`,僅此而已。為表示負數,我們先從 `-1` 開始考慮,在字面上,`-1` 加上 `1` 就是 `0`,而 `1` 的二進位編碼就是 `00000001` (二進位和十進位僅僅數制不同,編碼正數和 `0` 當然就是完全按照字面意義進行數制轉換編碼的,編碼負數其實就是編碼一個符號 `-`),其最低位就是 1,根據二進位加法,要想 `x + 00000001` 的結果為 `00000000`,`x` 的值必定是 `11111111`,但是不對啊,8 位元的 `1` 和 `00000001` 加在一起是 `100000000` 而非 `00000000`,也就是說,結果是 9 位元,超出一個位元組的範圍。 不過沒關係,我們的前提是計算機只能表示 8 位元的數字,那麼最高位的 `1` 當然是溢位,我們得到的結果就是 `00000000`,因此 `-1` 的編碼就是 `11111111`,接下來 `-2` 呢?很顯然 `-2 + 1 = -1`,因此 `-2` 為 `11111110`,依次類推,我們得到的最小的負數為 `10000000`,為什麼呢?設想還能表示比它小 `1` 的負數 `x`,則 `x + 1 = 10000000`,這樣的話 `x` 的值就是 `01111111`,我們姑且將這個數看成是比 `10000000` 還小 `1` 的一個負數,接下來考慮一下正數,我們知道 `1` 的編碼是 `00000001`,`2` 的編碼是 `00000010`,依次類推,我們也得到了 `01111111` 這個數,這是因為計算機將它能表示的數字編碼在一個圓環上而不是一個數軸上,那麼 `01111111` 到底是正數還是負數呢?這時候考慮一下阿貝爾群的性質,如果將 `01111111` 編碼為負數,那麼它將和它的反元素相加結果為 `00000000`,既然計算機算術僅僅最後做了模除 (modulo) 操作,其它的群性質和實數域的是一樣的,因此 `01111111` 的反元素肯定是正數,我們求出它的反元素是 `10000001`,而這數是我們從 `-1` 開始的負數編碼推導出來的一個負數編碼,因此這樣的假設不正確,所以 `01111111` 必然屬於一個正數的編碼,它的十進位數是 `127`,它是計算機能表示的最大的整數,而 `10000000` 則是計算機能表示的最小的負數,它的十進位值是 `-128`。 :::success 模除運算 ([modulo operation](https://en.wikipedia.org/wiki/Modulo_operation)) 和餘數運算 (complementation) 兩者概念上有重疊,但又不完全一致。模除主要是用於電腦術語 (而隨著不同的程式語言亦有落差),餘數更多是數學概念。兩者主要區別是:在被除數和除數符號不同時,餘數的符號有所歧義。 :notes: modulo 音標 [ˈmɑdʒəlo],該詞彙衍生自拉丁語 至於 `%` 和 `div` 在 C/C++ 語言的執行結果,正負號要以被除數抑或除數為主,程式語言的標準一度變遷過: * ISO C90 / ISO C++98: `%` 是 implementation-defined,而 [div](http://www.cplusplus.com/reference/cstdlib/div/) 依據被除數的正負號; * ISO C99 / ISO C++11: 將 `%` 和 [div](http://www.cplusplus.com/reference/cstdlib/div/) 都依據被除數的正負號; 對 2 的 N 次方作模除運算,可得到以下等價快速解: (適用於正整數) > x % 2^n^ == x & (2^n^ - 1) [最佳化編譯器](https://hackmd.io/s/Hy72937Me) 可能會用此來改寫模除運算,而在 C 語言這樣仰賴被除數的正負號來決定最終模除運算結果,這樣的最佳化對於有號數就不再適用 (除非改為 `unsigned`) ::: ![](https://i.imgur.com/og4XXYc.png) 若最大的正數 `01111111` 加 `1` 會得到什麼結果呢?答案是 `10000000`,也就是最小的負數,這也是合理的,因為計算機將數字編碼在一個圓環上。既然計算機將數字編碼在一個圓環上,那如果我們將此圓環從 `10000000` 處劈開並拉直,將得到一個線段,上面編碼的數字從 `10000000` 開始是遞增的,直到 `01111111`。有這個形象化的概念之後,下面看一下加法的實質,一個數 `x` 在圓環上,另一個數 `y` 肯定也在圓環上,`x + y` 的計算過程則是維持 `x` 不變,將 `00000000` 到 `y` 的這一段圓弧 ar 摘下來,拼接到 `x` 處,最終的 ar 的終點處的編碼就是結果,事實上 ar 有兩種摘取方式:順時針和逆時針,不管哪種方式,最後結果落到同一處。計算機加法的結果左後按照圓環的周長作模除,並不是說先得到實數域的字面結果,然後再執行取模操作,而是按照前面設計的圓環,二進位加法最終的模除是自動進行的,本質上說這個「自動」是通過高位的溢位來達成。注意,我們現在討論的是編碼,而不涉及有無號數,具體有號還是無號,就看指令的解釋了,`10000000` 可以是有號的 `-128`,也可是無號的 `128`,同樣,`11111111` 可以是有號的 `-1`,也可以是無號的 `255`。 ### 模除和溢位 編碼和符號彼此無關,那麼模除運算是如何實作呢?設想 `250 + 10` 的操作,字面操作的結果是 `260`,可是計算機最大只能由 8 位來表示,因此按照無號數解釋最大也只能表示為 `11111111`,也就是 `255`,可是 `260` 和 `255` 還相差 `5`,顯然結果需要在 `255` 的基礎上再加上 `5`,根據剛才的形象化的圓環加法,加上 `5` 之後落到 `00000100` 這個位置,也就是十進位 `4`,這個 `4` 就是就是最後的結果,一個圓環的周長是 `256`,`4` 正好是 `260` 除以 `256` 的餘數,而取餘數就是模除。在電腦硬體上,這是通過溢位來實現的,`255` 的二進位表示為 `11111111`,它加上 `1` 之後就發生最高位溢位到第 9 位元,由於計算機只能表示 8 位元的數值,因此丟棄最高位,結果為 `[1]00000000` (:notes: ==[]== 範圍內的位元會被丟棄,本文皆用這樣的表達法),一切從 `0` 開始,再加上 `4`,結果就是 `4`。不管在這個圓環上繞幾圈,最終的落點都在圓環上,每繞一圈就會發生最高位的溢位,然後從 `00000000` 開始,這就是模除的實質。 對於乘法,這個圓環依然使用,兩個數相乘,只要有一個數是正數,那麼就可以用上述的圓弧不斷拼接來得到答案,比如 `3 * 2` 就是用 `2` 個 `3` 這個圓弧拼接兩次,`-2 * 4` 就是拿 `4` 個 `-2` 這個圓弧拼接四次,對於兩個負數相乘,比如 `(-a) * (-b)`,可拆成 `(a * b) * (- 1) * (-1)`,只需要計算 `(-1) * (-1)` 即可,也就是 `11111111 * 11111111`,最終的結果是 `[xxx]00000001`,高位全部溢位,結果就是正數 `1`,在實數乘法中,我們依靠一個「負負得正」規則,然而在計算機編碼中,負號本身和數值一起被編碼,依靠溢位竟可推導出「負負得正」這個所謂的規則,顯然,計算機是不能被「規定」的,只有在純抽象的領域才能規定,在計算機上,必須落實這個規則,將負號和數值一起編碼可解決這個問題,直接了當地推導出一切在實數域上的異號數值乘法的性質。 :::success 過往數學教育對「負負得正」通常先要求學生記住,學會計算後再來理解,卻造就一群對數學原理一知半解的學生。要充分理解「負負得正」背後的原理,需要不少推理。18 世紀法國作家 Stendhal (1783-1843) 對於授課教師「負負得正」的解釋顯然並不滿意。他回想從前學習負數的情況: > 數學是不會矯柔造作。在我的青春歲月裡,我相信那些使用數學做為工具的科學也必然真確;別人這麼告訴我。但是當我發現沒有人能解釋負負得正(`-` × `-` = `+`) 的原因時,你能想像我的感受嗎?!(而這還是所謂「代數」的一項基本規則)對我來說,這個沒有解釋的難題真是夠糟的了(它既然能導致正確的結果,無疑地也應該可以解釋)。而更糟的是,有人用那些顯然對自己都不清不楚的理由來對我講解。 德國數學家與教育家 [Felix Klein](https://en.wikipedia.org/wiki/Felix_Klein) 在 1908 年語重心長地說: > 如果我們現在帶著批判的眼光去看中學裡負數的教法,常常可以發現一個錯誤,就是像老一代數學家如上指出的那樣,努力地去證明記號法則的邏輯必要性。…… 我反對這種做法,我請求你們別把不可能的證明講得似乎成立。大家應該用簡單的例子來使學生相信,或有可能的話,讓他們自己弄清楚。 參考資訊: * [負負為何得正(上)](https://kknews.cc/zh-tw/education/rzapo4.html) * [負負為何得正(下)](https://kknews.cc/education/xrb6j9.html) ::: 加法和乘法都套入這個「圓環 + 溢位」模型之後,最後再來看一下 `0` 這個特殊的數字,在實數域上,`-x + x = 0` 也是個規定,一個群的性質,然而在計算機,它卻是被真實地實現的,也是依靠溢位,不失一般性,以 `-1 + 1` 為例,`1` 的編碼為 `00000001`,要想得到 `-1` 的編碼和 `1` 加和等於 `00000000`,同時又沒有對計算機的行為進行「規定」,根據二進位加法,只要能得到 `[x[y]]00000000` 即可,8 位元以上的部分不用理會,由於計算機只能表示 8 位元,超出 8 位元者全部溢位即可,比如 `11111111 + 00000001 = [1]00000000`,就這實現群性質中的數值和「反元素」相加等於「零」的這個性質。 ### 反思所謂的規則 教科書上經常說一補數、二補數之類的概念,還說計算機一律使用二補數編碼,正數和 `0` 的二補數等於原始正負號表示型態,負數的二補數等於負數相反數的原始正負號表示形態的一補數加 `1`。其實根本不用記憶這麼多規則,僅靠藉由上述的「圓環 + 溢位」模型就能說明一切,什麼一補數、二補數之類的概念根本就沒有必要引出來,之所以發展是為了符合科學精神,任何事物都要有概念,概念的導出是一個分析和綜合的過程,在形成概念之前必然需要歸納出一個一般結論,接下來才可以形成概念,由此可想像,當初的編碼設計者也是先想到了上述的「圓環 + 溢位」這個形象化的模型,進而才引出一補數、二補數這些抽象的概念的,有了具象模型,再解釋為何負數的二補數是其相反數的一補數加 1 就簡單多了。 首先我們要知道負數和其相反數相加等於 `00000000`,由於計算機沒被「規定」,而是實現了群的性質,因此這個 `00000000` 實際上應該是 `100000000`,溢位了一個 `1` 到第 9 位元,我們知道一個正數和該正數取反之後相加,會得到 `11111111` 這個數值,然再加上 `1` 則會得到 `[1]00000000` 這個所謂的 `0`,正整數的二進位編碼完全按照進位規格的轉換機制,由十進位 (或者其它進位) 數轉化而來,而負數由於需要編碼一個「負號」,因此它需要被改成別的,於是就由「去掉負號的該數按位取反然後加上 `1`」來表示負數,其中包含了兩個部分,第一部分是負號,第二部門為該負數的相反數。最終,表示負數的時候,其相反數就成了「原始的正負號表示形態」,得到負數編碼的中間步驟 —— 對每個位元進行反操作的結果顯然就是「一補數」,而結果加 `1` 則稱作「二補數」。為了一致性,正數的補數就是原始的正負號表示形態!按照有號資料解釋,所有的負數的最高位都是 1,而所有的正數最高位都是 0,因此最高位也就成了負號位,注意,負號 `-` 的編碼已經隱藏在「取相反數 - 逐位元取反 - 結果加 1」的整個過程之中,因此最高位雖然是符號位元,它卻不是負號 `-` 的編碼,你不能說負號的編碼是 `10000000`。 如果我們的學習過程不是先死背一補數、二補數這類概念,而是先探討上述「圓環 + 溢位」的模型,最後透過這個模型自然而然導出這些概念的話,或許很多人就不至於被搞得糊塗。文藝復興以來,西方科學精神風靡,要知道這種精神的本質和古代純思辨推理精神的本質只差那麼一點點,那就是「概念」要通過「現實的對應」來檢驗,任何概念都是通過歸納法再透過推理得到一般化表述,對於計算機編碼以及任何其它的工程學原理而言,熟悉這個歸納的過程是最重要的,要比你死背規則有用多了,唯有在你理解這個歸納的過程,再去深入這些概念才會覺得輕鬆,理解概念的目的是將知識體系化,而只要理解歸納的過程才能真正學會這個概念。 ### 簡易加 / 減法器電路方塊圖 二補數表示法的主要目標是允許我們能在單一電路中進行加減法運算。為此,我們需要一個接收 2 個二進位的輸入 $a$ 和 $b$,以及 input carry $c_{in}$,並計算 $a + b + c_{in}$ 的結果。下圖是二補數加 / 減法器的方塊圖,圖中,當 $Sub/\overline{Add}$ 的結果為 `0`,"Selective Component" 會將 `y` 傳入加法器的 b input 並將 $c_{in}$ 設為 `0`。因此,加法器的輸出即為 $a+b+c_{in}=x+y$。然而,當 $Sub/\overline{Add}=1$ 時,"Selective Component" 會將 y 的一補數傳入加法器的 b input,及圖中的 $y^{compl}$。且在這個情況中,$c_{in}$ 會設為 `1`。因此,加法器執行 $a+b+c_{in}=x+(y^{compl}+1)$ 的運算。在前面的章節,$y^{compl}+1$ 就是 $y$ 的二補數。所以,加法器實際上是進行 $x-y$ 的運算。 ![](https://www.allaboutcircuits.com/uploads/articles/Fig2m11142017.png) 參考資料: [Two’s Complement Representation: Theory and Examples](https://www.allaboutcircuits.com/technical-articles/twos-complement-representation-theory-and-examples/) ### 關於編碼的符號 C 語言中提供有號 (signed) 和無號 (unsigned) 兩種資料型態,其實這僅提示「如何解釋」這個資料型態,對於機械碼層次的編碼來說,不用區分正負號,比如 `11111111` 可解釋成無號數 `255`,也可解釋成有號數 `-1`。那麼 C 語言的關於有號和無號的資料型態給誰看呢?其實是給硬體指令 (instruction) 看的,指令負責解釋一個資料是有號的還是無號的。與大部分人的想像不同,會區分有號數或無號數的指令非常少,按照直覺判斷,每個算術指令都該提供兩套才對,一套針對有號數,另一套針對無號數,實際沒有必要。因為計算機的數值編碼不區分正負號,甚至沒有大小,==完全是個封閉的阿貝爾群==,兩個數相加前怎麼解釋,它們的和就怎麼解釋,因此完全沒必要設計兩套指令,加法的過程完全符合正文中的圓弧拼接法則。本文假設計算機最多用 8 位編碼資料,然而如今的計算機可用 8 位元、16 位元、32 位元,乃至於 64 位元等不同的位元數來編碼資料,那就涉及到「將一個 `x` 位元的資料放到一個 `y` 位元的空間中」這類操作。 在計算機中,實際上每種資料都表示一個圓環,假設系統中有 8 位元、16 位元、32 位元三種資料的話,系統中就有三個圓環,只有將一個資料從一個圓環放到另一個圓環的指令才會考慮符號,比如現有 8 位元編碼為 `11111111`,現將其放入 16 位元的圓環中,如果它是無號數,顯然它是 `255`,因此 16 位元編碼為 `000000011111111`,然而如果它是有號數,那麼它就是 `-1`,它的 16 位元編碼就是 `1111111111111111`,可見放到 16 位元圓環中的位置是不同的,因此只有在此情況下才需要考慮符號,故計算機硬體在這種情況下提供了指令組,例如 Intel x86 的 [movzx](https://www.felixcloutier.com/x86/MOVZX.html) 和 [movsx](https://www.felixcloutier.com/x86/MOVSX:MOVSXD.html) 這兩道指令,在同一圓環上進行的運算根本沒有必要考慮符號,因此也就不需要提供兩套指令。 --- ## 第二部分 圖解有限長度二進位運算與二補數編碼 ### 準備工作 計算機無法表示整個抽象的實數域,我們實際使用的計算機是現實的,而非抽象的,計算機可以表示的數字是有固定長度的,比如 4 bit, 8 bit, 16 bit, 32 bit 等等。為了簡單起見,本文接下來以 4 位元為例進行講解,首先我們定義一個初始值,`0000`,然後讓其不斷加 `1`,看看最後會發現什麼: **0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111,?** 到 `1111` 後,再加 `1` 會怎樣?很顯然,再加 `1` 的話會變成 `10000`,然而我們假設我們只能表示 4 bit 的資料,那麼最高的第 5 位元的 `1` 將會溢位而被丟棄,所以最終的結果是 `1111 + 0001 = 0000`.    於是我們就有了下面的序列: **0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 0000, 0001, 0010......** 也就是說,無論怎麼加 `1`,加多少個 `1`,4 個 bit 的二進位數,只能表示 16 個元素,它們構成一個集合: **{0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111}** ### 時鐘上的運算 是不是很像我們平時看到的時鐘呢?我們的時鐘上有 12 個刻度,當指針指向 12 的時候,接下來沒有 13,而是重新從 1 開始,只不過在我們的 4 bit 例子中,刻度為 16 個,其它的都一樣: ![](https://i.imgur.com/ONhgmUV.png) 雖然我們是以 4 bit 作為例子,但這並不失一般性,其實哪怕是 64 bit 的資料,也是一樣的道理,除了我這裡無法給出圖示 ### 時鐘加法的物理含義 在徹底理解時鐘加法的物理含義之前,我們先看一下在這個鐘錶式的刻度盤上如何表示一個任意的 4 bit 集合中的數 a。很簡單,a 的物理含義就是從刻度 `0000` 作為起點,刻度 a 最終終點的一段圓弧: ![](https://i.imgur.com/x80FSAz.png) 現在假設兩個數相加,加數分別是 `x` 和 `y`,那麼 `x + y` 的物理含義就是,`x` 維持不變,順時針移動圓弧 `y`,直到圓弧 `y` 的起點與圓弧 `x` 的終點重合,即將圓弧 `y` 的起點順時針移動到圓弧 `x` 的終點,設移動後的圓弧為 `y'`: ![](https://i.imgur.com/b6HWhrq.png) 這樣,`y’` 的終點就是 `x + y` 的結果。 OK,這很容易,不是嗎? ### 時鐘減法的物理含義 理解了加法,我們再來看看時鐘減法的物理含義。 現在假設兩個數相減,`x - y` 的物理含義相比加法來講略微複雜,它分為兩步操作: 1. 先將圓弧 `y` 逆時針旋轉,使其終點移動到 `0000` 的位置,並翻轉其方向【翻轉的含義在於始終保持圓弧的起點位置與 `0000` 重合】,設新的圓弧為 `y’` ![](https://i.imgur.com/tLOwiib.png) 2. 然後再將圓弧 x 逆時針旋轉,使其起點 0000 移動到圓弧 y’ 的起始位置,設新的圓弧為 x’: ![](https://i.imgur.com/kHV4jTt.png) 這樣 `x’` 的終點就是 `x - y` 的結果。   然而為了統一起見,我們用哥倫布航海的思路達到同樣的目標,即將圓弧 `x` 和圓弧 `y` 順時針旋轉而非逆時針旋轉,達到同樣的效果。依然分兩步: 1. 先將圓弧 `y` 順時針旋轉,使其終點和 `0000` 重合,並翻轉起點和終點,設為圓弧 `y’`,作為基調: ![](https://i.imgur.com/rdaJWa4.png) 2. 再將圓弧 x 順時針旋轉,使其起點和圓弧 y’ 的終點重合,設為 x’: ![](https://i.imgur.com/oloCGDz.png) 圓弧 `x’` 的終點就是結果!只看上面的步驟 2,你就會發現,這個和上一小節講的加法物理意義是一致的,即都是「移動一條圓弧,使其起點與另一條圓弧的終點重合」,我們把逆時針旋轉全部統一成了順時針旋轉,這就是把減法全部統一成了加法,即將 `x - y` 轉換為了 `x + (-y)`。   也許你要問,第一步中為啥要反轉起點和終點呢?因為在加法中,任何圓弧的起點都是 `0000`,換句話說,你把一段圓弧理解成一個在「時鐘坐標系」中以 `0000` 為起點的一個向量就好了。 ## 階段性總結 到目前為止,我們理解了在這個時鐘上的加法和減法運算的物理意義,總結來說: * 加法就是順時鐘圓弧拼接; * 減法就是逆時針圓弧拼接; * 由於時鐘錶盤是個圓,按照哥倫布航海的思路,從一個方向能到的地方,從另一個方向也能到。 至今尚未涉及任何關於二進位和編碼,待我娓娓道來。 ### 阿貝爾群對稱性 `–x` 與 `-x` 在時鐘上的表示 接下來我們來談之前略過的阿貝爾群,並從數學上的「[群](https://zh.wikipedia.org/wiki/%E7%BE%A4)」(groups) 探討起。「群」的概念來自於多個領域,像是數論、代數方程、幾何。 簡單來說,群就是一組元素的集合,在集合中每兩個元素之間,定義了符合一定規則的某種運算規則。以下將九九乘法表簡化為「四四乘法表」: | x | 1 | 2 | 3 | 4 | | - |:-:|:-:|:--:|:--:| | 1 | 1 | 2 | 3 | 4 | | 2 | 2 | 4 | 6 | 8 | | 3 | 3 | 6 | 9 | 12 | | 4 | 4 | 8 | 12 | 16 | > 四四乘法表 我們再將個別元素除以 5 取餘數,得到以下表格: | x | 1 | 2 | 3 | 4 | | - |:-:|:-:|:-:|:-:| | 1 | 1 | 2 | 3 | 4 | | 2 | 2 | 4 | 1 | 3 | | 3 | 3 | 1 | 4 | 2 | | 4 | 4 | 3 | 2 | 1 | > 對「四四乘法表」個別元素除 5 取餘數 不難發現上表有個有趣的特性:它的每一列都是由(1、2、3、4)這四個元素組成,每一行中四個數全有,但也不重複,只是改變順序。這特性乍看之下沒什麼特別,但數學家 Euler 發現,並非對於每個 $n$ 用這方法構成的乘法表都具有這個性質,而是若且唯若 $n$ 是質數時,$(n-1)$ 個元素的餘數表才具備此特性。這個有關質數的結論對 Euler 證明費馬小定理頗有啟發。 費馬小定理是數論中的一個定理:假如 $a$ 是個整數,$p$ 是一個質數,那麼 ${a^{p}-a}$ 是 $p$ 的倍數,可表示為 ${a^{p}\equiv a{\pmod {p}}}$ 如果 a 不是 p 的倍數,這個定理也可以寫成 ${a^{p-1}\equiv 1{\pmod {p}}}$ 費馬小定理是 Euler 定理的一個特殊情況:如果 $n$ 和 $a$ 的最大公因數是 $1$,那麼 ${a^{\varphi (n)}\equiv 1{\pmod {n}}}$ 這裡 φ(n) 是 Euler 函數。Euler 函數的值是所有小於或等於n的正整數中與 n 互質的數的個數。若 $n$ 是個質數,則 φ(n) = n-1,即費馬小定理。 以現今群論的說法,上表的 4 個元素,構成了一個「群」,因為這 4 個元素兩兩之間定義了一種乘法 (本例是整數相乘再求 5 的餘數),並且滿足群的以下 4 個基本要求: 1. 封閉性: 兩元素相乘後,結果仍然是群中的元素。本例顯然存在此特性; 2. 結合律: `(a * b) * c = a * (b * c)`,整數相乘滿足結合律; 3. 單位元素: 存在單位元素,與任何元素相乘,結果不變。本例中對應於元素 `1`; 4. 反元素 (也稱「逆元」): 每個元素都存在反元素,元素與其反元素相乘,得到單位元素。也能在本例發現此特性; Euler 研究數論時,有了「群」的模糊概念,但「群」這個名詞以及基本設想,卻是首先在法國數學 Évariste Galois 研究方程理論時所提出,他在短短 20 年生命中所作的最重要的工作,就是開創建立「群論」這個無比重要的數學領域。說到方程可解性,又牽扯到另外一位也是年紀輕輕就去世了的挪威數學家 Niels Abel。 中學數學告訴我們,一元二次方程式 ax^2^ + bx + c = 0 的求根公式為: ![](https://i.imgur.com/GfqVyuF.png) 對於 3 次和 4 次的多項式方程式,數學家們也都得到了相應的一般求根公式,也就是由方程式的係數及根式組成的「根式解」,數學家歷經幾百年卻無法得到 5 次多項式方程式的一般解,所有的努力都以失敗告終,這使得阿貝爾有了另一個念頭:也許包括 5 次方程式在內的所有次數大於 4 的方程式,根本不存在統一的根式解。 Galois 從研究多項式的方程式理論中發展出群論,又巧妙地用群論的方法解決了一般代數方程式的可解性問題。Galois 的思想大致是:每個多項式都對應於一個與它的根的對稱性有關的置換群,後人稱之為「Galois 群」。下圖是個簡單置換群 S~3~ 的例子。一個方程有沒有根式解,取決於它的 Galois 群是否為可解群。 ![](https://i.imgur.com/giG50Fn.png) 在上圖的置換群 S~3~ 中,給定 3 個字母 ABC,它們能被排列成如上圖右邊的 6 種不同的順序。也就是說,從 ABC 產生 6 種置換構成的元素。這 6 個元素按照生成它們的置換規律而分別記成 `(1)`, `(12)`, `(23)` ... 括號內的數字表示置換的方式,比如 `(1)` 表示不變,`(12)` 的意思就是第 1 個字母和第 2 個字母交換等等。 不難發現,這 6 個元素在上圖的乘法規則之下,滿足上面談及的定義「群」的 4 個特性,進而構成一個群。這裡的「乘法」不是尋常用語的整數間乘法,而是兩個置換方式的連續操作。上圖右方還標示出 S~3~ 一個特別性質:其中定義的乘法不可交換。如上圖右方所示,`(12)` 乘以 `(123)` 得到 `(13)`,而當把它們交換變成 `(123)` 乘以 `(12)` 時,卻得到不同的結果 `(23)`,因此,S~3~ 是種不可交換的群,或稱之為「非阿貝爾群」,反過來說,像上面對個別元素除 5 取餘數的「四四乘法表」裡頭的元素的可交換群,被稱之為「阿貝爾群」。S~3~ 有 6 個元素,是元素數目最小的非阿貝爾群。 整體整數 (..., -4, −3, −2, −1, 0, 1, 2, 3, 4, ...) 的加法就構成一個「離散但無限」的群。因為兩個整數之和仍然是整數 (符合封閉性),整數加法符合結合律;`0` 加任何數仍然是原來那個數(0 就是單位元素),任何整數都和它的相應負整數抵消 (比如 `-3` 是 `3` 的反元素)。全體整數在整數乘法下卻並不構成「群」。因為整數的反元素不是整數,而是一個分數,所以不存在反元素,違反前述群的 4 個特性,不能構成群。 Galois 引入「群」這個述語時,主要考慮的是五次以上方程式解法的問題,但今天它的應用場景遠超越了當初設想,主要因為後來人們意識到,群論的最大用途是關於「對稱性」的研究:所有具有對稱性質,群論都可派上用場。 只要發生變換後仍有什麼東西還維持不變,那它就是對稱的。幾何體當然可以是對稱:一個圓左右翻轉後還是圓,旋轉 180 度後還是圓,所以它在這兩種變換下是對稱的。對稱性也適用於非幾何體的抽象概念,考慮到 f(x, y, z) = x^2^ + y^2^ + z^2^ 這個函數,無論我們如何調換 x, y, z 的位置,都是不變的;或者 sin(t),用 (t + 2π) 代替 t,也是不變的。它們也都具有相應的對稱性。 ![](https://i.imgur.com/RdzpZSQ.png) > 就連魔術方塊也是個「群」:魔術方塊中的小方塊可以看作群眾的元素,轉動方塊相當於運算,因此魔術方塊的公式可由群論得出 前述數學的對稱性質竟然和物理世界中的守恆可一一對應,例如物理學定律是不因時間的流逝而改變,換言之,它在時間變換下對稱,這個對稱性可直接推導出物理學中的能量守恆。物理學定律也不隨著空間的位置而改變,這個對稱性質又能推出另一條同樣關鍵的動量守恆。每個物理上的守恆量必然伴隨著數學上的對稱性,這是[傑出女性數學家 Emmy Noether](https://www.thenewslens.com/article/70724) 所發現。現代粒子物理學依賴著群論,種類繁多的新粒子之所以能被整齊歸入標準模型,歸功於對稱性質的研究。 透過對時鐘加法及減法物理意義的理解,我們知道 `x` 和 `-x` 的表示法可用下圖呈現: ![](https://i.imgur.com/4RiQFpt.png) 在數學上,我們知道 `-x` 是 `x` 的相反數,`x + (-x)` 的結果是 `0`,按照上述的物理意義去操作,我們可以很顯然看到這點。上面展示的這個 4 bit 所能表示的 16 個元素的集合就是一個阿貝爾群,確切的說是一個有限群,因為它只有有限的 16 個元素,它滿足以下的性質: * 在集合中 `x` 及 `y` 彼此之和 `x + y` 依然在集合中,這個已透過上述時鐘加法一目了然; * 集合中存在一個 0 元,即 `0000`,滿足任意的 `x` 與其相加均等於 `x` 本身:`x + 0000 = x`; * 集合中任意一個元素 `x` 均有一個反元素 `-x`,滿足 `x + (-x) = 0000`; * 集合中任意兩個元素 `x`,`y` 之和滿足交換律,即 `x + y = y + x` 這意味著,任何元素 `x` 的相反數(群加法裡的反元素即相反數,0 元為 `0`;群乘法的反元素即倒數,0 元為 `1 - x` 在時鐘圓弧表示上均相對 `0000` 點對稱,二者的加和為 `0000`,這個不再贅述。 這裡我們理解到一個群對稱性,即一個值和它的相反數關於 `0000` 對稱,顯然 `0000` 的相反數是它本身,這是阿貝爾群的性質決定的。 接著終於要探討二進位編碼,我們為上述的物理操作賦予二進位的意義。 ### 二進位編碼對稱性:一補數表示法 我們將 4 bit 能表示的所有數刻在那個時鐘上,再次展示出本節最初的那個圖: ![](https://i.imgur.com/8MzlIw0.png) 實際上任意長度 bit 的二進位都可以刻在那個時鐘上。不失一般性,我們仍以 4 bit 來討論。   我們知道 4 bit (任意長度的 bit) 能表示的數值個數為偶數個,這個不解釋。而且我們知道它們的極端在哪裡,一個極端是 `0000`,另一個極端是 `1111`,對於任意長度 bit 表示的數,極端永遠都是 `00...00` 和 `11...11`,一個全 `0`,一個全 `1`。如果我們把它們順序排在鐘錶上,拿 `1111` 做二進位遞減,拿 `0000` 做遞增,很顯然它們成對的兩個值按位或的結果都是 `1111`: ![](https://i.imgur.com/wjtA4xL.png) 因此我們得到了另一個對稱性,即一補數對稱性,和阿貝爾群對稱不同,0000 的一補數對稱是 1111,而不是它本身,因此它的對稱軸線與阿貝爾群對稱軸線有偏差: ![](https://i.imgur.com/qDNZn9M.png) 這一切 ``` 0+(-0)=0 —> 0000 + 0000 = 0000 1+(-1)=0 —> 0001 + ?1 = 0000; 2+(-2)=0; —> 0010 + ?2 = 0000; ...... ``` 上述的 `?x` 該是多少?我們從上一小節的兩種對稱性的對比就能知道答案!   很顯然,`?1` 就是 `1110`,而 `?2` 就是 `1101`,就是與固定加數在關於群對稱位置的另一個值。然而我們怎麼去定義它?!這是關鍵!總不能每次都擺出這個錶盤來,正確的科學的做法是找出一個規律,然後以此規律做出定義,也許這個定義沒有任何物理含義,但它是必要的,僅為定義。 我們發現上述兩種物理意義對稱(群對稱和一補數對稱)的對稱軸僅僅偏差 0.5,因此便可以定義二補數了,即一個數字在時鐘上位置關於 `0000` 群對稱的位置就是其二補數,它恰好表示為該數值關於一補數對稱軸對稱的位置所表示的值加上 `0001`: ![](https://i.imgur.com/iLzDl40.png) 然而這個二補數只是個狹義的二補數,為了更加不失一般性,將概念提升,規定在一補數對稱軸右邊的數值編碼的二補數是其本身,而一補數對稱軸左邊的數值編碼的二補數為其位置編碼加 1,因為: 1. 按照阿貝爾加法群,`x` 與 `-x` 的和必須是 `0000`,`0000` 的對稱數值為其本身 `0000`; 2. 按照一補數對稱,`0000` 的對稱位置為 `1111`,不再是 `0000`,它和其本身相差 `0001`。 關於一補數,二補數的概念就是這麼簡單,關於為什麼二補數是一補數加 1,通過上面的圖解應該可以看出本質了,就是兩種對稱的不相容問題,事實上,彼此是相容的,但為什麼呢? ### 回歸現實 讓我們回頭檢視現實世界。 -4, -3, -2, -1, 0, 1, 2, 3, ... 誰是誰的一補數?貌似是個簡單的問題。如果沒有一補數,何談二補數? 按照二進位的方法,-3 的二補數是什麼?是 -4 嗎?是 -2 嗎?其實都不是! 直接給出結論,扣除二進位,別的進位系統不存在一補數,這要從狀態談起。所謂一補數就是非此即彼,0 和 1 正好有這個特質。我們看十進位,與 `0` 相 「反」 的是 `1`, `2`, `3`, `4`, `5`, `6`, `7`, `8`, `9`,到底是哪一個是不確定的,所以在十進位裡,數值是沒有一補數的,既然沒有一補數,也就不存在「一補數對稱軸」了。 不存在對稱軸,也就沒法定義操作嗎?非也! 我們可以在群環域裡定義所有的這些!然而你知道為什麼在實數域裡不存在「二補數等於一補數加 1 」這種命題嗎?因為實數域不需要編碼!因為實數域的處理者是人的大腦,而非凡事都要考慮到有效儲存位元數的計算機,所以人可動用任何抽象的邏輯思維來搞定這一切。當有人說出 `1.234` 這個數的時候,人腦並不需要對其進行固定格式的編碼就可以理解這個數字的含義,這就是本質。 編碼的存在到底為了什麼?編碼是為了處理現實世界資料而發展出來。然而在抽象世界,根本就不需要編碼,或者說編碼本身就是抽象的。 「定義一個數」和「表示一個數」是完全不同的概念,定義一個數是抽象的,而表示一個數則不然,數學可以定義一個數,但是要表示一個數,即必然借助人腦或者計算機,而人腦和計算機對數的表示有所有不同,基本就是這樣。 對於到底是先學定義還是先學表示重要,這裡傾向於要先學會定義,你要先理解群,環的概念,才可能知道「負負得正」是必然,才會知道很多自認為神奇之處,其實是定義之內就可以推導出來的結論,然而若你侷限於表示法的形式而不思考背後原理,那你將錯過能夠駕馭電腦科學的 [原力](http://www.catb.org/jargon/html/U/UTSL.html)。 ---