2022q1 Homework1 (quiz2)

tags: Linux 核心設計 成大課程

contributed by < hbr890627 >

題目連結

測驗1

想對二個無號整數取平均值，用以下程式可以避免 overflow ，正常執行。

#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
    return low + (high - low) / 2;
}

可改寫為以下等價的實作：

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (EXP1);
}

其中：
a >> 1 ，向右 shift 一個位元，等價於 a/=2 。
b >> 1 ，向右 shift 一個位元，等價於 b/=2 。
但若是在 shift 之後才將兩者相加，可能會漏掉最右邊的位元，如： 01 + 01 = 10 ，需要在當 a, b 都為奇數時，補上 1 ， 因此 EXP1 = a & b & 1。

最後要再 & 1 ，是因為只需要取最右邊位元的資訊就好。

可以再次改寫為以下等價的實作：

uint32_t average(uint32_t a, uint32_t b)
{
    return (EXP2) + ((EXP3) >> 1);
}

參考第 1,2 週課堂問答簡記中， Eddielin0926 的解釋，可以將其思考成全加器除二，原本是 a + b >> 1 ，將 carry 提出來後就變成 (a & b) + ((a ^ b) >> 1)。
EXP2 = a & b
EXP3 = a ^ b

測驗2

在〈解讀計算機編碼〉一文中的「不需要分支的設計」一節提供的程式碼 min:

int32_t min(int32_t a, int32_t b) {
    int32_t diff = (a - b);
    return b + (diff & (diff >> 31));
}

diff >> 31 ，取最左邊的位元，看是正數或負數。
如果是正數， diff & (diff >> 31) 等於零，會 return b。
如果是負數， diff & (diff >> 31) 等於 diff ，會 return b + diff = a。

將上面程式碼進行改寫，可以得到以下實作 (max)：

#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((EXP4) & -(EXP5));
}

考慮兩種情況:

1. 當 a >= b 時，根據 XOR 的特性，((EXP4) & -(EXP5)) 要等於 0 時， 才會 return a，因此 -(EXP5) 要等於 0 才有機會， EXP5 = a < b 。
2. 當 a < b 時，根據 XOR 的特性，((EXP4) & -(EXP5)) 內應該要有包含 a ^ b 的部分，才能再 a ^ (a ^ b) 後 return b，EXP4 = a ^ b 。

測驗3

以下為 64 位元 GCD (greatest common divisor, 最大公因數) 求值函式:

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    while (v) {                               
        uint64_t t = v;
        v = u % v;
        u = t;
    }
    return u;
}

1. 當 u, y 都是 0 時，return 0。
2. 當 u=0 時，return v，當 v=0 時，return u。
3. 使用輾轉相除法找到最大公因數。

可改寫為：

#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 (COND);
    return RET;
}

if (!u || !v) return u | v;
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
    u /= 2, v /= 2;
}

1. 當 u, y 都是 0 時，return 0。
2. 當 u=0 時，return v，當 v=0 時，return u。
3. 判斷 u, v 是否都為偶數，並紀錄 shift 的次數。

while (!(u & 1))
    u /= 2;

4. 將 u 其中二的因數提出來。

do {
    while (!(v & 1))
        v /= 2;
    if (u < v) {
        v -= u;
    } else {
        uint64_t t = u - v;
        u = v;
        v = t;
    }
} while (COND);

5. 根據輾轉相除法，兩數要不斷相減直到 v 變為 0 為止，因此 COND = v!=0，將其簡化符合Linux的風格，COND = v。

return RET;

6. 最終，要 return 剩下不為 0 的數字，RET = u << shift。

測驗4

在影像處理中，bit array (也稱 bitset) 廣泛使用，考慮以下程式碼:

#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;
}

測驗5

測驗6

測驗7

測驗8