owned this note
owned this note
Published
Linked with GitHub
# 2020q3 Homework6 (quiz6)
contributed by < `CW-B-W` >
###### tags: `sysprog2020`
## Outline
[TOC]
## 測驗`1`
### bfloat16
* 將 float 的 `bit22~bit0` 截到剩 `bit22~bit16`
* BB1 = `0xff800000`
* ???
* BB2 = `0xffff0000`
* 將處理後的 float 截取成 bfloat16,即只將前 16bits 留下
```cpp=
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;
}
```
## 測驗`2`
### ring buffer
* RB1 = `1`
* `NEXT_START_INDEX(BUF)` 用來取得下一個 start 的位置,故為 `+1`
* RB2 = `1`
* `NEXT_END_INDEX(BUF)` 用來取得下一個 end 的位置,故為 `+1`
```cpp=
#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;
}
```
## 測驗`3`
### singly-linked list
* 注意這裡的 `cons(x, y)` 是 `{{y, x}}`
* 故建構順序為
* A->NULL
* B->A->NULL
* C->B->A->NULL
* D->C->B->A->NULL
* 初始 list 為 9547,故插入順序為
* A = `7`
* B = `4`
* C = `5`
* D = `9`
* SS1 = `node->next = *head`
* SS2 = `*head = node`
* 邊界條件處理
* 當 list 為空時
* 當插入的 node 該成為新的 head 時
* `node->next = *head` 將 `新的head` 指向 `舊的head`
* `*head = node` 將 `舊的head` 更新為 `新的head`
```cpp=
#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;
}
```
## 測驗`4`
### LeetCode 287. Find the Duplicate Number
* 只有一個重複數字 (稱之為 `x`),且數字範圍為 `[0, n)`
* 此作法對每一個 `bit i` 做判斷, i = [0, 32)
* `if (k & bit) ++c1` 計算 [0, n) 裡面存在 `bit i` 的數字數量
* `if (nums[k] & bit) ++c2` 計算 nums[] 裡面存在 `bit i` 的數字數量
* 如果發現 c2 多於 c1 ,則代表 `x` 裡面必存在 `bit i`,因為 `x` 重複多次,造成 `bit i` 多次被計算到
* CCC = `c1 < c2`
```cpp=
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;
}
```