2020q3 Homework4 (quiz4)

contributed by < chi-ming5566 >

測驗題

作業要求

• 重新回答第 4 周測驗題，連同附帶的「延伸問題」。
• 比照 課前測驗參考解答: Q1的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及進行相關實驗。

---

測驗一

int hammingDistance(int x, int y) {
    return __builtin_popcount(x OP y);
}

兩個位元比較後，相異為1，相同為0，此為XOR，所以
OP = ^。

---

測驗三

從 div3 與 div5 可知道要判斷的數是 3 還是 5 的倍數，若是，為 1，若否，則為 0。

再來看length的調整

#define MSG_LEN 8

static inline bool is_divisible(uint32_t n, uint64_t M) {
    return n * M <= M - 1;
}

static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1;

int main(int argc, char *argv[]) {
    for (size_t i = 1; i <= 100; i++) {
        uint8_t div3 = is_divisible(i, M3);
        uint8_t div5 = is_divisible(i, M5);
        unsigned int length = (2 << div3) << div5;

        char fmt[MSG_LEN + 1];
        strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);
        fmt[length] = '\0';

        printf(fmt, i);
        printf("\n");
    }
    return 0;
}

由此可知:

• 如果可以整除 3 和 5，length = 2 << 1 << 1 = 8
• 如果可以整除 3 或 5，length = 2 << 1 = 4
• 否則就是 2

而 KK1 KK2 KK3 則是在問對起點的調整，再來看 "FizzBuzz%u" 這個字串:

• 如果可以整除 “3” 或 “3 和 5”，則要從字串的位置 0 開始複製
• 如果只能整除 5，則要從字串 4 的地方開始複製
• 否則就從 8 的地方開始

由上面幾點可知， (MSG_LEN >> KK1) >> (KK2 << KK3) 經過計算後的結果 start 需如下表:

div3	div5	start
0	0	8
0	1	4
1	0	0
1	1	0

可從此表推測出最佳解為 (MSG_LEN >> div5) >> (div3 << 2)。

---

測驗四