# 2020q3 Homework6 (quiz6)
contributed by < `tsengsam` >

## 測驗 `1`: 把 FP32 轉換成 bfloat16
* 將 IEEE 754 的 [FP32](https://en.wikipedia.org/wiki/Single-precision_floating-point_format) (Single-precision floating-point format) 轉換成動態範圍相同，精度較低的 bfloat16

浮點數若以位元表示時會分成 **sign**, **exponent**, **fraction** 三個區間，與以前將整數表示成位元的方式不一樣。
以 **bfloat16** 為例：有 **1** 位元 sign bit、**8** 位元 exponent bits、**7** 位元 fraction bits。
換算成十進位的數值時：
**Float32 :** $(-1)^{b_{31}} \times 2^{(b_{30}b_{29}...b_{23})_2-127} \times (1.b_{22}b_{21}...b_{0})_2$
**Bfloat16 :** $(-1)^{b_{15}} \times 2^{(b_{14}b_{13}...b_{7})_2-127} \times (1.b_{6}b_{5}...b_{0})_2$
範例：4049~Hex~ = 0 10000000 1001001 = 3.140625~10~ ≈ π

* 轉換程式碼 (本題只考慮 Normalized number 的轉換)
若要以程式碼實現將 FP32 轉換成 bfloat16，需要注意
1. 特殊值的處理 (infinity, NaN)：如 exponent bits 全為 1 時可能為 inf, Nan
2. 浮點數不能做 bitwise operation：需要把型態轉為整數才能做
3. 判斷進位：如同十進位的四捨五入、十六進位的七捨八入，二進位便是零捨一入。在這次的轉換中是對 fraction 中的第 8 位元做進位，若為 1 要進位，若為 0 則捨棄。

  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; // BB1
      r /= 256;
      y = x + r;

      *py &= 0xffff0000; // BB2
      return y;
  }

  void print_hex(float x) {
      int *p = (int *) &x;
      printf("%f=%x\n", x, *p);
  }

  int main() {
      float a[] = {3.140625, 1.2, 2.31, 3.46, 5.63};
      for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) {
          print_hex(a[i]);
          float bf_a = fp32tobf16(a[i]);
          print_hex(bf_a);
      }

      return 0;
  }

因此 Line 3, 14 都是為了對浮點數做位元運算而做的型別轉換
Line7, 9 是對浮點數中的特殊值先做判斷
Line13~20 是要對 FP32 做進位判斷並捨去 fraction 後面 16 位元(從 MSB 數來第 8 個位元開始捨棄)，便完成 bfloat16 的轉換
本次轉換是對 fraction 中從 MSB 向 LSB 數第 8 個位元做進位判斷，而對二進制來說就是對該位元加 1，原本若是 0 不會進位；原本是 1 便會進位。
首先我知道回傳的 `y` 相當於 bfloat16 的值，其應是先完成進位，然後再捨去後面 16 位元，故 `BB2` 的行為是使後面 16 位元歸零的 `0xffff0000`
再來可從進位的數學式來推測 `BB1` 的行為：
我們想要把 b~8~ 加一：$y = (-1)^S \times 2^E \times (1.b_1b_2b_3b_4b_5b_6b_7(b_8+1)...b_{23})_2$
將加一取出相當於：$y = (-1)^S \times 2^E \times (1.b_1b_2b_3b_4b_5b_6b_7b_8...b_{23})_2 + (-1)^S \times 2^E \times 2^{(-8)} = x + (-1)^S \times 2^E \times 2^{(-8)} = x + r$
所以可知 `r` 就是將輸入 `x` 的 fraction 歸零，並且乘以 2^(-8)^
`BB1` 就是將 fraction 歸零，只留 sign, exponent 部分的 `0xff800000`

## 測驗 `2`: [ring buffer](https://en.wikipedia.org/wiki/Circular_buffer)
* 又稱 circular buffer，為固定大小、環狀、且可用來儲存資料的結構
本題中 buffer 定義了 int size, int start, int end, T \*elements 這些成員變數， 其中 start 與 end 分別代表第一筆資料與最後一筆資料的 index，其中因為其結構是環狀的，故需要特別注意的地方是判斷 buffer 為空或滿的情況。
* `RB1` 是指當 start 的 index 不等於 size 時表示 start 的下一個 index 還不會回到 0，故 `NEXT_START_INDEX(BUF)` 等於 `(BUF)->start + 1`
`RB2` 則是與 start 一模一樣的方式來判斷 `end`，故 `NEXT_END_INDEX(BUF)` 等於 `(BUF)->end + 1` 或 等於 `0`

## 測驗 `3`: Sort singly-linked list
本題在 macro 中使用了 **Compound literals** 去建立 static linked list

#define cons(x, y) (struct llist[]){{y, x}}

Compound literals 在 C 語言[規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)中 6.5.2.5 節介紹到：
* 小括號 "( )" 內的是型別，且大括號 "{ }" 內的是初始序列的寫法，稱作 Compound literals，他可以透過初始序列去定義無名的物件
* 並且 compound literals 是 lvalue，可以通過如取址運算去存取 (如 & operaiton)
> * A postfix expression that consists of a parenthesized type name followed by a braceenclosed list of initializers is a compound literal. It provides an unnamed object whose value is given by the initializer list.
> * If the type name specifies an array of unknown size, the size is determined by the
initializer list as specified in 6.7.8, and the type of the compound literal is that of the
completed array type. Otherwise (when the type name specifies an object type), the type
of the compound literal is that specified by the type name. In either case, the result is an
lvalue.

因此，一個 `cons(x, y)` 便會建立 `val = y`, `next = x` 的 `struct llist` 陣列
而若將本題中的`struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D)` 逐一展開

// 展開 cons(cons(cons(cons(NULL, A), B), C), D)
list->val = D;
list->next = &cons(cons(cons(NULL, A), B), C);

// 展開 cons(cons(cons(NULL, A), B), C)
list->val = C;
list->next = &cons(cons(NULL, A), B);

// 展開 cons(cons(NULL, A), B)
list->val = B;
list->next = &cons(NULL, A);

// 展開 cons(NULL, A)
list->val = A;
list->next = NULL

如此形成一個 linked list

digraph linkedList{
    node[shape=box]
    NULL[label=NULL, shape=plaintext]
    rankdir=LR
    D->C->B->A->NULL
}

故根據題目中 linked list 順序可知分別對應到 `D = (a) 9`, `C = (b) 5`, `B = (c) 4`, `A = (d) 7`

在接下來的程式碼中是要對 linked list 進行由小到大排序，排序的程式包含 `sorted_insert` 與 `sort` 兩個函式，且根據排序的方式可判斷出使用的是 **insertion sort**。
`sort` 將 linked list 中的元素逐一取出，插入到排序好的 list `sorted` 中；而 `sorted_lnsert` 便是決定將元素插入到哪個位置的函式。

void sorted_insert(struct llist **head, struct llist *node)
{
    if (!*head || (*head)->val >= node->val) {
        node->next = *head; // SS1
        *head = node  ; // SS2	
        return;
    }
    struct llist *current = *head;
    while (current->next && current->next->val < node->val)
        current = current->next;
    node->next = current->next;
    current->next = node;
}

void sort(struct llist **head)
{
    struct llist *sorted = NULL;
    for (struct llist *current = *head; current;) {
        struct llist *next = current->next;
        sorted_insert(&sorted, current);
        current = next;
    }
    *head = sorted;
}

Line 3 的條件式是在判斷當待排序元素的值比 `*head` 還小或它是第一個要排序的元素時，需要和 `*head` 做交換，此時會改變 `*head`。
因此 `SS1` 應是先將 `node->next` 指派為 `*head`，故此題為 `(d)`
而 `SS2` 是將 `*head` 指派為 `node`，故此題為 `(b)`

## 測驗 `4`: LeetCode 287. [Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)
本題要找到給定的數列中重複的那個數，且已知長度 n 的數列其數值範圍介於 1 到 n-1，重複的數值不一定只重複一次。

* 一般的寫法可能需要執行 $(n-1) \times n$ 次迴圈，也就是時間複雜度為 $O(n^2)$

    int findDuplicate_bad(int* nums, int numsSize){
        for (int i = 1; i < numsSize; i++)
        {
            int cnt = 0;
            for (int j=0; j<numsSize; j++)
            {
                if (i == nums[j])
                {
                    if (cnt == 1) return i;
                    cnt += 1;
                }
            }
        }
        return -1;
    }

* 本題的程式減少了最外層執行的次數，從原本是個別檢查 1 ~ (n-1) 是否有重複，改為只要執行 $\left \lceil{log_2(n)}\right \rceil$ 次，時間複雜度變成 $O(nlogn)$

    int findDuplicate_good(int *nums, int numsSize)
    {
        int res = 0;
        // 為何一定要 8*sizeof(int) 而不 32
        const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
        for (size_t i = 0; i < log_2; i++) {
            int bit = 1 << i;
            int c1 = 0, c2 = 0;
            for (size_t k = 0; k < numsSize; k++) {
                if (k & bit)
                    ++c1;
                if (nums[k] & bit)
                    ++c2;
            }
            if (c1 < c2) // CCC
                res += bit;
        }
        return res;
    }

Line 5 的 `log_2` 等於最大的數值其最高的 set bit 所在的位元數，這個數字相當於 $\left \lceil{log_2(n)}\right \rceil$，必定比 (n-1) 個數值來得少
接下來的兩層迴圈的原理是依次針對各個位元，比較 nums[0]~nums[n-1] 中的 set bit 數量 (c2) 與 0~n-1 中的 set bit 數量 (c1)，若在該位元中 c1 少於 c2，表示重複的數值在該位元是 set bit，故將 `res += bit`
* 可用表格來比較數值沒有重複與有重複的情形下，set bit 的差異，以 n = 4 為例：
在沒有數值重複的情況下，其 **位元 0** 的 set bit 有 2 個
| number | 位元 1 | 位元 0 |
| - | - | - |
| x | x | x |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
當重複的數字是 1 時，其 **位元 0** 的 set bit 數量會變多，重複其他值亦然。
| number | 位元 1 | 位元 0 |
| - | - | - |
| 1 | 0 | 1 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
也就是說，當有一個數值重複時，會使得相對應的位元 set bit 數量增加，此時就可以將這個位元所代表的十進位值 (`bit`) 累加到 `res`，再繼續下一個位元，故 `CCC` 為 `c1 < c2`

###### tags: `linux2020`