2024q1 Homework4 (quiz3+4)

contributed by < marsh-fish >

第三週測驗題

測驗 1

測驗 2
用 bitwise 來實作除法運算，根據 Hacker's Delight 使用 bitwise 來實現除法會比用除法運算更有效率。

若我們欲除以 10 ，但除以 10 無法單純的改成 bitwise 的形式，因為 10 並不是 2 的冪或接近 2 的冪的數值，於是我們打算找到一個接近 10 的數值以取代除以 10 的除法運算操作。以本題為例，

$2^N=128,a=13,\frac{128}{13}\approx 9.84$ 因此

$\frac{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

測驗 2