# 2022q1 Homework1 (quiz2)
###### tags: `Linux 核心設計` `成大課程`
contributed by < `hbr890627` >

[題目連結](https://hackmd.io/@sysprog/linux2022-quiz2)

## 測驗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==。
:::info
最後要再 `& 1` ，是因為只需要取最右邊位元的資訊就好。
:::
可以再次改寫為以下等價的實作：

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

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

## 測驗2
在〈[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)〉一文中的「不需要分支的設計」一節提供的程式碼 `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