2022q1 Homework (quiz4)

contributed by < hankluo6 >

第 4 週測驗題

測驗 1

運作原理

int ceil_log2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;                                                                                                                                    
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (EXP1) + 1;       
}

要得到

$\lceil {\log }_{2}x\rceil$ 相當於取得最高位元 0 的位置與 LSB 間的數字數量，所以可以用 binary search 的方法從 16, 8, 4, 2 位元間隔尋找。

15 行後 x 只剩兩個位元，所以需要 (x >> 1) 進行最後一次搜尋，並加上缺少的一次 r |= shift，可得出 EXP1 = r | shift | (x >> 1)

---

測驗 2

運作原理

#define BITS_PER_BYTE 8
#define BITS_PER_LONG (sizeof(unsigned long) * BITS_PER_BYTE)

#include <stddef.h>

static inline size_t ffs(unsigned long x)
{
    if (x == 0)
        return 0;

    size_t o = 1;
    unsigned long t = ~0UL;
    size_t shift = BITS_PER_LONG;

    shift >>= 1;
    t >>= shift;

    while (shift) {
        if ((EXP2) == 0) {
            x >>= shift;
            EXP3;
        }

        shift >>= 1;
        t >>= shift;
    }

    return o;
}

與前一題一樣，從 32, 16, 8, 4, 2 位元去尋找，所以當在搜尋範圍內有位元為 1 時，需要右移 x 並將結果加到回傳值 o 上。所以 EXP2 = s & t；而回傳值 o 則需加上對應的位元數，故 EXP3 = o += shift。

---

測驗 3

運作原理

struct foo_consumer {
    int (*handler)(struct foo_consumer *self, void *);
    struct foo_consumer *next;
};

struct foo {
    struct foo_consumer *consumers;
    unsigned long flags;
};

#include <stdbool.h>

/*
 * For foo @foo, delete the consumer @fc.
 * Return true if the @fc is deleted sfccessfully
 * or return false.
 */
static bool consumer_del(struct foo *foo, struct foo_consumer *fc)
{
    struct foo_consumer **con;
    bool ret = false;

    for (con = &foo->consumers; *con; EXP4) {
        if (*con == fc) {
            *con = EXP5;
            ret = true;
            break;
        }
    }

    return ret;
}

從結構可以看出 foo_consumer 透過 next 相連，所以 for 迴圈應該為遍歷所有的 foo_consumer，而這邊使用 pointer to pointer 當作 iterator，所以 EXP4 = con = &(*con)->next。EXP5 需要將刪除的 foo_consumer 後方的 element 接上，可得出 EXP5 = fc->next。

---