Intro

上一篇里我們已經知道了數據怎么表示，現在，我們該來使用這些數據做一點有用處的事情了。

二元布爾代數

上一篇中我們已經重復強調了，計算機只能看到電信號，它不知道什么是數字。只能識別一串的高低電平信號。

在\(\{0,1\}\)上定義的二元布爾代數可以幫助我們完成這一過程。

二元布爾代數有True與False兩種符號（我們將它編碼為1和0），與AND、OR、NOT三種基本運算。

• 用&來表示AND，它有兩個輸入一個輸出，只有在輸入全為1時才輸出1，其他情況下全部輸出0。
• 用|來表示OR，它一樣有兩個輸入與一個輸出，并只有在輸入全為0時才輸出0，其他情況下全部輸出1。
• 用~來表示NOT，它只有一個輸入與一個輸出，輸入1時輸出0，輸入0時輸出1。

這時候我們發現，AND與OR是可以轉化的，只要用NOT反轉輸入與輸出即可。

如果我們只對AND的輸出取反，我們就能得到一個NAND，只用它，我們能重新構建出AND、OR和NOT。
在現實里，使用晶體管可以簡單地制造出一個有NAND邏輯的電路元件。

對OR的輸出取反得到的NOR也有這種能重新構建基本運算的性質。

于是，我們能將電路轉化為布爾代數運算了。

接下來我們要構建一種運算XOR，它有兩個輸出一個輸入，只在兩個輸出不相同時輸出1，用^來表示。
注意這里的運算符號沒有優先級，全部從左往右算即可。

^(In1,In2) -> (ans) :
Input1 & (~Input2) | (~Input1) & Input2

于是我們構建了XOR，遇到XOR就將其展開為頂上的式子即可。

ADD & SUB

接下來我們來開始構建加法。

得益于二進制數的簡單，我們可以輕易列出一位二進制加法的所有可能性。

我們會發現，可能的輸出里有一個兩位數，這意味著一位的輸出是不夠的。
也就是說，如果有一個表示一位加法的運算符，它就至少得有兩個輸入與兩個輸出，否則無法表示所有可能的結果。
假設我們用和來表示一位數，用進位來表示第二位數，我們就能構造加法。
于是，我們認為這個加法運算有兩個輸出：和SUM、進位CAR。

# In1即Input1表示第一個輸入，所有的In符號同理。
SUM = In1 ^ In2
CAR = In1 & In2

這個元件就是一個半加器。

為什么說它是“半加器”？因為它只能處理一位的二進制加法。
我們當然不只是想處理一位的二進制加法，為此我們需要再對它做一點改造。

我們要給他加入第三個輸入：進位CARIN。
這是一個特殊的一位輸入，但我們可以簡單的將它視作是一個一位的二進制加數。

于是我們重新構建一位加法：

1bit_plus(In1,In2,CARIN) -> (SUM,CAR) :
SUM = (In1 ^ In2) ^ CARIN
CAR = (In1 & In2)|(In2 & CARIN)|(In1 & CARIN)

這個就是一個全加器，它與半加器最大的區別便是它能通過堆疊擴展成任意位數的二進制加法。
這是為什么？
想象一下我們在算加法時使用的豎式，它展示了一種將一個多位加法拆解成多次的一位加法的方法。現在我們把它擴展到二進制數，我們會發現情況變得十分簡單了，我們可以將一個位數的二進制數加法拆解成多次的一位加法，而我們已經構造出一個一位加法了。

	11100101
+	01010110
	--------

并且我們已經知道了，一個多位的二進制數事實上是一串一位二進制數序列。使用這種堆疊加法是一件十分顯然的事情。
于是，我們就構建出了任意位數的加法。

減法可以被視為加一個數的相反數，為此我們來構建一個取反運算。
前面我們已經知道了怎么表示一個負數，對一個數取反的方法其實就是將它的每一位進行NOT運算之后再加一。
以0100為例，它的相反數是1100。

-(In) -> (ans):
ans = ~In + 1

于是，我們順利構建出了加法與減法，并且這些操作都可以實現成一個具體的電路。

這些內容事實上可以通過一個游戲Turing Complete清晰地學到。

溢出

在我們知道加減法究竟意味著什么之后，我們就能知道溢出是發生了什么了。

無符號加

以四位加法來舉例：
當我們試圖計算1111 + 0001時，輸出結果事實上是SUM=0;CAR=1。但假設我們要將這個結果保存在一個四位的儲存器中時，CAR就被舍棄了。

這時就發生了溢出。
將這個情況往高位擴展也是同樣的，無符號加法會在最高位產生進位時將它舍棄掉。

這種舍棄是必不可少的，因為減法一定程度上依賴于這種舍棄的機制運行。

無符號減

通過剛才的過程我們已經知道了減法是通過加一個相反數實現的。事實上可以說無符號減就是依賴于溢出這個機制來順利執行的。
以剛剛的4-4為例

	0100
+	1100
	----
1	0000

可以看到當最高位的1（CAR）被舍棄掉之后結果（SUM）是正確的。

但減法是會產生負數的，當結果是負數的時候會產生借位
以2-4為例

	0010
+	1100
	----
	1110

我們發現結果是14,但如果我們將它解釋為一個有符號整數，它的值就是對的（-2）。
這種情況我們就稱它發生了借位。

有符號加減

有符號數的加減法并不依賴于溢出機制，于是執行有符號數的加減法不可避免的會有上溢與下溢的問題。
如以四位長度計算0111 + 0001結果超出了最高的表達范圍，變成了1000。這種情況就稱為正溢出。
相似的，若計算1000 + 1000，其結果產生了進位（1 0000），這時SUM=0000;CAR=1。我們稱這種情況是負溢出。

Outro

于是我們就完成了加法與減法的定義，我們不難發現，即使一個機器沒有人的智慧，仍然可以正確的完成計算。
到此，我們已經構想出了一臺可以進行加減法計算的機器，下一篇中我們將試著把它實現出來。