# 2020q3 Homework6 (quiz6)
###### Contributed by < `huang-me` >
###### tags: `embedded_master`

[quiz6 題目](https://hackmd.io/@sysprog/2020-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 的長度，並且計算 $log_{2}N$，這個數字所有數字中 most significant bit 是哪一個 bit。

## 沒有任何數字空缺(只有 duplicate 出現兩次)
假設：n = 3
計算後得 $log_{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;
}