---
tags: linux2022
---

# 2022q1 Homework2 (quiz2)
contributed by < [`ShawnLu31`](https://github.com/ShawnLu31) >

## 測驗 1
### 解釋程式碼

uint32_t average(uint32_t a, uint32_t b)
{
    return (a + b) / 2;
}

簡單地將 `a` 和 `b` 相加後除以 2 。但此作法可能導致 overflow，例如： uint32 的最大值相加。

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
$$

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` 判斷兩者是否皆為奇數。

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
### 解釋程式碼

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
### 解釋程式碼

#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
### 解釋程式碼

#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` 的意義?
:::

#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
### 解釋程式碼