2020q3 Homework6 (quiz6)

contributed by < ccs100203 >

tags: linux2020

第 6 週測驗題

測驗 1

將 FP32 轉換為 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;
}

以下為測試程式

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

• int *py = (int *) &y; 利用 pointer 的方式去做轉換，而不是做 int py = (int) y; ，差別在於後者會無條件捨去至整數，而前者會將 IEEE 754 的 bit 完整保留至 py 內。做轉換的目的在於對 integer 做 bitwise 操作，因為 float 不能做 bitwise 的操作。

• exp 及 man 分別是指數與尾數的部分，用來判斷 Boundary value，排除掉 Normalized number 以外的數值，參照以下的表
  

• 再來要對 Normalized number 做 round，這邊做 round 的方式是

  1. 利用 *pr &= 0xff800000; 只保留 sign 與 exp 的部分
  2. 接著 r /= 256 是為了 rounding。原理是在經過上面只保留前面後，r 會是
     $2^n\ast 1.00000...$ 在 IEEE 754 的規範中他會是第 9 位，這時做 r /= 256 變成
     $2^{n-8}\ast 1.00000...$ 後他會是 BFloat 16 規範外的第一個 bit，此時利用他與原本的 x 做相加就可以判定最後是否進位。
     只保留 sign 與 exp 的r 會是
     $0\stackrel{\text{8}}{\overbrace{xxxxxxxx}}\stackrel{\text{7}}{\overbrace{0000000}}$，故除 256 之後就會是 BFloat 16 外的第一個位置
  3. 將原本的數值 x 加上剛剛運算出的值 assgin 給 y
  4. 利用 *py &= 0xffff0000; 只保留 y 最前方的 16 bits，以符合 BFloat 16 的規範

測驗 2

ring buffer

#define RINGBUF_DECL(T, NAME) \
    typedef struct {          \
        int size;             \
        int start, end;       \
        T *elements;          \
    } NAME

#define RINGBUF_INIT(BUF, S, T)             \
    {                                       \
        static T static_ringbuf_mem[S + 1]; \
        BUF.elements = static_ringbuf_mem;  \
    }                                       \
    BUF.size = S;                           \
    BUF.start = 0;                          \
    BUF.end = 0;

#define NEXT_START_INDEX(BUF) \
    (((BUF)->start != (BUF)->size) ? ((BUF)->start + RB1) : 0)
#define NEXT_END_INDEX(BUF) (((BUF)->end != (BUF)->size) ? ((BUF)->end + RB2) : 0)

#define is_ringbuf_empty(BUF) ((BUF)->end == (BUF)->start)
#define is_ringbuf_full(BUF) (NEXT_END_INDEX(BUF) == (BUF)->start)

#define ringbuf_write_peek(BUF) (BUF)->elements[(BUF)->end]
#define ringbuf_write_skip(BUF)                   \
    do {                                          \
        (BUF)->end = NEXT_END_INDEX(BUF);         \
        if (is_ringbuf_empty(BUF))                \
            (BUF)->start = NEXT_START_INDEX(BUF); \
    } while (0)

#define ringbuf_read_peek(BUF) (BUF)->elements[(BUF)->start]
#define ringbuf_read_skip(BUF) (BUF)->start = NEXT_START_INDEX(BUF);

#define ringbuf_write(BUF, ELEMENT)        \
    do {                                   \
        ringbuf_write_peek(BUF) = ELEMENT; \
        ringbuf_write_skip(BUF);           \
    } while (0)

#define ringbuf_read(BUF, ELEMENT)        \
    do {                                  \
        ELEMENT = ringbuf_read_peek(BUF); \
        ringbuf_read_skip(BUF);           \
    } while (0)

對應的測試程式:

#include <assert.h>

RINGBUF_DECL(int, int_buf);

int main()
{
    int_buf my_buf;
    RINGBUF_INIT(my_buf, 2, int);
    assert(is_ringbuf_empty(&my_buf));

    ringbuf_write(&my_buf, 37);
    ringbuf_write(&my_buf, 72);
    assert(!is_ringbuf_empty(&my_buf));

    int first;
    ringbuf_read(&my_buf, first);
    assert(first == 37);

    int second;
    ringbuf_read(&my_buf, second);
    assert(second == 72);

    return 0;
}

為什麼需要 do {...} while(0)

根據 do/while(0) vs scope block 的解釋，使用這個寫法可以避免 dangling else 的出現。

if (<condition>)
  call_macro(a);
else
  bar(a);

如果 macro 內只使用 { }，程式展開後會變成

if (<condition>)
{
    statements
};
else
  bar(a);

可以注意大括號後面會有 ;，這會導致 if 判斷式到這裡就結束，else 獨立出來而導致編譯失敗。
一個解決方法是拿掉呼叫 macro 時的 ;，但這並不是一個優雅的解法，因為這會導致 coding style 不一致。

if (<condition>)
  call_macro(a)
else
  bar(a);

較為優雅的解法就是使用 do while(0)，要注意第 4 行， macro 內的 while(0) 後方不能有 ;，否則將失去這樣寫的用意。可以看到程式展開之後將變成下面的樣子

#define call_macro(x) \
do { \
  statements \
} while (0)

if (<condition>)
    do{
        statements
    }while(0);
else
  bar(a);

程式原理

解釋 ring buffer 運作模式

• ringbuf_write
  • 呼叫 ringbuf_write_peek，將 ELEMENT 放進 end 的位置
  • 呼叫 ringbuf_write_skip，將 end 指向下一個位置。當 start == end 時，會將 start 指向下一個位置，我想是因為 buffer 滿了，捨棄掉 buffer 內存放最久的 element。
• ringbuf_read
  • 呼叫 ringbuf_read_peek，將 start 指向的 ELEMENT 讀出來
  • 呼叫 ringbuf_read_skip，將 start 指向下一個位置。
• 使用到 NEXT_START_INDEX 或 NEXT_END_INDEX 時，都是為了把指針指向下一個位置，所以都需要做 + 1，由此可以選出答案。

好奇 ringbuf_read_skip 並不像 ringbuf_write_skip 當 buffer 在極值時有做判斷。如果 buffer 是空的而直接做 ringbuf_read，start 就會領先 end，變成要繞一圈 buffer 才會讀到後來 ringbuf_write 放入的值。

測驗 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) {
        node->next = *head;
        *head = node;	
        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, 7), 4), 5), 9);
    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

• 這題使用到 compound literal 的技巧，#define cons(x, y) (struct llist[]){{y, x}}，不過老師為了看大家夠不夠細心故意把 x, y 相反哈哈。

• 題目的 sort 是做 insertion sort，巡遍整個 linked-list 由小到大排序，題目問的部分是當他為 第一個值 or 最小的值，要放在 linked-list 最前面時要怎麼做。由於 node 要放到最前面，所以直接將 node->next 接上 *head，接著要對 *head 進行更新，所以 assign node 給 *head。

if (!*head || (*head)->val >= node->val) {
    node->next = *head;
    *head = node;
    return;
}

• 剩下的部分是 node 要插入在第一個位置以外的地方的情況，就是會先在 list 內不斷往後找直到有 value 比要插入的 node 大，或是已經巡遍到最後了，就會把 node 插入。

while (current->next && current->next->val < node->val)
    current = current->next;
node->next = current->next;
current->next = node;

測驗 4

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

1. 假設陣列長度為
   $n$，數值的範圍是
   $[1,n-1]$
2. 重複的數值不一定只重複一次
3. 範圍內的其他數字都只會出現一次

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 (c1 < c2)
            res += bit;
    }
    return res;
}

程式利用每個 bit 出現的次數去比對此數字有沒有出現過多次，當 理論上會出現的次數 (c1) < 實際上出現的次數 (c2) 時，代表這個 bit 出現次數過多，即為答案內的 bit。

理論上會出現的次數(c1): 1 ~ numsSize 的數字每個 bit 的總和，
e.g. 1~3

decimal	binary
1	0001
2	0010
3	0011

每個 bit 的總和就會是 0 0 2 2

• 以下是一步一步解說:

1. log2 是為了知道總共需要比較幾個 bit
2. bit = 1 << i 這邊就是每一次迴圈需要比對的 bit
3. 第 8 行的迴圈會跑遍 numsSize 內的所有數字，當前比較的 bit 的出現數量會被紀錄，在 c1 會記錄範圍內數字的 bit 出現數量，而 c2 則是記錄 nums 裡數字的 bit 出現數量。
4. 有了兩者的出現數量，就可以用 if (c1 < c2) 判斷當前的 bit 是否為出現次數過多的 bit，把當前的 bit 加進去 res 內。

運用 GNU extension 改善程式

上述的程式碼的時間複雜度為

$O(nlogn)$，空間複雜度為

$O(1)$

• 時間複雜度為
  $O(n)$，空間複雜度為
  $O(n)$
  宣告一條長度與 numsSize 相同的陣列去紀錄每個數字是否有出現過，缺點明顯，耗費記憶體空間

int findDuplicate(int *nums, int numsSize)
{
    int* arr = malloc((numsSize+1) * sizeof(int));
    for(int i=0; i<numsSize+1; ++i)
        arr[i] = 0;
    for(int i=0; i<numsSize; ++i){
        if(!arr[nums[i]-1])
            arr[nums[i]-1] = 1;
        else
            return nums[i];
    }
    return 0;
}

• 其他方法，正在思考 TODO