2022q1 Homework3 (quiz3)

contributed by < eric88525 >

第 3 週測驗題

Q1

#define GENMASK(h, l) \
    (((~0UL) >> (63 - h)) & ((~0UL) >> (l) << (l))) // (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))

從最低位元到 l 位元需要為 0，可判斷 shift left 應該為 l 次，先 shift right
～0UL 為 0XFFFFFFFFFFFFFFFF 且是無號數，右移 63-h 位元可讓 h 到最高位元為0
做 and 運算可留下左右方的 0 ，並保留共通的 1

仔細思考後認為 (~0UL) >> (l) << (l)) 可以寫成 (~0UL) << (l) ，原因是 (~0UL) >> (l) << (l)) 後，結果為最低位元到 l 為 0 其餘為 1，跟(~0UL) << (l)) 的結果一樣的

Q2

struct foo;
  
struct fd {
    struct foo *foo;
    unsigned int flags;
};

enum {
    FOO_DEFAULT = 0,
    FOO_ACTION,                           
    FOO_UNLOCK,
} FOO_FLAGS;

static inline struct fd to_fd(unsigned long v)
{
    return (struct fd){(struct foo *)(v&~3), v & 3}; // return (struct fd){EXP1, v & 3};
}

向下對齊 4 bytes 規律：
- 0～3 對齊到0
- 4～7 對齊到4
- 8～11 對齊到 8
可以觀察到只要把最後兩個位元設成0即可對齊，因此要 &~3 並轉形成struct 定義的型態

Q3

#include <stdint.h>
uint8_t rev8(uint8_t x)
{
    x = (x >> 4) | (x << 4);     
    x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2); // x = ((x & 0xCC) >> 2) | (EXP2);
    x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1); // x = ((x & 0xAA) >> 1) | (EXP3);
    return x;
}

abcd efgh
// x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2)
efgh abcd
// ((x & 0xCC) >> 2) | ((x & 0x33) << 2)
ghef cdab
// x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1)
hgfe dcba

透過 & mask 來讓特定位元交換

Q4

#include <stdio.h>
#include <stdarg.h>
#include <assert.h>

#define _foreach_no_nullval(i, p, arr) \
    assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))

#define foreach_int(i, ...)                                            \
    for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \
         _foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int);      \
         (i) = ((int[]){__VA_ARGS__, 0})[++_foreach_i])

#define foreach_ptr(i, ...)                                                 \
    for (unsigned _foreach_i =                                              \
             (((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
         (i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__,            \
                                                    NULL})[++_foreach_i],   \
                  _foreach_no_nullval(_foreach_i, i,                        \
                                      ((const void *[]){__VA_ARGS__})))

int main()
{
    int i;
    char *p;
    
    foreach_int(i, 0, -1, 100, 0, -99)
        printf("i is %i\n", i);
    
    foreach_ptr(p, "Hello", "world")
        printf("p is %s\n", p);

    return 0;
}

__VA_ARGS__ 用於將 macro 中的 ... 展開
在 for 迴圈中：
- 用於遍歷的變數為 _foreach_i ，因此要在每次迴圈結束都+1，也就是 ++_foreach_i
- _foreach_i 上限為 sizeof((int[]){__VA_ARGS__}) / sizeof(int); ，求得整個 int 陣列的元素數量
編譯時在預處理停止，可以看到 macro 會有以下展開，在宣告 _foreach_i 時很巧妙的透過 () 和＝的特性，先讓 i 等於陣列的第 0 元素，接著把 0 指派給 _foreach_i

for (unsigned _foreach_i = (((i) = ((int[]){0, -1, 100, 0, -99})[0]), 0); _foreach_i < sizeof((int[]){0, -1, 100, 0, -99}) / sizeof(int); (i) = ((int[]){0, -1, 100, 0, -99, 0})[_foreach_i++])
    printf("i is %i\n", i);

Q5

#include <limits.h>
int divide(int dividend, int divisor)
{
    int signal = 1;
    unsigned int dvd = dividend;
    if (dividend < 0) {
        signal *= -1;
        dvd = ~dvd + 1;
    }

    unsigned int dvs = divisor;
    if (divisor < 0) {
        signal *= -1;
        dvs = ~dvs + 1;
    }

    int shift = 0;
    while (dvd > (EXP6))
        shift++;

    unsigned int res = 0;
    while (dvd >= dvs) {
        while (dvd < (dvs << shift))
            shift--;                         
        res |= (unsigned int) 1 << shift;
        EXP7;
    }

    if (signal == 1 && res >= INT_MAX)
        return INT_MAX;
    return res * signal;
}

Q6

Q7


















int ilog32(uint32_t v)
{
    int ret = v > 0;
    int m = (v > 0xFFFFU) << 4;
    v >>= m;
    ret |= m;
    m = (v > 0xFFU) << 3;
    v >>= m;
    ret |= m;
    m = (v > 0xFU) << 2;
    v >>= m;
    ret |= m;
    m = (v > 0x3) << 1;
    v >>= m;
    ret |= m;
    ret += v > 1;
    return ret;
}

32 bit 為 0x0000 0000 ~ 0xFFFF FFFF , 0~31 bit

binary search 的概念，每次都先檢查 v 是否大於
$n / 2$ 的位元數，確認是否在0~n-1 或是 n~最高位元。 n 初始為32，每當檢查完一輪， n 都會除以2
line 4-6 7-9 10-12 13-15 是做相同的事情，先檢查 v 所含位元，是否大於 v 可能有的最高位元數的一半，舉例：
- 第4行先檢查 v 有無大於 32bits 的一半，也就是 0xffff ，第7行檢查 v 有無大於 16bits 的一半，也就是 0xff
每次檢查完如果有大於一半的位元數，用 ret 來紀錄至少含有的位元數:
- line 4 v > 0xFFFF 可確定最高位元至少會大於 1<<4 bit，也就是 16 bit，用 ret 紀錄下來

Q8



























void remove_data(tree &t, int d)
{
    tnode **p = &t;
    while (*p != 0 && (*p)->data != d) {
        if (d < (*p)->data)
            p = &(*p)->left; // EXP12;
        else
            p = &(*p)->right; // EXP13;
    }
    tnode *q = *p;
    if (!q)
        return;

    if (!q->left)
        *p = q->right;
    else if (!q->right)
        *p = q->left;
    else {
        tnode **r = &q->right;
        while ((*r)->left)
            r = &(*r)->left; // r = EXP14;
        q->data = (*r)->data;
        q = *r;
        *r = q->right;
    }
    delete q;
}

根據二元樹的規則，節點右側會大於當前節點，左邊則是小於。因此在 line:5 比較完數值後，要選擇往右或是往左走
EXP14 為讓 **r 在 d 節點右邊 subtree 中，往走找到最小值
假設 d 為15，15 右邊 subtree 的最小數值為18

把目標替換成 subtree 的最小數值

Q9

/* maximum alignment needed for any type on this platform, rounded up to a
   power of two */
#define MAX_ALIGNMENT 16

/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
    (((x) + MAX_ALIGNMENT - 1u) & ~(MAX_ALIGNMENT - 1u))

題目要求為 roundup
- ROUND_UP_TO_ALIGNMENT_SIZE(1~16) = 16
- ROUND_UP_TO_ALIGNMENT_SIZE(17~32) = 32
- ROUND_UP_TO_ALIGNMENT_SIZE(33~48) = 48

MAX_ALIGNMENT 的二進位為 0x10000 ，減一後 0x1111，可以把不足16的部分強制進位
進位後需要保留 0x10000 以後的資訊，因此要 & ~(MAX_ALIGNMENT - 1u) ，讓0~3bit 為0，4bit 以上保留

    0x0000100
+   0x0001111
-----------
    0x0010011
&   0x1110000
-------------
    0x0010000

Q10









#define DIVIDE_ROUND_CLOSEST(x, divisor)                       \
    ({                                                         \
        typeof(x) __x = x;                                     \
        typeof(divisor) __d = divisor;                         \
        (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
         (((__x) > 0) == ((__d) > 0)))                         \
            ? (((__x) + ((__d) >> 1)) / (__d))                  \
            : (((__x) - ((__d) >> 1)) / (__d));                 \
    })

line 3-4:
- 先用暫存變數存 x 數值，避免在後續展開時被更動，例如輸入 x++，在後續每次被使用時數值都會變動
line 5: 檢查 signed 或是 unsigned，如果 unsigned 條件會為 true
- signed int -1 = -1
- unsigned int -1 = 4294967295
line 6:
- 判斷正負號是否相同
line 7-8: 這段可視為 (__x / __d) ± 0.5
- 如果 x / divisor 為負，-0.5 來達到四捨五入
- 如果 x / divisor 為正，+0.5 來達到四捨五入