# 小學數學(bit ver.)

###### tags: `IT鐵人`

## 例題答案

不知道各位有沒有試試看前面的題目呢??這邊稍微講解一下ㄅ
**首先是a.**
> op=0 (代表R-type), funct=32 (也就是100000)
> 
> 代表加法ADD指令
>
> rs=1, rt=2, rd=3
> 
> 分別代表$at, $v0, $v1

所以代表將$at+$v0的結果放在$v1
Assembly的寫法就會是
> add $v1, $at, $v0

**再來是b.**
> op=43 (101011)
> 
>代表sw指令
>
> rs=16, rt=5
> 
> 分別代表$s0, $a1
>
> 而immediate只是代表位移的數量而已

所以代表將$s0中存的位置加上4
結果所指到的位址中的資料放進$a1中
Assembly的寫法為
> sw $a1, 4($s0)

**你答對了嗎??**

*稍微有點困難啦，畢竟sw上次沒有提到。
不過大學就是這樣嘛，東西很多教授不可能全部講一次。*
所以我們繼續努力吧！

## 二進位轉換方式

前面我們在標記register的位置時，使用2進位制，也就是說最初的代表2的0次方，在往前為2的1次方，以此類推，所以當我們要將數字從10進位制轉換成2進位制時，基本上用短除法就能夠做出來，或是一直用小於當下數字且最大的2的次方減下去也可以，以109來舉例的話…
> 109 - 64 = 45 (1xxxxxx)
> 45 - 32 = 13 (11xxxxx)
> 13 < 16 (110xxxx)
> 13 - 8 = 5 (1101xxx)
> 5 - 4 = 1 (11011xx)
> 1 < 2 (110110x)
> 1 - 1 = 0 (1101101)

噹啷！是不是很簡單阿~結果就是1101101喔！

## 負數表示方式

那麼既然正數可以如此表示，那麼負數呢？
既然負數會有一個減號在前面，我們可以在2進位的最前面多增加一個代表正負數的bit。
這就叫做**sign and magnitude**
所以 109 = 01101101
如果-109 = 11101101
那麼問題來了，以8個bit來表示數字的話
0就有正負0兩種可能
+0 = 00000000
-0 = 10000000

另外一種沒什麼在用的方法稱為**1's Complement**
就是直接取補數就好(1變0，0變1)
所以 109 = 01101101
那麼-109 = 10010010
這麼一來有些加減法可以正常運作，有些不行
不過0一樣有正負0兩種表示方法，所以

最後一個最實用的，升級版的前者：**2's Complement**
取完補數後將結果+1
這麼一來
0 = 00000000
-0 = 11111111 + 1 = 1 00000000
最前面的1會跑出我們在意的8 bit
所以結果仍然是00000000
並且負數換成正數也是同樣的作法
有興趣的同學可以試試看
採用了**2's Complement**，可以解決正負0的問題 ~~不會撞號~~

## 加減法

定義好數字的正負如何表示之後，加減法的部份就簡單多了。
加法只要將兩者加起來；減法則要將後者變號，再使用加法即可。

舉例來說
> | | 7 + 9 = 16 |
> | -------- | -------- |
> | | 00000111 |
> | + | 00001001 |
> | = | 00010000 |

> | | 13 - 20 = -7 |
> | -------- | -------- |
> | | 00001101 |
> | + | 11101100 (00010100的負數) |
> | = | 11111001 (00000111的負數) |

要特別注意的是，在7+9=16之中，發生了進位，要是進位的時候壓到了最前面的bit，就會讓人認為結果是負數，這種情況稱為**Overflow**

### Overflow

寫過程式的同學，應該聽過這個詞，中文稱為溢位(~~腋味~~)。

如果在c語言中執行以下程式碼片段

int x = 1000000000;
int y = 2000000000;
printf("%d\n", x+y);

則會出現
> -1294967296

這就是因為加法之後進位壓到了sign bit，導致程式以為結果為負數。
所以做計算的時候要特別注意，基本上正數加上正數，以及負數加上負數都有可能發生溢位。

### 加法器

以int來說，最大的數字為 ${2}^{31}-1$，也就是說如果要一次加起兩個數字，我們需要一個32 bit的加法器，不過太大了，並且如果又要支援更大的加法，又會需要更大的加法器來一次實施，所以我們不是這樣想的，我們用的是多個加法器連接來計算。

也就是說，以一個32 bit的加法來看，我們用的是32個1 bit的加法器，一個一個的加上去，並且將進位往後傳，就像是國小老師教的那樣，那個我們單純將一堆加法器連接在一起，就稱為**Ripple Carry Adder**。

不過這代表每次都要等前面一個adder做完運算才能輪到下一位。

為了加快速度，出現了新的加法加速器，這就是**Carry Lookahead Adder(CLA)**

透過邏輯運算，我們可以將前面是否會進位提早告訴後面的adder，這麼一來就能將結果加速，至於CLA的原理，礙於篇幅的關係，杰哥打算留到下一篇再跟各位介紹。

## 牛刀小試

這篇輕輕鬆鬆，我們做兩個簡單的加減法就好了，題目如下：
> | a. | 28 + 90 |
> | -|-|
> | b. | 30 - 120 |

在紙上寫出計算過程吧~~

| 上一篇 | 下一篇 |
|-|-|
|[我也...可以跟電腦娘說話嗎](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/Bkus0I4R_)|[CLA以及bit乘法](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/Sk4AiBGyt) |

## 成為資工金牌之路有你有我