2022q1 Homework2 (quiz2)

contributed by < 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 個位元。

• 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

解釋程式碼