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

###### tags: `homework`

## 測驗 1

轉換程式

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

    *py &= 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;
}

輸出

3.140625=40490000
3.140625=40490000
1.200000=3f99999a
1.203125=3f9a0000
2.310000=4013d70a
2.312500=40140000
3.460000=405d70a4
3.453125=405d0000
5.630000=40b428f6
5.625000=40b40000

### 1. 解釋上述程式碼的運作機制

    exp = *py & 0x7F800000u;
    man = *py & 0x007FFFFFu;
    if (!exp && !man) /* zero */           
        return x;
    if (exp == 0x7F800000u) /* infinity or NaN */
        return x;

- 從 fp32 取出 exp 和 mantissa
- 透過檢查 exp 和 mantissa 來確認此 fp32 值是否為 0 或 特殊值

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

- 取出 sign 和 exp，共前 9 個 bit，BB1 = 0xff800000 = 0b[1][11111111]000...
- e.g. 1.200000f = 0b3f99999a，與 0xff800000 & 運算後得 0x3f800000，即 1.000000f
- r /= 256 相當於對 exp - 8，得 0x3b800000，即 0.003906f，將 Normalized Number 或 Denormalized Number 的 .. 除 256 做正規化
- 再將正規化後的小數加上去得到最佳精度

`*py &= BB2;` 而 bfloat16 為 16 bit，因此取 y 的前 16 bit (signed number, exp, mantissa)，故 BB2 為 0xffff0000

---

## 測驗 3
考慮到以下靜態初始化的 singly-linked list 實作:

#include <stdio.h>

/* clang-format off */
#define cons(x, y) (struct llist[]){{y, x}}
/* clang-format on */

struct llist {
    int val;
    struct llist *next;
};

void sorted_insert(struct llist **head, struct llist *node)
{
    if (!*head || (*head)->val >= node->val) {
        SS1;
        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;
}

int main()
{
    struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D);
    struct llist *p;
    for (p = list; p; p = p->next)
        printf("%d", p->val);
    printf("\n");

    sort(&list);
    for (p = list; p; p = p->next)
        printf("%d", p->val);
    printf("\n");
    return 0;
}

> 其執行結果為:
> 9547
> 4579

### 1. 解釋上述程式碼的運作機制

參照 [C 語言程式設計技巧](https://hackmd.io/@sysprog/c-trick)

**「靜態」的 linked list**

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

- 利用 compound literal 建立 static linked list
- 可針對未知大小的 array/struct 初始化，也可以直接對特定位置的 array 或 struct 的內容賦值
- compound literal 可以做 lvalue ，可以傳特定型別或自己定義的 struct

> C99 [6.5.2.5] Compound literals
> - The type name shall specify an object type or an array of unknown size, but not a variable length array type.
> - 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.

將 ``` struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D); ``` 展開如下

// 展開 cons(cons(cons(cons(NULL, A), B), C), D)
llist.val = D;
llist.next = &cons(cons(cons(NULL, A), B), C);

// 展開 cons(cons(cons(NULL, A), B), C)
llist.val = C;
llist.next = &cons(cons(NULL, A), B)

// 展開 cons(cons(NULL, A), B)
llist.val = B;
llist.next = &cons(NULL, A);

//展開 cons(NULL, A)
llist.val = A;
llist.next = NULL;

digraph structs {
    rankdir=LR;
    node[shape=record];
    node1 [label="{<val> D | <next> &cons(cons(cons(NULL, A), B), C)}"]
    node2 [label="{<val> C | <next> &cons(cons(NULL, A), B)}"]
    node3 [label="{<val> B | <next> &cons(NULL, A)}"]
    node4 [label="{<val> A | <next> NULL}"]
    
    node1:next -> node2:val node2:next -> node3:val node3:next -> node4:val
}

- 結果輸出為 9547 ，故 D = 9、C = 5、B = 4、A = 7

**Insertion Sort**
> 將第 i 筆資料插入前 i - 1 筆已完成排序好的資料中

- ```#34 *head = sorted;``` **變數 sorted 為指向已排序好的 list 之 head**，因此在最後時必須將其指派給 *head
- ``` sorted_insert(&sorted, current);``` **變數 current 指向尚未完成排序的 list 之 head**，將其插入已完成排序的 list 中

- 考慮下列情況來思考 SS1 和 SS2

digraph structs {
    rankdir=LR;
    node[shape=box];
    node1 [label=" 9 "]
    node2 [label=" 5 "]
    node3 [label=" 4 "]
    node4 [label=" 7 "]
    null  [label="NULL "]
    sorted[label="*head(sorted)"]
    current[label="node"]
    
    {
        rank = "same";
        sorted -> node2;        
    }
    node2 -> node1
    
    {
        rank = "same";
        current -> node3;
    }
    node3 -> node4 -> null 
}

void sorted_insert(struct llist **head, struct llist *node)
    if (!*head || (*head)->val >= node->val) {
        SS1;
        SS2;	
        return;
    }
    ...

digraph structs {
    rankdir=LR;
    node[shape=box];
    node1 [label=" 9 "]
    node2 [label=" 5 "]
    node3 [label=" 4 "]
    node4 [label=" 7 "]
    null  [label="NULL "]
    sorted[label="*head(sorted)"]
    current[label="node"]
    
    {
        rank = "same";
        sorted -> node2;        
    }
    node2 -> node1
    
    {
        rank = "same";
        current -> node3;
    }
    node3 -> node2
    node4 -> null 
}

digraph structs {
rankdir=LR;
node[shape=box];
node1 [label=" 9 "]
node2 [label=" 5 "]
node3 [label=" 4 "]
node4 [label=" 7 "]
null [label="NULL "]
sorted[label="*head(sorted)"]
current[label="node"]

{
rank = "same";
sorted -> node3;
}
node2 -> node1
current -> node3;
node3 -> node2
node4 -> null
}

---
## 測驗 4

LeetCode 287. Find the Duplicate Number 給定一個整數序列，其中會有一個數值重複，請找出。

已知條件：
1. 假設陣列長度為 n，數值的範圍是 1 到 n−1
2. 重複的數值不一定只重複一次


> Example 1:
> Input: nums = [1,3,4,2,2]
> Output: 2
> 
> Example 2:
> Input: nums = [3,1,3,4,2]
> Output: 3
> 
> Example 3:
> Input: nums = [1,1]
> Output: 1
> 
> Example 4:
> Input: nums = [1,1,2]
> Output: 1

考慮以下程式碼是可能的解法:

int findDuplicate(int *nums, int numsSize)
{
int res = 0;
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 (CCC)
res += bit;
}
return res;
}

### 1. 解釋上述 LeetCode 題目和程式碼的運作機制，指出改進空間並實作

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;
}

- c2 表示第 k 個數之第 i 位 bit 出現次數
- 由於**數值的範圍是 1 到 n−1**，n 為陣列長度，因此 c1 用來表示在此範圍的**每個數值之第 i 位 bit 出現次數**
    e.g. Input: nums = [3,1,2,x]，numsSize = 4，數值範圍 1 到 3
    **bit = 001**
    |    k     |   k & bit  | nums[k] & bit |
    | -------- | ---------- | ------------- |
    | 000 (0)  | 0 (c1 = 0) | 1 (c2 = 1)    | 
    | 001 (1)  | 1 (c1 = 1) | 1 (c2 = 2)    |
    | 010 (2)  | 0 (c1 = 1) | 0 (c2 = 2)    |
    | 011 (3)  | 1 (c1 = 2) | ? (c2 = 2+?)  | 
- ``` if (CCC) res += bit; ```   
    - x 可能是 1, 2, 3 其中一個數，我們也知道在此範圍中 c1 的值固定為 2，由 1 和 3 提供
    - 所以當 x 為 1 或 3 時，第 0 位的 bit 為 1，此時 c2 會大於 c1
    - 因此考慮所有 c2 > c1 的 i ，重複的值可用 $\sum2^i$ 表示
    - e.g. x = 3，則 $res = 2^0 + 2^2$ 

---