2020q3 Homework6 (quiz6)

Contributed by < huang-me >

tags: embedded_master

quiz6 題目

測驗1 bfloat16

float fp32tobf16(float x) {
    float y = x;
    int *py = (int *) &y;
    unsigned int exp, man;
    exp = *py & 0x7F800000u;
    man = *py & 0x007FFFFFu;
    if (!exp && !man) /* zero */           
        return x;
    if (exp == 0x7F800000u) /* infinity or NaN */
        return x;

    /* Normalized number. round to nearest */
    float r = x;
    int *pr = (int *) &r;
    *pr &= 0xff800000;
    r /= 256;
    y = x + r;

    *py &= 0xffff0000;
    return y;
}

5-6行 分別利用 bitwise operation 取得 Exponential, Mantissa
7-10行 則處理 0、INF 等例外情況
13-17行 把輸入的數字除以 256 並且加到原本的 x 中以達到 round 的效果
19-20行 最後只取 y 的前面 16 個 bit

測驗2 ring buffer

do {...} while(0) macro

• 當我們在 if, else 中呼叫 macro 時，如果沒有使用 do {...} while(0) 而是直接使用 {} 將內容包起來就可能造成程式沒有辦法 compile，如下：

if(statement)
    marco(x);
else
    func(y);

• 因為 macro 就是把寫好的程式展開而已所以等同於 {}; else ... 不過大掛號後面不應該有 ';' 因此會有 compilation error ，此時如果把 ';' 拿掉就可以順利執行，不過這樣的程式碼不直覺，所以我們選擇用 do {...} while(0)

測驗3

macro 初始化 struct llist

#define cons(x, y) (struct llist[]){{y, x}}　
此題一開始就使用到了 compund literal，在 define 中將 struct 的 val，next 都設定好

y assign 給 val
x 則 assign 給 next

sorted_insert

從 head 開始逐一走訪，如果 current->next->val 大於想要插入的值則把新的 node 插入在 current & current->next 的中間。

sort

利用前面定義好的 sorted_insert 一一將 node 插入到 sorted 中。

測驗4 Find duplicate number

一開始先設定 N 為 list 的長度，並且計算

$lo{g}_{2}N$，這個數字所有數字中 most significant bit 是哪一個 bit。

沒有任何數字空缺(只有 duplicate 出現兩次)

假設：n = 3 計算後得

$lo{g}_{2}n$ = 2

	bit 2	bit 1	bit 0
1	0	0	1
2	0	1	0
3	0	1	1
全部出現次數	0	2	2

• 無論加入的數值為和，只要和沒有 duplicate 的 set bit 數量作比較就可以找到 duplicate number。

有其他數字沒有出現在 list 中(duplicate 不止出現兩次)

在 duplicate number 的 set bit 的 bit 出現 1 的次數總和一定會變得比原本應該出現的次數多，因此我們一樣只需要跟從 1 ~ n-1 比較，只要出現的次數比應該出現的次數多，就代表這個 bit 在 duplicate number 裡面必定是 set bit。

int myfindDuplicate(int *nums, int numsSize)
{
    // AMOUNT OF BITS
    const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
    // GO THROUGH ALL NUMBERS IN NUMS
    int *c2;
    c2 = calloc(log_2, sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        while (nums[i]) {
            c2[__builtin_ctz(nums[i])]++;
            nums[i] &= nums[i] - 1;
        }
    }

    int res = 0;
    for (int i = 0; i < log_2; i++) {
        int c1, r, bit = 1 << i;
        r = numsSize & bit ? numsSize & (bit - 1) : 0;
        c1 = ((numsSize >> (i + 1)) << i) + r;
        res |= (c1 < c2[i]) << i;
    }
    free(c2);
    return res;
}