2022q1 Homework2 (quiz2)

contributed by < jj97181818 >

測驗 1

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (EXP1);
}

	(a >> 1) + (b >> 1) + (a & b & 1)
a = 2, b = 2	1 + 1 + 0
a = 2, b = 3	1 + 1 + 0
a = 3, b = 2	1 + 1 + 0
a = 3, b = 3	1 + 1 + 1

在 a 和 b 右移 1 位之後，最低位元可能會出現需要進位的狀況，因此要將最低位元考慮進來，也就是加上第三項 EXP1 = a & b & 1。

uint32_t average(uint32_t a, uint32_t b)
{
    return (EXP2) + ((EXP3) >> 1);
}

在 你所不知道的 C 語言：數值系統篇 有提到用加法器來思考：x + y = x ^ y + (x & y) << 1
其中，x ^ y 可求得位元相加不進位的總和，x & y 則求得進位，並將進位的值左移一位，與總和相加。

 (x + y) / 2
= (x ^ y + (x & y) << 1) >> 1
= ((x ^ y) >> 1) + (x & y)

現在要求 (x + y) / 2 就是將 x ^ y + (x & y) << 1 整個右移一位，求得 ((x ^ y) >> 1) + (x & y)，因此，EXP2 = a & b, EXP3 = a ^ b。

比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出

比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 (可研讀 CS:APP 第 3 章)

研讀 Linux 核心原始程式碼 include/linux/average.h

研讀 Linux 核心原始程式碼 include/linux/average.h，探討其 Exponentially weighted moving average (EWMA) 實作，以及在 Linux 核心的應用

測驗 2

先看 解讀計算機編碼 提供 min 的程式碼：

int32_t min(int32_t a, int32_t b) {
    int32_t diff = (a - b);
    return b + (diff & (diff >> 31));
}

• a > b：會因為 diff 是正的，diff >> 31 為 0，(diff & (diff >> 31)) 就會是 0，直接回穿 b。
• a < b：會因為 diff 是負的，diff >> 31 32 個 bit 都是 1，因此 (diff & (diff >> 31)) 就會是 diff 本身，所以 b + diff = b + (a - b) = a，最後回傳 a。

這題 max 的程式碼：

#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((EXP4) & -(EXP5));
}

限制：

• EXP4 為 a 和 b 進行某種特別 bitwise 操作，限定用 OR, AND, XOR 這三個運算子。
• EXP5 為 a 和 b 的比較操作，亦即 logical operator，限定用 >, <, ==, >=, <=, != 這 6 個運算子。

1. 這個程式最後要回傳 a 或是 b，看誰比較大。而 a ^ 0 會是 a 自己，而 a ^ (b - a) 會是 b（會寫 b - a 是參考 min 程式碼中 diff 的想法），所以 ((EXP4) & -(EXP5)) 會是 0 或是 (b - a)。
2. 因為 EXP5 是做比較運算，會回傳 0 或 1，在 EXP5 為 0 的情況下，不論 EXP4 是什麼，((EXP4) & -(EXP5)) 都會是 0，也就是最後會回傳 a，是 a 比較大的情況。
3. 因此 EXP5 為 1 就會是 b 比較大的情況，EXP5 即為 a < b，-(EXP5) 為 -1，每個 bit 皆為 1，任何值與 -1 做 AND 運算都還會是自己，也就是 ((EXP4) & -(EXP5)) 的值會被 EXP4 決定。
4. 會希望 EXP4 會是 b - a，但是限定使用 OR, AND, XOR。當 EXP4 為 a ^ b 時，回傳的值會是 a ^ (a ^ b)，a 和 a 自己做 XOR 會是 0，0 再和 b 做 XOR 就會是 b 本身了。

因此 EXP4 = a ^ b, EXP5 = a < b

針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作

針對有號整數的實作和無號整數的實作一樣，因為這裡做的 XOR 的結果對於有號與無號沒有差別，後面 a < b 的部分就是按照兩者的大小比較，是 0 或 1，對有號無號也沒有影響。

#include <stdint.h>
int32_t max(int32_t a, int32_t b)
{
    return a ^ ((a ^ b) & -(a < b));
}

Linux 核心也有若干 branchless / branch-free 的實作

請在 Linux 核心原始程式碼中，找出更多類似的實作手法，請善用 git log 檢索。

在 drivers/gpu/drm/radeon/r600_blit.c 的第 492 行有 branchless 的實作：

int2float 是將 int 轉成 float，這裡避免 branch 的方法是先用 __fls 找出 MSB 的位置，然後用旋轉指令將 unsigned int 擴展成浮點數。

/* 23 bits of float fractional data */
#define I2F_FRAC_BITS  23
#define I2F_MASK ((1 << I2F_FRAC_BITS) - 1)

/*
 * Converts unsigned integer into 32-bit IEEE floating point representation.
 * Will be exact from 0 to 2^24.  Above that, we round towards zero
 * as the fractional bits will not fit in a float.  (It would be better to
 * round towards even as the fpu does, but that is slower.)
 */
uint32_t int2float(uint32_t x)
{
	uint32_t msb, exponent, fraction;

	/* Zero is special */
	if (!x) return 0;

	/* Get location of the most significant bit */
	msb = __fls(x);

	/*
	 * Use a rotate instead of a shift because that works both leftwards
	 * and rightwards due to the mod(32) behaviour.  This means we don't
	 * need to check to see if we are above 2^24 or not.
	 */
	fraction = ror32(x, (msb - I2F_FRAC_BITS) & 0x1f) & I2F_MASK;
	exponent = (127 + msb) << I2F_FRAC_BITS;

	return fraction + exponent;
}

也一併附上原本有 branch 的程式碼：

uint32_t int2float(uint32_t input)
{
	u32 result, i, exponent, fraction;

	if ((input & 0x3fff) == 0)
		result = 0; /* 0 is a special case */
	else {
		exponent = 140; /* exponent biased by 127; */
		fraction = (input & 0x3fff) << 10; /* cheat and only
						      handle numbers below 2^^15 */
		for (i = 0; i < 14; i++) {
			if (fraction & 0x800000)
				break;
			else {
				fraction = fraction << 1; /* keep
							     shifting left until top bit = 1 */
				exponent = exponent - 1;
			}
		}
		result = exponent << 23 | (fraction & 0x7fffff); /* mask
								    off top bit; assumed 1 */
	}
	return result;
}

測驗 3

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int shift;
    for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }
    while (!(u & 1))
        u /= 2;
    do {
        while (!(v & 1))
            v /= 2;
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (COND);
    return RET;
}

1. 在做 do while 的輾轉相除法之前，如果 u 和 v 皆為 2 的倍數，就將 u, v 都除以 2，直到至少其中一個不為 2 的倍數，shift 紀錄著除以 2 的次數（右移的次數）。
2. 輾轉相除法只關心每次除法的餘數是否為 0，為 0 時即得到最大公因數。這裡我們用相減的方式，當 t = u - v 的差為零時，表示得到最大公因數，又 v = t，因此COND = v。
3. 最後回傳的最大公因數為 u，但因為在做輾轉相除法之前有先將 u 除以 2（右移），因此要乘 2 shift 次（左移）。

因此 COND = v, RET = u << shift

在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升

將原本判斷是偶數時，用迴圈不停地除以 2 的程式，都改成用 __builtin_ctz 算出從 LSB 到最低位元 1 之前的 0 的數量，然後透過右移來達到除以 2 的效果。

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int shift = min(__builtin_ctz(u), __builtin_ctz(v));
    u >>= shift;
    v >>= shift;
    
    u >>= __builtin_ctz(u);
    do {
        v >>= __builtin_ctz(v);
        
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (v);
    return u << shift;
}

解釋其實作手法和探討在核心內的應用場景

Linux 核心中也內建 GCD (而且還不只一種實作)，例如 lib/math/gcd.c，請解釋其實作手法和探討在核心內的應用場景。

在 lib/math/gcd.c 中有實作兩種 GCD，如果能使用 __ffs（find first bit in word），就用第一種 GCD 實作，反之用第二種。__ffs.h 會針對不同架構做不同的實作，通用版本的 __ffs.h 在 linux/include/asm-generic/bitops/__ffs.h 中：

在使用 __ffs.h 的 GCD 實作中，和以 __builtin_ctz 改寫 GCD 程式中的 __builtin_ctz 很像，只是換成使用 __ffs（這裡的 __ffs 是從 0 開始從 LSB 算到最低位元 1，__builtin_ctz 是從 1 開始算到最低位元 1 的前一個，剛好結果會是一樣的）。

r & -r 和測驗 4 的答案 EXP6 = bitwise & -bitwise 是同樣意思，會留下最低位元的 1，其餘位元為 0。

#if !defined(CONFIG_CPU_NO_EFFICIENT_FFS)

/* If __ffs is available, the even/odd algorithm benchmarks slower. */

/**
 * gcd - calculate and return the greatest common divisor of 2 unsigned longs
 * @a: first value
 * @b: second value
 */
unsigned long gcd(unsigned long a, unsigned long b)
{
	unsigned long r = a | b;

	if (!a || !b)
		return r;

	b >>= __ffs(b);
	if (b == 1)
		return r & -r;

	for (;;) {
		a >>= __ffs(a);
		if (a == 1)
			return r & -r;
		if (a == b)
			return a << __ffs(r);

		if (a < b)
			swap(a, b);
		a -= b;
	}
}

#else

/* If normalization is done by loops, the even/odd algorithm is a win. */
unsigned long gcd(unsigned long a, unsigned long b)
{
	unsigned long r = a | b;

	if (!a || !b)
		return r;

	/* Isolate lsbit of r */
	r &= -r;

	while (!(b & r))
		b >>= 1;
	if (b == r)
		return r;

	for (;;) {
		while (!(a & r))
			a >>= 1;
		if (a == r)
			return r;
		if (a == b)
			return a;

		if (a < b)
			swap(a, b);
		a -= b;
		a >>= 1;
		if (a & r)
			a += b;
		a >>= 1;
	}
}

#endif

測驗 4

#include <stddef.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
    size_t pos = 0;
    for (size_t k = 0; k < bitmapsize; ++k) {
        uint64_t bitset = bitmap[k];
        size_t p = k * 64;
        for (int i = 0; i < 64; i++) {
            if ((bitset >> i) & 0x1)
                out[pos++] = p + i;
        }
    }
    return pos;
}

這個程式是將 bitmap 陣列裡面所有 uint64_t 型別的整數中，bit 為 1 的位置都記錄到 out 裡面。

#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
    size_t pos = 0;
    uint64_t bitset;
    for (size_t k = 0; k < bitmapsize; ++k) {
        bitset = bitmap[k];
        while (bitset != 0) {
            uint64_t t = EXP6;
            int r = __builtin_ctzll(bitset);
            out[pos++] = k * 64 + r;
            bitset ^= t;                           
        }
    }
    return pos;
}

限制：

• 考慮到 -bitwise 的特性

1. 如果 bitwise = 01101100，那 -bitwise = 10010100，可以發現 bitwise 和 -bitwise 最低位元的 1 往右的位元都一樣。
2. 在 bitset 不是 0 的時候就繼續在迴圈裡面找最低位元的 1，因此在第 12 行的 bitset ^= t; 應該要將 bitwise 該次找到最低位元的 1 改成 0，這裡的 t 要只有最低位元的 1，其餘位元都是 0，才能讓 bitset 和 t 做 XOR 之讓最低位元的 1 改為 0。
3. t = bitwise & -bitwise 可以讓 t 只留下最低位元的 1。

因此 EXP6 = bitwise & -bitwise

舉出這樣的程式碼用在哪些真實案例中

因為只儲存 1 的位置，所以可以用在壓縮儲存大小的場景，例如：壓縮圖片。

檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進

設計實驗，檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 bitmap density;

思考進一步的改進空間

舉出 Linux 核心使用 bitmap 的案例

閱讀 Data Structures in the Linux Kernel 並舉出 Linux 核心使用 bitmap 的案例

測驗 5

#include <stdbool.h>                       
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
    
struct rem_node {
    int key;
    int index;
    struct list_head link;
};  
    
static int find(struct list_head *heads, int size, int key)
{
    struct rem_node *node;
    int hash = key % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (key == node->key)
            return node->index;
    }
    return -1;
}

char *fractionToDecimal(int numerator, int denominator)
{
    int size = 1024;
    char *result = malloc(size);
    char *p = result;

    if (denominator == 0) {
        result[0] = '\0';
        return result;
    }

    if (numerator == 0) {
        result[0] = '0';
        result[1] = '\0';
        return result;
    }

    /* using long long type make sure there has no integer overflow */
    long long n = numerator;
    long long d = denominator;

    /* deal with negtive cases */
    if (n < 0)
        n = -n;
    if (d < 0)
        d = -d;

    bool sign = (float) numerator / denominator >= 0;
    if (!sign)
        *p++ = '-';

    long long remainder = n % d;
    long long division = n / d;

    sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
    if (remainder == 0)
        return result;

    p = result + strlen(result);
    *p++ = '.';

    /* Using a map to record all of reminders and their position.
     * if the reminder appeared before, which means the repeated loop begin,
     */
    char *decimal = malloc(size);
    memset(decimal, 0, size);
    char *q = decimal;

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

    for (int i = 0; remainder; i++) {
        int pos = find(heads, size, remainder);
        if (pos >= 0) {
            while (PPP > 0)
                *p++ = *decimal++;
            *p++ = '(';
            while (*decimal != '\0')
                *p++ = *decimal++;
            *p++ = ')';
            *p = '\0';
            return result;
        }
        struct rem_node *node = malloc(sizeof(*node));
        node->key = remainder;
        node->index = i;

        MMM(&node->link, EEE);

        *q++ = (remainder * 10) / d + '0';
        remainder = (remainder * 10) % d;
    }

    strcpy(p, decimal);
    return result;
}

• 13~23 行：hash = key % size; 用 remainder % size 的方式決定要把節點塞在哪一個 heads 的 linked list。在這個 function 裡面，我們嘗試在特定 linked list 找尋是否有相同的餘數（key）的節點，如果有就回傳 index（value），如果找不到就回傳 -1。
• 72~75 行：先替 heads 配置記憶體，產生有 1333 個 bucket 的 hashtable，可以用 index 去指定特定 bucket。並將每個 bucket 的頭都先指向自己，因為還沒有任何值放進來。
• 77~93 行：當還有餘數 remainder 的時候，就在這個迴圈裡處理小數點後面的數字。先去 hash table 找特定 linked list 有沒有一樣的餘數。
  • 79~88 行：如果有一樣的餘數，pos >= 0，處理循環小數的部分。
  • 89~96 行：如果沒有，pos 為 -1，並配置一個節點加到 linked list 上面，其中 key 為餘數，index 為小數點後第幾位（從第 0 位開始算）。要將節點加在 hashtable 上的某個 bucket，用 find 函式尋找特定餘數的方式一樣，用 ramainder % size 來決定要在哪個 heads 的 linked list 找餘數。
    (remainder * 10) / d
  • 95~96 行： (remainder * 10) / d 是算出這位的小數數字，+ '0' 讓前面數字轉成字元，然後加到 dicimal 裡。(remainder * 10) % d 會算出下一輪的餘數。

因此 PPP = pos--, MMM = list_add, EEE = &heads[remainder % size]

指出其中不足，並予以改進

改進一：

第 58 行，不需要特別做 division > 0 的條件判斷：

sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);

因為在第 45 行已經處理過為負數的 n 和 d 了：

/* deal with negtive cases */
    if (n < 0)
        n = -n;
    if (d < 0)
        d = -d;

所以可以改成：

sprintf(p, "%ld", (long) division);

改進二：

第 51 行的判斷正負號：

bool sign = (float) numerator / denominator >= 0;

可以改成：

bool sign = numerator < 0 ^ denominator < 0;

找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例

在 Linux 核心原始程式碼的 mm/ 目錄 (即記憶體管理) 中，找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例，予以探討和解說其應用場景

測驗 6

/*
 * ALIGNOF - get the alignment of a type
 * @t: the type to test
 *
 * This returns a safe alignment for the given type.
 */
#define ALIGNOF(t) \
    ((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X)

1. 解釋 ALIGNOF(t)

• (struct { char c; t _h; } *)0 表示將 0 轉型成指向 struct { char c; t _h; } 的 pointer，他的特殊意義為空指標，但不能確定空指標指向的位置。
• (&((struct { char c; t _h; } *)0)->M) 是取得 struct 中某個成員 M 的位址
• (char *)(&((struct { char c; t _h; } *)0)->M) 是將 struct 中某成員 M 的位址轉型成 char*
• ((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X) 就是將 struct 中某成員 M 的位址減去 X

2. offsetof 是找某個 struct st 中的成員 m 與 struct 起始位置間的距離（指定成員和起始位置的偏移量）。比較好的寫法是第二種，用位址減去另外一個位址，得到位址的偏移量，第一種是直接得到 m 的位址，但是不能保證空指標的值為多少。

#define offsetof(st, m) ((size_t)&(((st *)0)->m))

#define offsetof(st, m) ((size_t)((char *)&((st *)0)->m - (char *)0))

3. ALIGNOF 可以用 offsetof 來實作，這題 ALIGNOF 實作的前半 (char *)(&((struct { char c; t _h; } *)0)->M) 和 offsetof 一樣作用，後半減掉一個 X，X = 0。
   ALIGNOF 改用 offsetof 實作：

#define ALIGNOF(t) offset(struct { char c; t _h; }, M)

4. 有發現 struct 的第一個成員放 char 可能是因為它做 alignment 的大小是最小的（1 byte），如果後面 t 型別變數 _h 需要比較大的 alignment 的話，那 char c 也需要 padding 到跟 _h 一樣的 alignment size，所以才會去算 char c 的大小（指定成員 _h 和 struct 起始位置的偏移量），所以這裡的 M 為 _h，即可得到 t 型別 _h alignment 的大小。

因此 M = _h, X =0

在 Linux 核心原始程式碼中找出 __alignof__ 的使用案例 2 則

針對其場景進行解說

第一則：

在 linux/include/linux/kstrtox.h 的第 30 行：

static inline int __must_check kstrtoul(const char *s, unsigned int base, unsigned long *res)
{
	/*
	 * We want to shortcut function call, but
	 * __builtin_types_compatible_p(unsigned long, unsigned long long) = 0.
	 */
	if (sizeof(unsigned long) == sizeof(unsigned long long) &&
	    __alignof__(unsigned long) == __alignof__(unsigned long long))
		return kstrtoull(s, base, (unsigned long long *)res);
	else
		return _kstrtoul(s, base, res);
}

kstrtoul 是將一個字串轉成 unsigned long，實作有用到 __alignof__ 來判斷 unsigned long 和 unsigned long long 的 alignment 大小是否一樣。可能是要確保在該 data model 下 unsigned long 和 unsigned long long 的大小是一樣的，例如在 LP64 下，就都是 64 bit。

第二則：

在 linux/crypto/aegis.h 的第 18 行：

union aegis_block {
	__le64 words64[AEGIS_BLOCK_SIZE / sizeof(__le64)];
	__le32 words32[AEGIS_BLOCK_SIZE / sizeof(__le32)];
	u8 bytes[AEGIS_BLOCK_SIZE];
};

struct aegis_state;

extern int aegis128_have_aes_insn;

#define AEGIS_BLOCK_ALIGN (__alignof__(union aegis_block))

有一個巨集 AEGIS_BLOCK_ALIGN 會取得 union aegis_block 的 alignment 大小。

在 Linux 核心原始程式碼找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集

探討其實作機制和用途，並舉例探討 (可和上述第二點的案例重複)

• 在 linux/tools/testing/selftests/vm/pkey-helpers.h 的第 180 行有 ALIGN_DOWN 和 ALIGN_UP 的巨集：

#define ALIGN_UP(x, align_to)	(((x) + ((align_to)-1)) & ~((align_to)-1))
#define ALIGN_DOWN(x, align_to) ((x) & ~((align_to)-1))

• 在 linux/tools/testing/selftests/vm/hmm-tests.c 的第 54 行有 ALIGN 的巨集：

#define ALIGN(x, a) (((x) + (a - 1)) & (~((a) - 1)))

ALIGN_UP

ALIGN_UP 的參數 x 是原本的大小，align_to 是要用多少 bit 為倍數來對齊。

左段的程式 ((x) + ((align_to) - 1)) 是將 x 加上 align_to 的大小再減去 1，讓原本大小不足 align_to 的部分，能向上進 1 位到 align_to，例如：x = 5, align_to = 32，為了讓 5 能夠對齊變成 32 位元，就讓 5 + (32 - 1) = 36，讓值超過 32。

右段的程式 ~((align_to)-1)) 是要去除不足 align_to 的餘數，因為最後算出來的值應該是 align_to 的倍數。延續上面的例子來解釋，就是 ~(32 - 1) 用二進位來表達 1110 0000，再與 36 做 AND 運算，會將不足 32 的部分都 clear 掉，就從 5 向上對齊成 32 了。

ALIGN_DOWN

向下對齊不需要加上(align_to) - 1 來補足不到 align_to 的餘數，而是直接捨棄不到 align_to 的部分。同樣用 ~((align_to)-1)) 去除不足 align_to 的餘數，最後算出來的值也是 align_to 的倍數。

ALIGN

在 linux 核心程式碼找到的 ALIGN 巨集看起來和向下對齊一樣。

測驗 7

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 << KK1) << KK2;

        char fmt[9];
        strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (KK3)], length);
        fmt[length] = '\0';

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

1. length 代表著要印出字串的長度，可被 3 整除要輸出 Fizz（4 個字元），可被 5 整除要輸出 Buzz（4 個字元），同時可被 3 和 5 整除要輸出 FizzBuzz（8 個字元），其餘的輸出數字本身（length 預設是 2 個字元）。
2. unsigned int length = (2 << KK1) << KK2; 會先將 2（0010）左移 KK1 位，再左移 KK2 位。當 KK1 為 div3，KK2 為 div5 時，就可以根據 div3 和 div5 為 1（可被整除）或 0（不可被整除），來調整 length，如下表。

	左移位數	length
只被 3 整除	一位	0100 = 4
只被 5 整除	一位	0100 = 4
被 3 和 5 整除	兩位	1000 = 8
其餘	零位	0010 = 2

3. strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (KK3)], length); 的 9 要改成 8，因為一個數在不能被 3 和 5 整除的時候，是要將 "%u" 複製到 fmt 裡面，而 % 的位置在第 8 位。
4. 當 div5 為 1 時（被 5 整除），8 右移一位為 4，從第四位開始複製 4 個字元長度，剛好是 Buzz。所以接下來要處理只被 3 整除和被 15 整除的情況，都需要從第 0 位開始複製，因為 div5 的關係，這時候的值可能是 8（1000）或 4（0100），要保證能變成 0 的話需要右移 4 位，因此 KK3 為 div3 << 2，就可以右移 4 位了。

因此 KK1 = div3, KK2 = div5, KK3 = div3 << 2

評估 naive.c 和 bitwise.c 效能落差

避免 stream I/O 帶來的影響，可將 printf 更換為 sprintf

改寫 bitwise.c 程式碼，試圖運用更少的指令來實作出 branchless

分析 Faster remainders when the divisor is a constant: beating compilers and libdivide 一文的想法 (可參照同一篇網誌下方的評論)，並設計另一種 bitmask，如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」，然後再改寫 bitwise.c 程式碼，試圖運用更少的指令來實作出 branchless;

• 參照 fastmod: A header file for fast 32-bit division remainders on 64-bit hardware

提出 throughput (吞吐量) 更高的 Fizzbuzz 實作

研讀 The Fastest FizzBuzz Implementation 及其 Hacker News 討論，提出 throughput (吞吐量) 更高的 Fizzbuzz 實作

解析 Linux 核心原始程式碼 kernel/time/timekeeping.c

解析 Linux 核心原始程式碼 kernel/time/timekeeping.c 裡頭涉及到除法運算的機制，探討其快速除法的實作 (注意: 你可能要對照研讀 kernel/time/ 目錄的標頭檔和程式碼)

• 過程中，你可能會發現可貢獻到 Linux 核心的空間，請充分討論