--- tags: linux2022 --- # 2022q1 Homework2 (quiz2) contributed by < [`ShawnLu31`](https://github.com/ShawnLu31) > ## 測驗 1 ### 解釋程式碼 ```c uint32_t average(uint32_t a, uint32_t b) { return (a + b) / 2; } ``` 簡單地將 `a` 和 `b` 相加後除以 2 。但此作法可能導致 overflow,例如: uint32 的最大值相加。 ```c uint32_t average(uint32_t low, uint32_t high) { return low + (high - low) / 2; } ``` 避免直接相加導致 overflow ,其中一個數與兩數的差的平均相加,兩者的差不會超過該兩個數的數值,所以不會導致 overflow 。 $$high = (high - low) + low$$ $$ \frac{high + low}{2} = \frac{(high - low) + 2low}{2} = \frac{high - low}{2} + low $$ ```c uint32_t average(uint32_t a, uint32_t b) { return (a >> 1) + (b >> 1) + (a & b & 1); } ``` `a` 和 `b` 各自除以 2 並相加。 因右移運算子 `>>` 移出的位元會被忽略,若 `a` `b` 皆為奇數,右移除 2 的結果會差 1 ,必須加回 1 ,故使用 `a & b & 1` 判斷兩者是否皆為奇數。 ```c uint32_t average(uint32_t a, uint32_t b) { return (a & b) + ((a ^ b) >> 1); } ``` 參考加法器原理 `a + b` 等價於 `((a & b) << 1) + (a ^ b)` , `(a & b) << 1` 為進位, `(a ^ b)` 為和。 所以 `(a + b) / 2` 等價於 `(((a & b) << 1) + (a ^ b)) >> 1` ,再化簡 -> `(((a & b) << 1) >> 1) + ((a ^ b) >> 1)` -> `(a & b) + ((a ^ b) >> 1)` ## 測驗 2 ### 解釋程式碼 ```c uint32_t max(uint32_t a, uint32_t b) { return a ^ ((a ^ b) & -(a < b)); } ``` 若 `a` 小於 `b`,則 `-(a < b) = -1` ,否則等於 `0` 。 回傳值會有兩種情況: `a ^ ((a ^ b) & -1)` 或 `a ^ ((a ^ b) & 0)` 在 `a` 小於 `b` 時,`-(a < b) = -1` , `-1` 在二補數表示時為 `0xffffffff` ,所以 AND `-1` 不會有改變,可以去掉化簡為 `a ^ a ^ b` 。兩個同樣的數做 XOR 會為 `0` ,將 `a ^ a` 先運算為 `0` ,再運算 `0 ^ b` 等於 `b` 。 ``` // a < b a ^ ((a ^ b) & -(a < b)) = a ^ ((a ^ b) & -1) = a ^ ((a ^ b) & 0xffffffff) = a ^ (a ^ b) = 0 ^ b = b ``` 在 `a` 大於等於 `b` 時, `-(a < b) = 0` , AND `0` 結果都是 `0` ,括號內 `((a ^ b) & 0)` 等於 `0` ,最後`a ^ 0` 等於 `a` 。 ``` // a >= b a ^ ((a ^ b) & -(a < b)) = a ^ ((a ^ b) & 0) = a ^ 0 ``` 變數用途: * `(a < b)` 做比較。 * 第一個 `a` 回傳 `a` 的值。 * 第二個 `a` 抵銷第一個 `a` 在需要回傳 `b` 時。 * 第一個 `b` 回傳 `b` 的值。 ## 測驗 3 ### 解釋程式碼 ```c #include <stdint.h> uint64_t gcd64(uint64_t u, uint64_t v) { if (!u || !v) return u | v; int shift; for (shift = 0; !((u | v) & 1); shift++) { u /= 2, v /= 2; } while (!(u & 1)) u /= 2; do { while (!(v & 1)) v /= 2; if (u < v) { v -= u; } else { uint64_t t = u - v; u = v; v = t; } } while (v); return u << shift; } ``` 可分成三個區域: 1. `if` 區域對應 GCD 演算法規則第 1、2 條。因至少一個數為 0 ,使用 OR 運算子回傳另一個數的值。 2. `for` 區域對應 GCD 演算法規則第 3 條。兩數 LSB 皆為 0 (偶數), 2 為公因數, shift 紀錄兩者最大公因數的 2 的冪。 3. `while` 和 `do while` 區域對應 GCD 演算法規則第 4、5 條。 * 第一個 `while` 與 `do while` 內部的 `while` 迴圈,使 `u` `v` 移除 2 的因數,因為經過前述的 `for` 迴圈,已不再有 2 的因數。 * `do while` 迴圈為輾轉相除法:被除數(大數)除以除數(小數),再使餘數與除數成為下一輪的被除數與除數,重述此動作直到餘數為 0 ,除數便是最大公因數。 在此實作,因 `v` 為迴圈的條件,所以使 `v` 一直放餘數, `u` 一直放除數,當 `v` 為 0 時, `u` 便為最大公因數。 所以 `v` 大於 `u` 時,可直接 `v -= u` ;`v` 小於 `u` 時,此時 `v` 為除數 `u` 被除數,須將除數換成 `u` ,並把差值給 `v` ,才能維持 `v` 餘數 `u` 除數。 最後回傳 `u << shift` ,公因數(不含因數 2)乘回因數 2 的冪,得到最大公因數。 ## 測驗 4 ### 解釋程式碼 ```c #include <stddef.h> size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out) { size_t pos = 0; for (size_t k = 0; k < bitmapsize; ++k) { uint64_t bitset = bitmap[k]; size_t p = k * 64; for (int i = 0; i < 64; i++) { if ((bitset >> i) & 0x1) out[pos++] = p + i; } } return pos; } ``` 外部迴圈走訪 bitmap 每個元素。 bitset 取出 bitmap 的一個元素,內部迴圈低位往高位尋找為 `1` 的位元,若該位原為 `1` ,此時 `i` 為第 `i` 個位元。 :::warning * out 的輸出涵義? pos 為 out 的 index,每找到一個 `1` pos 會加一。 bitmap 位元若都是 `1` pos 有最大值 ` bitmapsize * 64` 。 `p + i = k * 64 + i` 的意義? ::: ```c= #include <stddef.h> size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out) { size_t pos = 0; uint64_t bitset; for (size_t k = 0; k < bitmapsize; ++k) { bitset = bitmap[k]; while (bitset != 0) { uint64_t t = bitset & -bitset; int r = __builtin_ctzll(bitset); out[pos++] = k * 64 + r; bitset ^= t; } } return pos; } ``` 使用 `__builtin_ctzll` 改寫原本的迴圈,由低位往高位尋找第一個碰到的 `1` , `r` 等價於原本程式的 `i` 。 且使用 `XOR t` 清除碰到的 `1` (最低位元的 `1` ) ,使下一次的 `__builtin_ctzll` 不會成重複找到同個位元的 `1` 。 `-bitset` 為 `bitmap` 的二補數,兩者做 AND 後的 `t` 唯一的 `1` 會是 `bitmap` 最低位元的 `1` 。 此方法會直接找到需要的位元位置,不需像原本程式用迴圈一一檢查每個位元。 ## 測驗 5 ### 解釋程式碼 ## 測驗 6 ### 解釋程式碼 ## 測驗 7 ### 解釋程式碼
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up