Try   HackMD

2022q1 Homework2 (quiz2)

contributed by < Tcc0403 >

測驗連結

測驗一

考慮以下對二個無號整數取平均值的程式碼:

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

這個直覺的解法會有 overflow 的問題,若我們已知 a, b 數值的大小,可用下方程式避免 overflow:

#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
    return low + (high - low) / 2;
}

可改寫為以下兩種等價實作:

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

題目分析

第一種等價實作:

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

前兩項的操作為右移一位元,可以視作為 a, b 兩值除以 2

a+b2=a2+b2 看似沒有問題,但先進行右移操作,會忽略 a, b 兩值相加最低位元進位的情況,
因此我們需要補上第三項,判斷最低位元相加是否進位,若有進位則加 1

a[0] b[0] Carry
0 0 0
0 1 0
1 0 0
1 1 1

觀察真值表可以得到

Carry=a0b0

  • 使用位元遮罩取得最低位元
    a0=a0x0001, b0=b0x0001
  • 整理成以下等式:
    Carry=a0b0=(a0x0001)(b0x0001)=ab0x0001

轉成程式碼,第三項 EXP1 即為 a & b & 1

第二種等價實作:

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

回顧半加器 (Half adder) 實作方法

A B Carry Sum
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

由真值表可得

Carry=AB, Sum=AB

進行多位元加法時,除了計算兩數在該位元的加總值 (Sum) ,計算出的進位值 (Carry) 還得進位至高位元 (i.e. 第

i 位元所計算出的進位值必須加到第
i+1
位元)

轉成程式碼即為 a & b + (a ^ b) << 1,等價於 a + b
a & b + (a ^ b) << 1 兩項分別右移一位

(a & b) >> 1 + (a ^ b),即為兩數平均(a + b) / 2

EXP2 = a & b, EXP3 = a ^ b

延伸問題

  1. 解釋上述程式碼運作的原理
  2. 比較上述實作在編譯器最佳化開啟的狀況,對應的組合語言輸出,並嘗試解讀 (可研讀 CS:APP 第 3 章)
  3. 研讀 Linux 核心原始程式碼 include/linux/average.h,探討其 Exponentially weighted moving average (EWMA) 實作,以及在 Linux 核心的應用

    移動平均(Moving average),又稱滾動平均值、滑動平均,在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數,來分析資料點的計算方法。
    移動平均通常與時間序列資料一起使用,以消除短期波動,突出長期趨勢或周期。短期和長期之間的閾值取決於應用,移動平均的參數將相應地設置。例如,它通常用於對財務數據進行技術分析,如股票價格、收益率或交易量。它也用於經濟學中研究國內生產總值、就業或其他宏觀經濟時間序列。

延伸問題 : 研讀 include/linux/average.h

EWMA 實作

DECLARE_EWMA(name, _precision, _weight_rcp) 巨集依據引數宣告相應的結構體以及操作相關函式

  • 結構體中僅有一個 unsigned long 型態的成員 internal
  • 操作相關函式有 init, read, add
  • _precision 決定 internal 中要用多少位元當作小數部分,即計算平均的精度
  • _weight_rcp 決定計算新的平均值時,新數值與原本平均值的權重
    為了計算效率,必須為 2 的冪

觀察 add 函式中實際計算新平均數的程式碼段落

WRITE_ONCE(e->internal, internal ?			\
​   		(((internal << weight_rcp) - internal) +	\
​   			(val << precision)) >> weight_rcp :	\
​   		(val << precision));	
  • weight_rcp 為以 2 為底的 _weight_rcp 之對數
  • 如果是第一次執行 add ,此時 internal 為 0,便直接將新數值作為平均值依照前面訂定的精度格式寫入
  • 其餘情況則按照以下方式更新平均值
    new average=(_weight_rcp1)average+new value_weight_rcp

在實作方法中,由於權重必定為 2 的冪,便可以使用位移操作取代計算效率較低的除法操作,

測驗二

改寫〈解讀計算機編碼〉一文的「不需要分支的設計」一節提供的程式碼 min,我們得到以下實作 (max):

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

題目分析

觀察題目提及的 min 函式

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

該函式中先計算 diff = a - b,再透過 bitwise 操作觀察最高位元判斷正負:

  • 若最高位元是 1 ,表示 diff 為負,即 a < bdiff & (diff >> 31) 會得到 diffb + (diff & (diff >> 31) 所得到的結果即為 a

對有號負數數進行右移是 implementation-defined,在不同環境可能會有不同結果,上述假設對有號負數右移為算術位移 (Arithmetic shift)

摘錄自 C99 [6.5.7] Bitwise shift operators :

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type
or if E1 has a signed type and a nonnegative value, the value of the result is the integral
part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the
resulting value is implementation-defined.

  • 若最高位元是 0 ,表示 diff 為正, 即 a > bdiff & (diff >> 31) 會得到 0 , b + (diff & (diff >> 31) 所得到的結果即為 b

上述函式在判斷最高位元時,順便將此判斷式作為位元遮罩得到相應的修正量,以達成 branchless

分析原題目 max 函式

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

可以將 a 視作原本給定的值, EXP4 視作相應的修正量, EXP5 為判斷式兼位元遮罩:

  • 若 a 較大,則後面不需要修正量,此時作為判斷式兼位元遮罩的 EXP5 需要等於 0 , 即 a < b
  • 若 a 較小,使 a < b 為 1,由於二補數編碼的關係,前面加上負號可將其變為 0xFFFF 的位元遮罩,與 EXP4 做位元運算會得到 EXP4 ,要使原式 a ^ (EXP4) = b,透過與 a 自己做 XOR 運算再與欲得之值 bXOR 便能成立,即 EXP4 = a ^ b

延伸問題

  1. 解釋上述程式碼運作的原理
  2. 針對 32 位元無號/有號整數,撰寫同樣 branchless 的實作
  3. Linux 核心也有若干 branchless / branch-free 的實作,例如 lib/sort.c:
    ​​​​/*
    ​​​​ * Logically, we're doing "if (i & lsbit) i -= size;", but since the
    ​​​​ * branch is unpredictable, it's done with a bit of clever branch-free
    ​​​​ * code instead.
    ​​​​ */
    ​​​​__attribute_const__ __always_inline
    ​​​​static size_t parent(size_t i, unsigned int lsbit, size_t size)
    ​​​​{
    ​​​​    i -= size;
    ​​​​    i -= size & -(i & lsbit);
    ​​​​    return i / 2;
    ​​​​}
    
    請在 Linux 核心原始程式碼中,找出更多類似的實作手法。請善用 git log 檢索。

延伸問題 : 針對 32 位元無號/有號整數的 branchless 實作

有號整數的 max :

改寫上方的有號整數版本 min

int32_t max(int32_t a, int32_t b) {
    int32_t diff = (a - b);
    return a + (-diff & (diff >> 31));
}
  • (diff >> 31) 作為判斷式兼位元遮罩,按照上面分析, diff 為正時位元遮罩為 0,回傳值即是第一項,故改寫為 a
  • diff 為負,需要回傳 b = a + (b - a) = a + (-diff),故原本的修量需要補上負號才能正確回傳 b

無號整數的 min :

改寫上方的無號整數版本的 max

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

只要修改判斷式成立的條件即可

測驗三

考慮以下 64 位元 GCD (greatest common divisor, 最大公因數) 求值函式:

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    while (v) {                               
        uint64_t t = v;
        v = u % v;
        u = t;
    }
    return u;
}

改寫為以下等價實作:

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

題目分析

等價實作中的 do-while 迴圈與原程式中的 while 迴圈皆是在進行輾轉相除法,結束條件為除數等於零,觀察兩段程式碼可以發現 v 皆是當中的除數,因此 COND 同樣也是 v

由於在等價實作中,進行輾轉相除法之前先提出了 u, v 兩數為最大的 2 的冪公因數,在回傳之前,必須先將由輾轉相除法得到的被除數 u 進行修正,將上面提出的最大的 2 的冪公因數乘回去,RETu << shift

延伸問題

  1. 解釋上述程式運作原理;
  2. 在 x86_64 上透過 __builtin_ctz 改寫 GCD,分析對效能的提升;
  3. Linux 核心中也內建 GCD (而且還不只一種實作),例如 lib/math/gcd.c,請解釋其實作手法和探討在核心內的應用場景。

延伸問題 : 程式運作原理

#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 (v);
    return u<<shift;
}

GCD 演算法

  1. If both x and y are 0, gcd is zero
    gcd(0,0)=0
    .
  2. gcd(x,0)=x
    and
    gcd(0,y)=y
    because everything divides 0.
  3. If x and y are both even,
    gcd(x,y)=2×gcd(x2,y2)
    because
    2
    is a common divisor. Mulitplication with
    2
    can be done with betwise shift operator.
  4. If x is even and y is odd,
    gcd(x,y)=gcd(x2,y)
    .
  5. On similar lines, if x is odd and y is even, then
    gcd(x,y)=gcd(x,y2)
    . It is because
    2
    is not a common divisor.

以下分段說明:

if (!u || !v) return u | v;

對應至 GCD 演算法第 2 點

  • gcd(x,0)=x
    and
    gcd(0,y)=y
    because everything divides 0.

若 u 和 v 中其中一數為 0 ,則直接回傳另一數

x | 0 會得到 x

int shift;
for (shift = 0; !((u | v) & 1); shift++) {
    u /= 2, v /= 2;
}

對應至 GCD 演算法第 3 點

  • If x and y are both even,
    gcd(x,y)=2×gcd(x2,y2)
    because
    2
    is a common divisor. Mulitplication with
    2
    can be done with betwise shift operator.

先取出uv 之間屬於

2n 的公因數,shift 即為最大的
n

while (!(u & 1))
    u /= 2;

對應至 GCD 演算法第4 點

  • If x is even and y is odd,
    gcd(x,y)=gcd(x2,y)
    .

u 為偶數時,可以除以

2

do {
    while (!(v & 1))
        v /= 2;
    if (u < v) {
        v -= u;
    } else {
        uint64_t t = u - v;
        u = v;
        v = t;
    }
} while (v);

其中 while(!(v &1)) v /= 2; 對應至 GCD 演算法第 5 點

  • On similar lines, if x is odd and y is even, then
    gcd(x,y)=gcd(x,y2)
    . It is because
    2
    is not a common divisor.

可以透過迴圈不變性 (loop invariant) 來幫助解讀程式

  • u 為被除數
  • v 為除數

當除數 v為 0 時結束迴圈,被除數 u 為進入迴圈前 uv 的最大公因數

事實上 u 在迴圈前不一定是被除數,因為先前透過 GCD 演算法第 4 點去除不必要的計算

return u << shift;

最後回傳最大公因數時,乘上原先取出屬於

2n 的公因數,可以透過左移達成

延伸問題 : 透過 __builtin_ctz 改寫程式

已知除法運算會耗費較多時間,我們可以利用 __builtin_ctz (編譯器會產生對應到現代微處理器的專門指令) 搭配上述針對二進位特性調整的演算法,減少除法的使用

改寫之前先透過 perf 分析程式,將一百萬組由 rand 函式生成的亂數傳入 gcd64 函式執行

$ gcc -g3 -O0 gcd.c -o gcd
$ perf record ./gcd
$ perf annotate

由上圖可以發現,花費 CPU 週期數最多的段落為迴圈當中的 v /= 2 運算,佔據約 28%

以下為改寫過後的程式

uint64_t gcd64_ctz(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int shift = __builtin_ctzll(u | v);
    u = u >> __builtin_ctzll(u);
    
    do {
        v = v >> __builtin_ctzll(v);
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (v);
    return u << shift;
}

透過 perf 分析前後差異

$ gcc -g -O0 gcdcmp.c -o gcdcmp
$ perf record ./gcdcmp
$ perf report

將同樣一百萬筆由 rand 函式所產生的亂數傳入 gcd64gcd64_ctz 函式比較,發現改寫過後的版本花費時間幾乎是原來的一半

延伸問題 : lib/math/gcd.c 實作手法

測驗四

在影像處理中,bit array (也稱 bitset) 廣泛使用,考慮以下程式碼:

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

考慮 GNU extension 的 __builtin_ctzll 的行為是回傳由低位往高位遇上連續多少個 0 才碰到 1。

用以改寫的程式碼如下:

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

其中第 9 行的作用是找出目前最低位元的 1,並紀錄到 t 變數。舉例來說,若目前 bitset 為

000101b,那 t 就會變成
000001b
,接著就可以透過 XOR 把該位的 1 清掉,其他保留 (此為 XOR 的特性)。

題目分析

題目提示要考慮到 -bitwise 的特性,在二補數編碼中,恰巧最低位元的 1 之下的位元皆會保留
(e.g.

(00101000)b=11011000b, (10111010)b=01000110b)

利用此特性,自己與自己的負數(二補數)進行 AND 操作,即可找出最低位元的 1
EXP6 即為 `bitset & -bitset'

延伸問題

  1. 解釋上述程式運作原理,並舉出這樣的程式碼用在哪些真實案例中;
  2. 設計實驗,檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進?應考慮到不同的 bitmap density;
  3. 思考進一步的改進空間;
  4. 閱讀 Data Structures in the Linux Kernel 並舉出 Linux 核心使用 bitmap 的案例;

程式運作原理

測驗五

以下是 LeetCode 166. Fraction to Recurring Decimal 的可能實作:

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

請補完,使得程式碼符合預期,儘量以最簡短且符合一致排版的形式來撰寫。

題目分析

先觀察 PPP, MMM, EEE 所處迴圈(第 77-97 行)的用途,可以大致分成三個部分:

  • 第 78-88 行: 尋找 remainder 是否存在於 hashmap 之中
    • 若存在,將小數部分依格式更新到 result 後,結束該函式並回傳
    • 若不存在,則繼續往下執行
  • 第 89-93 行: 建立節點,插入對應的 hashmap 位置
  • 第 95-96 行: 更新小數部分,並計算下一位的 remainder

PPP > 0 為條件式的 while 迴圈,負責更新循環小數前的部分,前面透過 find 函數取得循環小數開始的位數 pos,所以這裡需要更新 pos 個位數,由於該迴圈內部沒有額外操作,透過 pos-- 使迴圈執行的同時遞減 posPPPpos--

MMM, EEE 處於同一行,該行的作用為將建立好的節點插入對應的 hashmap 位置, MMM 即是 list API 插入節點的巨集 list_add ,至於要插入哪一個 head (heads[?]),需要回頭去看 hash 是如何計算,找到 find 函式有寫到 hash = key % size ,上面呼叫 find 函式時,是將 remainder 傳入 , EEE 即是 heads[remainder % size]

延伸問題

  1. 解釋上述程式碼運作原理,指出其中不足,並予以改進

    例如,判斷負號只要寫作 bool isNegative = numerator < 0 ^ denominator < 0;
    搭配研讀 The simple math behind decimal-binary conversion algorithms

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

測驗六

__alignof__ 是 GNU extension,以下是其可能的實作方式:

/*
 * 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)

請補完上述程式碼,使得功能與 __alignof__ 等價。

題目分析

觀察題目中的實作方法,發現是兩個位址相減
先透過結構體指標 struct {char c; t _h; } *將 0 視作該結構體的起始位址,
再存取型態為 t 的結構體成員 _h 位址,減去前一個成員的位址,
便可算出型態 t 在當前環境的 alignment

M 即是上述提到要測試的型態成員 _h,由於成員 c 作為第一個成員,起始位址與結構體相同,
X 即是一開始設定的結構體起始位址 0

延伸問題

  1. 解釋上述程式碼運作原理
  2. 在 Linux 核心原始程式碼中找出 __alignof__ 的使用案例 2 則,並針對其場景進行解說
  3. 在 Linux 核心源使程式碼找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集,探討其實作機制和用途,並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻,儘量共用相同的巨集

測驗七

考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目:

  • 從 1 數到 n,如果是 3的倍數,印出 “Fizz”
  • 如果是 5 的倍數,印出 “Buzz”
  • 如果是 15 的倍數,印出 “FizzBuzz”
  • 如果都不是,就印出數字本身

直覺的實作程式碼如下: (naive.c)

#include <stdio.h>
int main() {
    for (unsigned int i = 1; i < 100; i++) {
        if (i % 3 == 0) printf("Fizz");
        if (i % 5 == 0) printf("Buzz");
        if (i % 15 == 0) printf("FizzBuzz");
        if ((i % 3) && (i % 5)) printf("%u", i);
        printf("\n");
    }
    return 0;
}

觀察 printf 的(格式)字串,可分類為以下三種:

  1. 整數格式字串 "%d" : 長度為 2 B
  2. “Fizz” 或 “Buzz” : 長度為 4 B
  3. “FizzBuzz” : 長度為 8

考慮下方程式碼:

char fmt[M9];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");

我們若能精準從給定輸入 i 的規律去控制 startlength,即可符合 FizzBuzz 題意:

 string literal: "fizzbuzz%u"
         offset:  0   4   8

以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (bitwise.c)

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

其中 is_divisible 函式技巧來自 Faster remainders when the divisor is a constant: beating compilers and libdivide,甚至 gcc-9 還內建了 FizzBuzz optimization (Bug 82853 - Optimize x % 3 == 0 without modulo)。
請補完,使得程式碼符合預期,儘量以最簡短且符合一致排版的形式來撰寫。

題目分析

依據題目需求,先整理各個條件所對應的長度 length 和起點 start:

length start
3 的倍數 4 0
5 的倍數 4 4
15 的倍數 8 0
都不是 2 8

可以發現長度 length 都是 2 的冪

  • 符合零個條件時,長度為 2
  • 符合一個條件時,長度為 4
  • 符合兩個條件時,長度為 8

符合條件數與所需的位移量剛好相等,可將判斷條件的布林值直接帶入 KK1, KK2,分別為 div3, div5

再來起點的部分,題目已經先給定了 9 >> div5 的操作,透過真值表觀察位移量

9 >> div5 (9 >> div5) >> (KK3) KK3
3 的倍數 9 0
3
5 的倍數 4 4 0
15 的倍數 4 0
2
都不是 9 8 ?

發現題目有問題

延伸問題

  1. 解釋上述程式運作原理並評估 naive.cbitwise.c 效能落差
    • 避免 stream I/O 帶來的影響,可將 printf 更換為 sprintf
  2. 分析 Faster remainders when the divisor is a constant: beating compilers and libdivide 一文的想法 (可參照同一篇網誌下方的評論),並設計另一種 bitmask,如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」,然後再改寫 bitwise.c 程式碼,試圖運用更少的指令來實作出 branchless;
  3. 研讀 The Fastest FizzBuzz Implementation 及其 Hacker News 討論,提出 throughput (吞吐量) 更高的 Fizzbuzz 實作
  4. 解析 Linux 核心原始程式碼 kernel/time/timekeeping.c 裡頭涉及到除法運算的機制,探討其快速除法的實作 (注意: 你可能要對照研讀 kernel/time/ 目錄的標頭檔和程式碼)

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