---
# System prepended metadata

title: 2024q1 Homework4 (quiz3+4)

---

# 2024q1 Homework4 (quiz3+4)
contributed by < `marsh-fish` >

### 第三週測驗題

[測驗 1](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-1)


[測驗 2](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-2)
用 bitwise 來實作除法運算，根據 [Hacker's Delight](https://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf) 使用 bitwise 來實現除法會比用除法運算更有效率。

若我們欲除以 10 ，但除以 10 無法單純的改成 bitwise 的形式，因為 10 並不是 2 的冪或接近 2 的冪的數值，於是我們打算找到一個接近 10 的數值以取代除以 10 的除法運算操作。以本題為例， $2^N = 128, a = 13, \cfrac{128}{13} \approx 9.84$ 因此 $\cfrac{128}{13}$ 便是一個可用來代替除以 10 的數值，乘 13 的運算以 bitwise 改寫會成`((((tmp >> 3) + (tmp >> 1) + tmp) << 3) + d0 + d1 + d2)`，其中的 `d0 d1 d2` 為向右位移 3 時所遺失的所以須再運算完後將其補回。餘數為被除數減去商數乘以除數的結果(餘數定理)，又`10＝(4+1)*2`，因此 `r = tmp - 10 * q;` 以 bitwise 寫成 ` r = tmp - (((q << 2) + q) << 1);`

### 第四週測驗題

[測驗 1](https://hackmd.io/@sysprog/linux2024-quiz4#%E6%B8%AC%E9%A9%97-1)


[測驗 2](https://hackmd.io/@sysprog/linux2024-quiz4#%E6%B8%AC%E9%A9%97-2)
