2020q3 Homework6 (quiz6)

contributed by < chi-ming5566 >

測驗題

---

測驗一

bfloat16 浮點數格式由 Google 公司發展，最初用於該公司第三代 Tensor 處理單元 (Cloud TPU)。bfloat16 的主要想法是提供 16 位元浮點數格式，其動態範圍與標準 IEEE 754 的 FP32 (Single-precision floating-point format) 相同，但精度較低，相當於指數區和 FP32 保持相同的 8 位元，並將 FP32 的 fraction 區域縮減到 7 位元。

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

• 第一段程式碼內的 5~10 行，屬於常規的確認是否為 0/INF/NAN 的判斷，處理完後，接著需要把精度轉換為bfloat 的 format。
• 因為我們無法直接對 float 的 bitwise operation，所以先用一個 int * 去指向 float r 的 address。
• 再來從後面y = x + r可以推測出，r 是一個維持精度的補償值，且 bfloat 的 fraction 只有 7 個 bits，所以我們只需要把 fraction 的第 8 個 bits 加回來即可。
• 而程式碼第 13 ~ 17 行則在做第 3 點的事情，因此BB1 = 0xff800000，另外 float 的r /= 256;是 exponent 減 8 的結果，而不是向右 shift 8 個 bits。
• 最後把 bloat 的格式存入 *py，因此BB2 = 0xffff0000。

---

測驗二

#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 的出現。

程式原理

解釋 ring buffer 運作模式

• ringbuf_write
  • 呼叫 ringbuf_write_peek，將 ELEMENT 放進 end 的位置。
  • 呼叫 ringbuf_write_skip，將 end 指向下一個位置。當 start == end 時，會將 start 指向下一個位置。
• ringbuf_read
  • 呼叫 ringbuf_read_peek，將 start 指向的 ELEMENT 讀出來。
  • 呼叫 ringbuf_read_skip，將 start 指向下一個位置。
• 使用到 NEXT_START_INDEX 或 NEXT_END_INDEX 時，都是為了把指針指向下一個位置，所以都需要做 +1 。

---

測驗三

#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

• 題目的 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;

---

測驗四

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

1. 假設陣列長度為 n，數值的範圍是 1 到 n−1.
2. 重複的數值不一定只重複一次
   考慮以下程式碼是可能的解法:

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

• log_2 是用來判別該數列的最大數值轉換成 2 進位共有幾個 bits ，因為後面會從右至左逐一 bit 來檢查。
• 再來看到程式碼第 8 ~ 13 行，根據鴿籠原理，有 n 個數字，其中數字的範圍式 1 ~ n-1，那麼這 n 個數字中必定有一個數字重複。
• 假設該重複的數字為 1 ，就檢查 n 個數字的最右邊的 bit 是否為 1 ，並把是 1 的次數加總，如果總和比 1 ~ n-1 最右邊 bit 為 1 的次數總和還多，那麼我們可以推測，該重複數字的最右邊 bit 必定是 1，而其餘 bit 也是如此。
• 第 14 行則是判斷上述條件是否達成，是的話累加進 res ，因此CCC為c1 < c2 。