2022q1 Homework3 (quiz3)

contribute by < Korin777 >

測驗一

在 Linux 核心原始程式碼，include/linux/bitfield.h 提及一個巨集 GENMASK，其作用是依據給定的範圍，產生連續的 bitmask，例如:

GENMASK(6, 4) 產生
$01110000_{2}$
GENMASK(39, 21) 產生 0x000000ffffe00000 (64 位元)
已知我們使用的微處理器架構為 64 位元，且 unsigned long 為 8 位元組寬度 (符合 LP64 資料模型)，以下是可能的 GENMASK 巨集的定義:

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

~0UL 每個位元皆為 1,而 GENMASK 則會將 h ~ l 以外的位元都變為 0
先將一個 ~0UL 的 63 ~ h 位元(不包括 h)變為 0 => (~0UL) >> (63 - h)
再將另一個 ~0UL 的 l ~ 0 位元(不包括 l)變為 0 => (~0UL) >> (l) << (l)
對前兩數做 & 運算即可獲得題目所求 => ((~0UL) >> (63 - h)) & ((~0UL) >> (l) << (l))

測驗二

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

align_down : A value at or before value that is a multiple of alignment.
題目要求第一個成員的地址對 4 個位元組進行向下對齊 , 所以該地址必為 4 的倍數且比 v 小 , 即 v 的最後兩個 bit 應為 0
~3 二進位表示中 , 第 0 及第 1 個 bit 為 0 其餘皆為 1 , 因此 v & ~3 能夠確保地址為 4 的倍數且比 v 小

測驗三

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

0xCC = 11001100 0x33 = 00110011
0xAA = 10101010 0x55 = 01010101

先將 x 分為兩半 , 左半邊的 bit 與右半邊互換 , 此時 x 被分為兩塊
將分出來的兩塊在各別切為兩半 , 左半邊的 bit 與右半邊互換 , x 被分為四塊 0xCC = 11001100 0x33 = 00110011
將分出來的四塊在各別切為兩半 , 左半邊的 bit 與右半邊互換 , x 被分為八塊 , 而各塊皆為 1 bit , 反轉完成
e.g : 11010010
1101 | 0010 => 00101101
00|10 11|01 => 10000111
1|0 0|0 0|1 1|1 => 01001011

測驗四

#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__})))

foreach_int 即 foreach_ptr 為 Variadic Macros 可以傳入可變數量的參數(即 ... 可為零或多個) , 而在最後被命名的 argument(即 i) 後的所有 argument(包含他們之間的逗號) 會被前處理器展開到有 __VA_ARGS__ 的地方
(((int[]){__VA_ARGS__})[0]) 即展開為 (((int[]){0, -1, 100, 0, -99})[0]) 也就是 array ((int[]){0, -1, 100, 0, -99}) index 0 的值
_foreach_i 會被 assign 成 (((i) = ((int[]){__VA_ARGS__})[0]), 0) 括號中最後的那個值 , 也就是 0
for 迴圈每跑完一次 i 就要改為 array 下一個 index 的值 , 因此 _foreach_i 要先加 1(即 ++_foreach_i)

測驗五

#include <limits.h>
// dividend / divisor
int divide(int dividend, int divisor)
{
    int signal = 1; // 商的正負
    // 確保 dvd dvs 為正數 dvd / dvs
    unsigned int dvd = dividend;
    if (dividend < 0) { // 被除數為負數
        signal *= -1;
        dvd = ~dvd + 1; // dvd = -dvd
    }
    unsigned int dvs = divisor;
    if (divisor < 0) { // 除數為負數
        signal *= -1;
        dvs = ~dvs + 1; // dvs = -dvs
    }
    int shift = 0;
    while (dvd > (dvs << shift)) // 找出 divisor 乘以 2 的多少次方後會大於 dividend
        shift++;
    unsigned int res = 0;
    while (dvd >= dvs) { // 找出 dividend 除以 divisor 的商之二進位表示中 bit 為 1 的位元 , 並將 res 對應的位元設成 1
        while (dvd < (dvs << shift))
            shift--;                         
        res |= (unsigned int) 1 << shift;
        dvd -= dvs << shift;
    }
    if (signal == 1 && res >= INT_MAX) // 避免 -2147483648 / -1 = 2147483648 => overflow
        return INT_MAX;
    return res * signal;
}

找出 dividend 除以 divisor 的商之二進位表示中 bit 為 1 的位元 , 並將 res 對應的位元設成 1
e.g :
$101 \div 5 = 20 = 5 \times 2^{4} + 5 * 2^{2} = 10100_{2}$ = res

測驗六

static bool can_insert(struct list_head *head, int p1, int p2)
{
    struct point_node *pn;
    list_for_each_entry (pn, head, link)
        return p1 == pn->p1; 
    return true;
}
static int maxPoints(struct Point *points, int pointsSize)
{
    if (pointsSize <= 2)
        return pointsSize;

    int i, j, slope_size = pointsSize * pointsSize / 2 + 133;
    int *dup_cnts = malloc(pointsSize * sizeof(int));
    int *hori_cnts = malloc(pointsSize * sizeof(int));
    int *vert_cnts = malloc(pointsSize * sizeof(int));
    int *slope_cnts = malloc(slope_size * sizeof(int));
    memset(hori_cnts, 0, pointsSize * sizeof(int));
    memset(vert_cnts, 0, pointsSize * sizeof(int));
    memset(slope_cnts, 0, slope_size * sizeof(int));

    for (i = 0; i < pointsSize; i++)
        dup_cnts[i] = 1;

    struct list_head *heads = malloc(slope_size * sizeof(*heads));
    for (i = 0; i < slope_size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (i = 0; i < pointsSize; i++) {
        for (j = i + 1; j < pointsSize; j++) {
            if (points[i].x == points[j].x)
                hori_cnts[i]++, hori_cnts[j]++;

            if (points[i].y == points[j].y)
                vert_cnts[i]++, vert_cnts[j]++;

            if (points[i].x == points[j].x && points[i].y == points[j].y)
                dup_cnts[i]++, dup_cnts[j]++;

            if (points[i].x != points[j].x && points[i].y != points[j].y) {
                int dx = points[j].x - points[i].x;
                int dy = points[j].y - points[i].y;
                int tmp = gcd(dx, dy);
                dx /= tmp;
                dy /= tmp;
                int hash = dx * dy - 1333 * (dx - dy);
                if (hash < 0)
                    hash = -hash;
                hash %= slope_size;
                if (can_insert(&heads[hash], i, j)) {
                    struct point_node *pn = malloc(sizeof(*pn));
                    pn->p1 = i;
                    pn->p2 = j;
                    list_add(&pn->link, &heads[hash]); 
                }
            }
        }
    }

    for (i = 0; i < slope_size; i++) {
        int index = -1;
        struct point_node *pn;
        list_for_each_entry (pn, &heads[i], link) {
            index = pn->p1;
            slope_cnts[i]++;
        }
        if (index >= 0)
            slope_cnts[i] += dup_cnts[index];
    }

    int max_num = 0;
    for (i = 0; i < pointsSize; i++) {
        if (hori_cnts[i] + 1 > max_num)
            max_num = hori_cnts[i] + 1;
        if (vert_cnts[i] + 1 > max_num)
            max_num = vert_cnts[i] + 1;
    }
    for (i = 0; i < slope_size; i++) {
        if (slope_cnts[i] > max_num)
            max_num = slope_cnts[i];
    }

    return max_num;
}

hori_cnts[i] : 用來記錄與點 i 在同一個水平線上的點數量
vert_cnts[i] : 用來記錄與點 i 在同一個鉛直線上的點數量
dup_cnts[i] : 用來記錄與點 i 重複的點數量
slope_cnts[i] : 用來記錄與點 i 在同個斜率 m 之線上的的點數量
heads[i] : 用來連結某個斜率下的所有點 point_node
static bool can_insert(struct list_head *head, int p1, int p2) : 用來判斷一個點該不該被加到 list_head[i]
- 每個 list_head[i] 一開始都可以插入點
- 當有一點插入 list_head[i] 後 , 除非 p1 為第一個插入的點 , 否則就不允許插入 , 這是因為 maxPoints 會先將 points[1~pointsSize-1] 中與 points[0] 斜率為 m 的點加入對應的 list_head[i] , 再來換看 points[1] , 而 points[1] 與 points[2~pointsSize-1] 一樣有斜率為 m 的點且對應到同一個 list_head[i] , 這時要是允許插入 , 就會出現點重複的情況
maxPoints : 求出 hori_cnts、vert_cnts、slope_cnts , 當中最大的即為 Max Points on a Line
註:
1.int hash = dx * dy - 1333 * (dx + dy) 應改為 int hash = dx * dy - 1333 * (dx - dy); , 否則 (0,0)、(3,4)、(4,3) 會被判斷再同意條線上 , 因 (0,0)、(3,4) 及 (0,0)、(4,3) hash 值相同
2.同樣斜率的多條不同的線只有第一條會被記錄
3.題目的點都是唯一的 , 所以可以不用計算 dup_cnts

測驗七

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 > 3) << 1;
    v >>= m;
    ret |= m;
    ret += v > 1;
    return ret;
}

題目要求最少需要多少位元才可儲存 , 即 32 位元中最高位元的 1 出現在哪一個 bit
ret : 最少需要多少位元才可儲存

每次將 v 尚未檢查的 bits 分為兩半 , 並看左半邊是否有值
有的話表示最高位元的 1 在左半邊 , 且我們需要右半邊的 bit 來儲存 v , 這時右半邊查看完畢 ; 沒有則表示最高位元的 1 在右半邊 , 這時左半邊查看完畢 , 重複步驟 1 直到剩兩個尚未檢查的 bit
最後兩個尚未檢查的 bit 會分別在 ret = v > 0; 及 ret += v > 1; 被檢查到

e.g : v = 01110010
v > 0 => ret = 1
0111 | 0010 => 0111 、 ret = 1 + 4
01 | 11 => 01 、 ret = 1 + 4 + 2
01 <= 1 => ret = 1 + 4 + 2 = 7

測驗八

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; // EXP14
        q->data = (*r)->data;
        q = *r;
        *r = q->right;
    }
    delete q;
}

題目為二元搜尋樹 , 可知樹的 left child 比 parent 小 , 而樹的 right child 比 parent 大
EXP12 及 EXP13 為二元搜尋樹尋找 data 的過程 , 根據 if 條件可知是要往左還往右 , 而 p 為 pointer to pointer 所以應該 assign 成 pointer 的地址 e.g:&(*p)->left

測驗九

考慮以下進行記憶體地址對齊 (alignment) 的巨集:

/* 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 - 1) & ~(MAX_ALIGNMENT - 1))

由題目及程式碼可以推測，此巨集的功能為將給定的記憶體以 16 個 bit向上對齊
(((x) + MAX_ALIGNMENT - 1) 確保新的記憶體位置大於等於原本的記憶體位置，達成向上對齊
& ~(MAX_ALIGNMENT - 1) 將低位的 4 個 bit 清為 0 ，確保記憶體位置為 16 的倍數

撰寫出對應 ROUND_DOWN 巨集:

/* 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_DOWN_TO_ALIGNMENT_SIZE(x) \
    (x & ~(MAX_ALIGNMENT - 1))

只要將 x 低位的 4 個 bit 清為 0 就能確保記憶體位置為 16 的倍數，且新的記憶體位置也小於等於原記憶體位置，達成向下對齊

測驗十

#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));                 \
    })

DIVIDE_ROUND_CLOSEST 巨集會得到 x 除以 divisor 四捨五入後的結果
加上 (__d >> 1) 相當於讓 (__x)/(__d) 四捨五入，當 (__x) >= 0.5*(__d) 則 (__d)-(__x)%(__d) <= (__d >> 1) => 進位，又整數除法會無條件捨去小數
(((__x) > 0) == ((__d) > 0))) 判斷結果為正或負，負數捨去小數點相當於取大的數，因此要改成減 ((__d) >> 1)
(((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 判斷 x 或 divisor 是否為無號數，若有無號數，因另一數也會被轉型成無號數，所以結果必為正數

測驗十一

static inline unsigned long fls(unsigned long word)
{
    int num = 64 - 1;
        
    if (!(word & (~0ul << 32))) {
        num -= 32;
        word <<= 32;
    }
    if (!(word & (~0ul << (64 - 16)))) {
        num -= 16;
        word <<= 16;
    }
    if (!(word & (~0ul << (64 - 8)))) {
        num -= 8;
        word <<= 8;
    }
    if (!(word & (~0ul << (64 - 4)))) {
        num -= 4;
        word <<= 4;
    }   
    if (!(word & (~0ul << (64 - 2)))) {
        num -= 2;
        word <<= 2;
    }   
    if (!(word & (~0ul << (64 - 1))))
        num -= 1;
    return num;
} 

unsigned long i_sqrt(unsigned long x)
{
    unsigned long b, m, y = 0;
    if (x <= 1)
        return x;
    m = 1UL << (fls(x) & ~1UL);
    while (m) {
        b = y + m;
        y >>= 1; //xxx

        if (x >= b) {
            x -= b; //yyy
            y += m;
        }
        m >>= 2; //zzz
    }
    return y;
}

參考 kdnvt 的筆記，將 x 拆為以下形式:
- $x = (000 b_{0} b_{1} b_{2} \dots b_{n - 1} b_{n})^{2}$
- $000 b_{0} b_{1} b_{2} \dots b_{n - 1} b_{n}$ 為 bits pattern ，
  $b_{0}$ 為最高位的 1 ，
  $b_{1}$ ~
  $b_{n}$ 為 0 或 1 ，
  $(000 b_{0} b_{1} b_{2} \dots b_{n - 1} b_{n})$ 即所求的平方根 y
fls : 找出某數最高位的 bit 1 ，最低為 0 最高為 63
m = 1UL << (fls(x) & ~1UL) : 題目平方根為向下取整，又 y 的平方最小一定為奇數個 bits ，因此當 x 最高位的 1 在偶數 bit 時( fls(x) 為奇數) ，要將 fls(x) 減一( fls(x) & ~1UL) ，確保 y 平方小於等於 x
while 迴圈為求得 y =
$(b_{0} b_{1} b_{2} \dots b_{n - 1} b_{n})$ 的過程，從
$b_{0}$ 找到
$b_{n}$ ，其中 m 為
$b_{i}^{2}$ ， y 為
$2 * b_{i} * (b_{i - 1} + \dots + b_{0})$ (假設目前已找出
$(b_{0} \dots b_{i - 1} x x x)$ , x為尚未找出的bit) ，而 b = y + m 則為
$b_{i}$ 為 1 時當前
$y_{i}^{2}$
$(b_{0} \dots b_{i - 1} 1000)$ 會多出上一個
$y_{i - 1}^{2}$
$(b_{0} \dots b_{i - 1} 0000)$ 的值，當這個值大於 x 表示該 bit 應為 0 ，反之將 x 減去 b , y 加上 m
m 為
$b_{i}^{2}$ ，要找下一個 bit
$b_{i + 1}^{2}$ 會右移兩位， y 為
$2 * b_{i} * (b_{i - 1} + \dots + b_{0})$ 要找下一個 bit
$2 * b_{i + 1} * (b_{i} + \dots + b_{0})$ 會右移一位
*註 :
$b_{i}$ >> 1 =
$b_{i + 1}$

題目連結

2022q1 Homework3 (quiz3)

測驗一

測驗二

測驗三

測驗四

測驗五

測驗六

測驗七

測驗八

測驗九

測驗十

測驗十一

Read more

2023q1 Homework7 (ktcp)

2023q1 Homework5 (quiz5)

2023q1 Homework4 (quiz4)

2023q1 Homework3 (quiz3)