計算機概論-邏輯運算
這篇是講關於邏輯運算的一些觀念
邏輯運算
NOT
NOT運算子是一元運算子，只有一個輸入，輸出與輸入相反的值
輸入0就會輸出1，輸入1就會輸出0
truth table：
| x | NOT x |
|---|---|
| 0 | 1 |
| 1 | 0 |
擴展到n bits之後就可以做一補數運算了www
例如：NOT 10011000 = 01100111
AND
AND運算子是二元運算子，有兩個輸入
只有兩個輸入同時為1的時候才會輸出1，其他輸出0
truth table：
| x | y | x AND y |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
擴展到n bits之後可以用來做unset(強制設為0)
例如10100110 AND 00000111 = 00000110
OR
OR運算子是二元運算子，有兩個輸入
只要其中一個輸入為1就會輸出1，其他輸出0
truth table：
| x | y | x OR y |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
擴展到n bits之後可以設定特定位元為1
例如10100110 OR 11111000 = 11111110
XOR
XOR運算子是二元運算子(念作exclusive-or)，有兩個輸入
兩個輸入不一樣的時候才會輸出1，其他輸出0
XOR其實是由前三個運算組合起來的
$ x\ XOR\ y\leftrightarrow[x\ AND\ (NOT\ y)]\ OR\ [(NOT\ x)\ AND\ y] $
truth table：
| x | y | x XOR y |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
擴展到n bits之後可以用來反轉特定位元
例如10100110 OR 11111000 = 01011110
位移運算
邏輯位移
- 右移
所有位元都往右移一位，捨棄最右邊的位元，最左邊的位元填上0
例如10011000右移一位之後變成01001100
- 左移
所有位元都往左移一位，捨棄最左邊的位元，最右邊的位元填上0
例如10011000左移一位之後變成00110000
循環位移
- 右移
所有位元都往右移一位，最右邊的位元補到最左邊的位元
例如10011001右移一位之後變成11001100
- 左移
所有位元都往左移一位，捨棄最左邊的位元補到最右邊的位元
例如10011001左移一位之後變成00110011
算術位移
- 右移
所有位元都往右移一位，捨棄最右邊的位元，最左邊的位元填上原本的位元(保持原本的正負號)
例如10011000右移一位之後變成11001100
- 左移
所有位元都往左移一位，捨棄最左邊的位元，最右邊的位元填上0
例如10011000左移一位之後變成00110000
算術運算
整數(二補數)的加減法
整數(二補數)運算的過程：
$ A \pm B=? $
- 判斷是加法或減法
- 若為減法則做二補數
- 相加
例1：A=$ (00010001)_2 $,B=$ (00010110)_2 $
A+B=?
- 判斷是加法或減法：加法
- 若為減法則做二補數：跳過
- 相加
$$ \begin{split}
&\ \ \ \ 1\ \ \ \ \ \ \ \ \ \ \ \ Carry(進位) \\
&00010001\ A \\
+&\underline{00010110}\ B \\
&00100111\ R(結果)
\end{split} $$
我們得到 (+17) + (+22) = (+39)
例2：A=$ (11011101)_2 $,B=$ (00010100)_2 $
A-B=?
- 判斷是加法或減法：減法
- 若為減法則做二補數：$ (00010100)_2 $ 的二補數 $ (11101100)_2 $
- 相加
$$ \begin{split}
1&11111\ \ \ \ \ \ \ Carry(進位) \\
&11011101\ A \\
+&\underline{00010100}\ (\overline{B}+1) \\
&11001001\ R(結果)
\end{split} $$
我們得到 (-35) - (+20) = (-55)
整數(sign-and-magnitude)的加減法
整數(sign-and-magnitude)運算的過程：
$ A \pm B=? $
- 判斷是加法或減法
- 若為減法則將 $ B_{Sign} $ 做NOT運算
- 指定S為 $ A_{Sign}\ XOR\ B_{Sign} $
- 若S等於1跳到第5步驟，否則跳到第6步驟
- $ R_{Magnitude} \leftarrow A_{Magnitude}+(\overline{B_{Magnitude}}+1) $
- 檢查是否overflow
- 如果overflow，$ R_{Sign} \leftarrow A_{Sign} $，然後結束，如果沒有跳到下一步驟
- $ R_{Magnitude} \leftarrow (\overline{R_{Magnitude}}+1) $
- $ R_{Sign} \leftarrow B_{Sign} $
- $ R_{Magnitude} \leftarrow A_{Magnitude}+B_{Magnitude} $
- 檢查是否overflow
- 如果overflow，回到overflow然後結束，如果沒有跳到下一步驟
- $ R_{Sign} \leftarrow A_{Sign} $
例1：A=$ (00010001)_2 $,B=$ (00010110)_2 $
A+B=?
- 判斷是加法或減法：加法
- 若為減法則將 $ B_{Sign} $ 做NOT運算：跳過
- 指定S為 $ A_{Sign}\ XOR\ B_{Sign} $：S=0
- $ R_{Magnitude} \leftarrow A_{Magnitude}+B_{Magnitude} $：$ R_{Magnitude}=0100111 $
- 檢查是否overflow
- 如果overflow，回到overflow然後結束，如果沒有跳到下一步驟
- $ R_{Sign} \leftarrow A_{Sign} $：$ R_{Sign}=0 $
這樣就得到結果 $ (+17)+(22)=(00100111)_2=(+39) $
例2：A=$ (00010001)_2 $,B=$ (10010110)_2 $
A+B=?
- 判斷是加法或減法：加法
- 若為減法則將 $ B_{Sign} $ 做NOT運算：跳過
- 指定S為 $ A_{Sign}\ XOR\ B_{Sign} $：S=1
- $ R_{Magnitude} \leftarrow A_{Magnitude}+(\overline{B_{Magnitude}}+1) $：$$ \begin{split}
No\ overflow\ \ \ \ \ \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Carry(進位) \\
A_{Sign}\ 0\ \ \ \ \ \ &0010001\ A_{Magnitude} \\
B_{Sign}\ 1\ \ +&\underline{1101010}\ (\overline{B_{Magnitude}}+1) \\
&1111011\ R_{Magnitude} \\
R_{Sign}\ 1\ \ \ \ \ \ &0000101\ R_{Magnitude}= (\overline{R_{Magnitude}}+1) \\
\end{split} $$
這樣就得到結果 $ (+17)+(-22)=(10000101)_2=(-5) $
例3：A=$ (11010001)_2 $,B=$ (10010110)_2 $
A-B=?
- 判斷是加法或減法：減法
- 若為減法則將 $ B_{Sign} $ 做NOT運算
- 指定S為 $ A_{Sign}\ XOR\ B_{Sign} $：S=1
- $ R_{Magnitude} \leftarrow A_{Magnitude}+(\overline{B_{Magnitude}}+1) $：$ R_{Magnitude}=(0111011)_2 $
- 檢查是否overflow
- 如果overflow，$ R_{Sign} \leftarrow A_{Sign} $，然後結束：$ R_{Sign}=1 $
這樣就得到結果 $ (-81)+(-22)=(10111011)_2=(-59) $
浮點數的加減法
$ A \pm B=? $
浮點數運算的過程：
- 如果其中一個數字為0，運算結果就為另一個數字
- 檢查是加法或減法
- 如果是減法，把 $ B_{Sign} $ 做NOT運算
- 將兩個數字去正規化(在尾數前面加個1 www)
- 將指數較小的數字累乘，並向右位移
- 將兩數相加(sign-and-magnitude)
- 檢查有沒有overflow
- 如果有overflow就將尾數右移，指數加一
- 正規化
- 如果需要捨去尾數則捨去
例1：
A=$ (0\ 10000001\ 01110000000000000000000)_2 $
B=$ (0\ 10000110\ 01000011110000000000000)_2 $
A+B=?
- 如果其中一個數字為0，運算結果就為另一個數字：跳過
- 檢查是加法或減法：加法
- 如果是減法，把 $ B_{Sign} $ 做NOT運算：跳過
- 將兩個數字去正規化(在尾數前面加個1 www)：
$ A_{Mantissa}=(101110000000000000000000)_2 $
$ B_{Mantissa}=(101000011110000000000000)_2 $
- 將指數較小的數字累乘，並向右位移
A較小，指數加五，尾數右移五位
A_{Mantissa}=(000001011100000000000000) $
- 將兩數相加(sign-and-magnitude)
R_{Mantissa}=(101001111010000000000000)_2
- 檢查有沒有overflow
- 如果有overflow就將尾數右移，指數加一：沒有
- 正規化
$ R=(0\ 10000110\ 101001111010000000000000)_2 $
- 如果需要捨去尾數則捨去：跳過
這樣就得到結果$ R=(010000110101001111010000000000000)_2 $
例2：
A=$ (0\ 10000001\ 01110000000000000000000)_2 $
B=$ (1\ 10000001\ 11000001100000000000000)_2 $
A-B=?
- 如果其中一個數字為0，運算結果就為另一個數字：跳過
- 檢查是加法或減法：減法
- 如果是減法，把 $ B_{Sign} $ 做NOT運算
- 將兩個數字去正規化(在尾數前面加個1 www)
$ A_{Mantissa}=(101110000000000000000000)_2 $
$ B_{Mantissa}=(111000001100000000000000)_2 $
- 將指數較小的數字累乘，並向右位移：兩數指數一樣，跳過
- 將兩數相加(sign-and-magnitude)：
$ R_{Sign}=(1)_2 $
$ R_{Mantissa}=(1010100011000000000000000)_2 $
- 檢查有沒有overflow：有
- 如果有overflow就將尾數右移，指數加一
$ R_{Exponent}={10000010}_2 $
$ R_{Mantissa}=(0010100011000000000000000)_2 $
- 正規化
$ R=(1\ 10000010\ 001010001100000000000000)_2 $
- 如果需要捨去尾數則捨去
$ R=(1\ 10000010\ 00101000110000000000000)_2 $