Try   HackMD

2022q1 Homework3 (quiz3)

測驗題目

測驗 1

程式碼運作原理

功能

產生連續的 bitmask

  • GENMASK(6, 4) 產生 011100002
  • GENMASK(39, 21) 產生 0x000000ffffe00000 (64 位元)

GENMASK 巨集定義

首先,我們可以看到巨集內有兩個 ~0UL (0xFFFFFFFFFFFFFFFF) 先做 shift 操作,接著做 AND
因此,可以推測其作法是將

  • ~0UL 右移產生高位 63 - h bits 為 0 的 unsigned long
  • ~0UL 左移產生低位 l bits 為 0 的 unsigned long

所以 LEFT = 63 -h 用以產生高位 63 - h bits 個 0 ,而 RIGHT = l 用以產生低位 l bits 個 0

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

測驗 2

程式碼運作原理

功能

fd結構體的第一個成員的地址對 4 個位元組進行向下對齊。







G



address

Memory address

0x0

0x1

0x2

0x3

0x4

0x5

0x6

0x7



space_before

Memory space before

 

data

data

data

data

 

 

 




space_after

Memory space after

data

data

data

data

 

 

 

 




space_before->space_after





圖片參考 jim12312321

記憶體向下對齊實作

首先,從結構體 fd 包含 struct foo *foo 以及 unsigned int flags
接著可以根據 fd 推測 EXP1 應該包含 struct foo *

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

因為要作 4 bytes 的的向對齊,低位 2 bits clear,所以用 bitmask 的方式讓 v~3 作 AND。
因此 EXP1 = (struct foo *)(v & ~3)

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

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

測驗 3

Leetcode 190. Reverse Bits

程式碼運作原理

功能

輸入的 8 位元無號整數逐一位元反轉。

  • Input = 00100101
  • Output = 11011010

實作

利用 AND 與 Shift 達到高位移到低位;低位移到高位,接著將兩者用 OR 合併。

  1. 將高位 4 bits 與低位 4 bits 交換
  2. 將高、低位 4 bits 內的高位 2 bits 與低位 2 bits 交換
  3. 將高、低位 2 bits 內的高位 1 bits 與低位 1 bits 交換

EXP2EXP3 為負責處理低位 4 bits 的部份,所以

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

測驗 4

程式碼運作原理

foreach 巨集

遍歷集合中每個成員。

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

預期輸出:

i is 0
i is -1
i is 100
i is 0
i is -99
p is Hello
p is world

foreach 與 for 不相同的地方是 foreach 通常不維護明確的計數器

擴充 foreach 巨集定義

foreach 的巨集定義為 for 迴圈的實做,因此 EXP4, EXP5 的部份應該是更新 _foreach_i (index)。
由於每次迴圈都要對 i 賦值,因此要先更新 foreach_i 接著再對 i 賦值,所以:

  • EXP4 = ++_foreach_i
  • EXP5 = ++_foreach_i
#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})[EXP4])

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

測驗 5

LeetCode 29. Divide Two Integers

程式碼運作原理

規則

輸入兩正整數,將兩數相除,並將成果無條件捨去。

沒有除法的實做

先處理兩數處法的 sign bit, 用 signal 紀錄 sign bit,若 dividend < 0 則對 dvd 作二的補數,接著若 divisor < 0 則對 dvs 作二的補數。sign bit 用 signal *= -1 來處理,若只有一者為負,則 signal = -1,若兩者皆為負或皆不為負,則 signal = 0

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

shift 負責將 dvs 的最高位元對齊 dvd 的最高位元。
所以 EXP6 = dvs << shift

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

res 負紀錄商,而 EXP7 = dvd -= dvs << shift 將被除數減去除數。

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

先判斷 res 是否 overflow,最後將 res 乘上 signal 即為兩數相除的商。

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

測驗 6

LeetCode 149. Max Points on a Line

程式碼運作原理

規則

測驗 7

程式碼運作原理

功能

針對給定的 32 位元無號數,計算扣除開頭的 0,最少需要多少位元才可儲存

實作

利用 Binary Search 的方式,判斷最高位的 1 的位子。
比教最高位的 1 是否在前半部,若在前半部,將後半部 shift 掉。
可知 EXP10 = (v > 3) << 1
EXP11 只有一行,負責處理最後兩個 bits。
所以 EXP11 = ret += v > 1

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 = EXP10;
    v >>= m;
    ret |= m;
    EXP11;
    return ret;
}

測驗 8

程式碼運作原理

用 indirect pointer 改寫 remove_data

在第一個 while loop 的地方,他是負責 binary search 部份,因此 EXP12EXP13 應該是根據判斷 d(*p)->data 的大小進行向下搜尋。
因此:

  • EXP12 = p = &(*p)->left
  • EXP13 = p = &(*p)->right
void remove_data(tree &t, int d)
{
    tnode **p = &t;
    while (*p != 0 && (*p)->data != d) {
        if (d < (*p)->data)
            EXP12;
        else
            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 = EXP14;
        q->data = (*r)->data;
        q = *r;
        *r = q->right;
    }
    delete q;
}

測驗 9

程式碼運作原理

記憶體地址對齊 (alignment) 的巨集

先對地址加上對齊大小(16),因此 MMM = 16
接著捨去最低 4 位元,因此應該要與最低 4 位元皆為 0 其餘皆為 1 的數進行 AND 運算,所以 NNNMAX_ALIGNMENT - 1

/* 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 - MMM) & ~(NNN))

測驗 10

程式碼運作原理

功能

處理二個表示式進行整數除法操作時,最接近的整數值。
參考執行成果:

  • DIVIDE_ROUND_CLOSEST(7, 3) = 2
  • DIVIDE_ROUND_CLOSEST(6, 3) = 2
  • DIVIDE_ROUND_CLOSEST(5, 3) = 2

巨集實作

round(a/b)=(a+b/2)/b

分為兩種情況:

  1. xdivisor 為 unsigned 或同號
    • RRR = (__x)+(__d)>>1
  2. xdivisor 為異號
    • SSS = -(__x)+(__d)>>1
#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)))                         \
            ? ((RRR) / (__d))                  \
            : ((SSS) / (__d));                 \
    })

測驗 11

程式碼運作原理

不用除法的開平方根實作

返回 word 的最高有效位元的位置。

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;
} 
    m = 1UL << (fls(x) & ~1UL);
    while (m) {
        b = y + m;
        XXX;

        if (x >= b) {
            YYY;
            y += m;
        }
        ZZZ;
    }