# Division
## Booth's Algorithm
根據當前位元和前一位元的組合，執行以下操作：

* 00: 連續的0中段，不進行算術操作。
* 01: 連續的1結束，將被乘數（multiplicand）加到產品的左半部分。
* 10: 連續的1開始，將被乘數減去產品的左半部分。
* 11: 連續的1中段，不進行算術操作。

與之前的演算法一樣，將產品register向右移動1位。

### Booths Example (2 x 7)
* 初始值：
* Multiplicand（被乘數）: 0010
* Product（產品）: 0000
* 下一步操作：subtraction（減法）
* 步驟1：
* a. 產品減去被乘數：0000 - 0010，結果是 1110。
* b. 進行算術右移：1110（產品）和 0111（sign extension）。
* 下一步操作：no operation（無操作），然後進行右移。
* 步驟2：
* 進行算術右移：0010 1111（產品）和 0011（sign extension）。
* 下一步操作：no operation（無操作），然後進行右移。
* 步驟3：
* 進行算術右移：0010 1111（產品）和 1001（sign extension）。
* 下一步操作：no operation（無操作），然後進行右移。
* 步驟4：
* a. 產品和被乘數相加：0010 + 0010，結果是 0001 1100。
* b. 進行算術右移：0001 1100（產品）和 1（sign extension）。
* 下一步操作：
* no operation（無操作），然後進行右移。
* 最終結果：
* 最後一步完成，結果為：0000 1110。
### Booths Example (2 x -3)
* 初始值：
* Multiplicand（被乘數）: 0010
* Product（產品）: 0000
* 下一步操作：subtraction（減法）
* 步驟1：
* a. 產品減去被乘數：0000 - 0010，結果是 1110。
* b. 進行算術右移：1110（產品）和 1101（sign extension）。
* 下一步操作：addition（加法），然後進行右移。
* 步驟2：
* a. 產品和被乘數相加：1110 + 0010，結果是 0001 0110。
* b. 進行算術右移：0001 0110（產品）和 1（sign extension）。
* 下一步操作：subtraction（減法），然後進行右移。
* 步驟3：
* a. 產品減去被乘數：0001 0110 - 0010，結果是 0010 1110。
* b. 進行算術右移：0010 1110（產品）和 1011（sign extension）。
* 下一步操作：no operation（無操作），然後進行右移。
* 步驟4：
* a. 進行算術右移：1111 0101（產品）和 1（sign extension）。
* b. 完成，結果為：0010 1111 1010。
## Division in MIPS
* Signed division
`div $t1, $t2 # t1 / t2`
* 此指令將寄存器 $t1 中的值除以寄存器 $t2 中的值。
* 商數存儲在特殊寄存器 LO（Low），餘數存儲在特殊寄存器 HI（High）。
* 複製商和餘數:
* mflo（從 LO 移動）將 LO 寄存器的內容複製到目標寄存器 $t3。
* mfhi（從 HI 移動）將 HI 寄存器的內容複製到目標寄存器 $t4。
* 在這些指令之後，$t3 包含商，$t4 包含餘數。

mflo $t3   # 將商數複製到 t3
mfhi $t4   # 將餘數複製到 t4

* Unsigned division
`divu $t1, $t2 # t1 / t2`
* 此指令執行無符號除法，將寄存器 $t1 和 $t2 中的值視為無符號整數。
* 商數存儲在 LO 寄存器中，餘數存儲在 HI 寄存器中。
## 長除法
* 將被除數不動，從最高位元開始，一路將除數移動到可以減到被除數的最低位元。
* 如果被除數減掉除數的結果是正的，則商大於零，將商填入結果。
* 將剩餘的部分與除數的低位元重新結合，然後繼續進行下一輪的減法。
* 重複步驟，直到所有位元都處理完畢。
* 在這個過程中，如果在某一步驟中無法再進行減法（即結果為負值），則必須還原被減去的值，將商填入0，然後繼續下一位元的操作。

這種方法可以有效地進行除法操作，特別是在沒有計算器或電腦的情況下。在現代計算機科學中，使用二進制表示的32位元除法，也可使用類似的原理，但以二進制位元運算為基礎。

## 除法器
64位元除法器的設計，其中包含32位元的被除數和除數，以及64位元的餘數和ALU（算術邏輯單元）。

* 64位元Divisor：實際上只使用32位元，其餘32位元用於移位操作。
* 被除數和餘數：都是64位元，被除數一直保留在Remainder中。
* ALU：用於執行64位元的減法。

進行32位元除法時的步驟：
* 初始狀態：Divisor位於64位元的高位元，被除數位於Remainder中，ALU用於減法。
* 第一次減法：由於Remainder的高位元為零，減法結果一定為負。商填零，開始將Divisor向低位元移動。
* 循環：繼續將Divisor向低位元移動，並根據每次減法的結果確定商的值。
* 最後一次減法：當Divisor移動到最低位元時，執行最後一次減法，根據結果確定最終的商和餘數。

如果減法的結果是正的，表示可以繼續減，並填入對應的商值。如果減法的結果是負的，則商填零，並將餘數還原回之前的狀態。

這種除法器設計的目的是實現32位元除法，同時最終的商不會超過32位元