2022q1 Homework4 (quiz4)

contributed by < StevenChou499 >

• 作業需求
• 測驗題目

---

測驗 1

延伸第 3 週測驗題的測驗 7 ，已知輸入必為大於 0 的數值 (即 x > 0 )，以下程式碼可計算

$[{\log }_2(x)]$，，也就是 ceil 和 log2 的組合並轉型為整數:

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

請補完，使其行為符合預期。作答規範:

• EXP1 應以最簡潔的形式撰寫，且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)
• EXP1 為表示式，限制使用 ^ , & , | , << , >> 這幾個運算子，可能會出現常數
• EXP1 不該包含小括號 (即 ( 和 ) )
• 為了自動批改的便利，變數出現的順序 (可從缺) 從左到右為 r , shift , x
• EXP1 不可包含 , 和 ; 這樣的分隔符號 (separator)

思考與想法

本題與測驗3的第 7 題其實非常相似，前面之時做方法其實都是相同的，只是因為這次需要搭配計算的是 ceil 的方式， 因此一開始需要先將數字 x 減 1 ，最後在計算完之後再加上 1 ，以避免在計算以 2 為底的對數時少算。而因為 EXP1 只需要計算最後一位，不需要經過計算相加並儲存，其值為 r | shift | x >> 1 。

EXP1 : r | shift | x >> 1

---

測驗 2

複習〈你所不知道的 C 語言: bitwise 操作〉，改寫第 3 週測驗題的測驗 11 裡頭的 fls 函式 (fls 意謂 "find last set")，使其得以計算 Find first set:

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

請補完，使其行為符合預期。作答規範:
EXP2 和 EXP3 應以最簡潔的形式撰寫，且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)
EXP2 和 EXP3 限制使用 ^, &, |, <<=, >>=, +=, -= 這幾個運算子，可能會出現常數
EXP2 和 EXP3 不該包含小括號 (即 ( 和 ) )
為了自動批改的便利，變數出現的順序 (可從缺) 從左到右為 x , o , t , shift ，也就是說，你應該寫 x ^ t 而非 t ^ x
EXP2 和 EXP3 不可包含 , 和 ; 這樣的分隔符號 (separator)

思考與想法

---

測驗 3

考慮以下改寫自 Linux 核心的程式碼:

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

請補完，使 consumer_del 行為符合註解規範。作答規範:

1. EXP4 和 EXP5 應以最簡潔的形式撰寫，且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)
   2.EXP4 和 EXP5 都包含指標操作 (如 ->)

思考與想法

題目使用了 pointer to a pointer 的方式循序訪問各個 foo_consumer ，並比較之後若相同則刪除該 foo_consumer ，回傳 true 。因此 EXP4 之值應該為讓 for 迴圈跳往下個 foo_consumer 的 con = &(*con)->next ，而 EXP5 之值應該為 con = &(*con)->next ，才可以跳過想要刪除的點而直接連接至下一個 foo_consumer 。

EXP4 : con = &(*con)->next
EXP5 : con = &(*con)->next

測驗 4