# 2022q1 Homework2 (quiz2)
contributed by <`HScallop`>
###### tags: `linux2022`
> [2022q1 quiz2](https://hackmd.io/@sysprog/linux2022-quiz2)

### 測驗 1

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

EXP1 = ?
> a & b & 1

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

EXP2 = ?
> a & b

EXP3 = ?
> a ^ b
#### 延伸問題
1. 當初這兩題在上課有回答出來。思考這兩題的時候，覺得很類似於以前上邏輯設計的時候 full-adder 的作法。
在 EXP1 的程式碼因為先各自 ~~>> 1~~ `/2` ，所以除了最小位數外，不需要再考慮 propagation ，而 EXP2, EXP3 就像是經典的 full-adder 加法後，再 ~~>> 1~~ `/2` 的結果。
從上圖可以看出 sum 就是 a ^ b propagation 則是 a & b 。

2.
---
### 測驗 2

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

EXP4 = ?
> a ^ b

EXP5 = ?
> a < b

#### 延伸問題
1. 可以參考 [解讀計算機編碼 - 不需要分支的設計](https://hackmd.io/@sysprog/binary-representation#%E4%B8%8D%E9%9C%80%E8%A6%81%E5%88%86%E6%94%AF%E7%9A%84%E8%A8%AD%E8%A8%88)想法上是利用 `diff = a - b` 還有 ~~(diff >> 31)~~ 判斷 `diff < 0` ，如果 `diff < 0` `b` 就會被加上 ``(a - b)`` 轉換成 `a` 。
回到測驗本測驗的問題，還是一樣要在 `b > a` 時，把 `a` 轉換成 `b` 。跟前面不一樣的地方是這邊想用 `XOR` 來實作。
所以推測在 `b > a` 時，會用 `a ^ a ^ b` 把 `a` 變成 `b` 。

2.
---

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

COND = ?
> v

RET = ?
> u << shift

#### 延伸問題
1. 程式碼實現了題目給定的簡化規則，再用輾轉相除法找到 GCD，以下按照敘述來對應程式碼行數

- If both x and y are 0, gcd is zero $gcd(0, 0)$.
- $gcd(x, 0) = x$ and $gcd(0, y) = y$ because everything divides 0.
> line 4
> `u` 或 `v` 會有一個是 `0` 所以 `u | v` 會是非 `0` 的另外一個數。
- If both x and y are even, $gcd(x, y) = 2 * gcd(\dfrac{x}{2}, \dfrac{y}{2})$ because 2 is a common divisor.
Multiplication with $2$ can be done with bitwise shift operator.
> line 6-8
> `!((u | v) & 1)` 這邊的 `AND 1` 就是最小一位數的 mask 只要 `u` 或 `v` 有一個是奇數，就會跳出迴圈。

- If x is even and y is odd, $gcd(x, y) = gcd(\dfrac{x}{2}, y)$, vice versa.
> line 9-21
> while loop on line 9: u is even and v is odd.
> while loop on line 12: u is odd and v is even.
> line 11 開始的 do while 迴圈是輾轉相除法的實作，比較特別的是他會把相減之後的數留在 `v` ，繼續用 u is odd and v is even 的規則簡化。
> 所以這邊 `COND` 是輾轉相除法的終止條件。
> 而`RET` 是最後結果，需要注意剛剛照著規則提出的 2 要乘回來。
---
2.

### 測驗 4

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

改寫的程式碼:

#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 = EXP6;
            int r = __builtin_ctzll(bitset);
            out[pos++] = k * 64 + r;
            bitset ^= t;                           
        }
    }
    return pos;
}

EXP6 = ?
> bitset & -bitset

#### 延伸問題
1. 其實在原本的題目中就有說明第 9 行的作用是找出最小的位數的 `1` ，這邊利用了 2's complement 的特性。
e.g.
$010001\underbrace{0...0}_\text{n}$
2's complement:
1. invert bits $101110\underbrace{1...1}_\text{n}$
2. add 1 $101111\underbrace{0...0}_\text{n}$

比較可以發現，只會有最小一位的 `1` 和更小位數的 `0` 會一樣，其他位置都已經被反轉。
第一段程式碼第 8 行的迴圈被取代了，運用 `__builtin_ctzll`，不需要一位一位檢查。

2.