2022q1 Homework2 (quiz2)
contributed by < hsuedw
>
測驗 1
題目
- 以 bitwise 操作對兩個無號整數取平均值。
- 也就是撰寫程式碼 2 中的
EXP1
使其功能等價於程式碼 1。
- 也就是撰寫程式碼 3 中的
EXP2
與 EXP3
使其功能等價於程式碼 1。
- 程式碼 1
- 程式碼 2
- 程式碼 3
作答
EXP1
= a & b & 1
- 假設
EXP2
= a & b
EXP3
= a ^ b
延伸問題 1. 解釋上述程式碼運作的原理
-
程式碼 2 運作的原理
- 在 bitwise 運算中,向左位移一個 bit 就相當於 ,其中
- 雖然在數學上 = + ,但是在 C 語言中,當 a 與 b 皆為奇數時,因為 a 與 b 皆個別先除以 2 再相加,所以平均值會少 1。假設 a = 3,b = 5。
- (a + b) / 2 = 4
- a / 2 + b / 2 = 3
- 若 a 與 b 為一奇一偶或皆為偶數,則沒有這個現象。
- 一個奇數的二進為編碼中,LSB 必為 1。若
a & b
的 LSB 為 1,表示 a 與 b 皆為奇數。所以將 EXP1 實作為 a & b & 1
可補上當 a 與 b 皆為奇數時,各別先除二再相加所少掉的那個 1。
-
程式碼 3 運作的原理
- AND 與 XOR 的真值表如下所示。
|
|
AND |
XOR |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
- 一個位元的加法運算如下所示。觀察後可發現進位 (carry) 那一欄就是 AND 運算。 bit sum 那一欄就是 XOR 運算。所以可以用 AND 與 XOR 進行加法運算。
|
carry |
bit sum |
0 + 0 |
0 |
0 |
0 + 1 |
0 |
1 |
1 + 0 |
0 |
1 |
1 + 1 |
1 |
0 |
- 對兩個整數 a 與 b 做加法。
a ^ b
就是每個位元的各別位元和。 (a & b) << 1
就是兩數相加後,各別位元的進位狀況。所以,C 語言程式碼中, a + b
可改寫為 (a ^ b) + ((a & b) << 1)
。
(a + b) / 2
就是 (a + b) >> 1
。
- 所以,
(a + b) >> 1
就是 ((a ^ b) + ((a & b) << 1)) >> 1
。展開後就可以得到 (a & b) + (a ^ b) >> 1
。
- 所以,
EXP2
可實作為 a & b
, EXP3
可實作為 a ^ b
。
-
參考資料:
延伸問題 2. 比較上述實作在編譯器最佳化開啟的狀況,對應的組合語言輸出,並嘗試解讀 (可研讀 CS:APP 第 3 章)
延伸問題 3. 研讀 Linux 核心原始程式碼 include/linux/average.h,探討其 Exponentially weighted moving average (EWMA) 實作,以及在 Linux 核心的應用
移動平均(Moving average),又稱滾動平均值、滑動平均,在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數,來分析資料點的計算方法。
移動平均通常與時間序列資料一起使用,以消除短期波動,突出長期趨勢或周期。短期和長期之間的閾值取決於應用,移動平均的參數將相應地設置。例如,它通常用於對財務數據進行技術分析,如股票價格、收益率或交易量。它也用於經濟學中研究國內生產總值、就業或其他宏觀經濟時間序列。
測驗 2
題目
作答
延伸問題 1. 解釋上述程式碼運作的原理
- 列舉部分 AND 與 XOR 運算的特性。
- a ^ a = 0
- a ^ 0 = a
- a ^ 0xffffffff = 0 (假設 a 為 32 位元整數)
- a & a = a
- a & 0 = 0
- a & 0xffffffff = a
- 為了說明方便,把程式碼補齊,如下所示。
- 假設 a > b
a ^ ((a ^ b) & -(a < b))
- ⇒
a ^ ((a ^ b) & -(0))
C99 Standard
6.5.8 Relational operators
Each of the operators < (less than), > (greater than), <= (less than or equal to), and >= (greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false.) The result has type int.
- ⇒
a ^ ((a ^ b) & 0)
- ⇒
a ^ (0)
- ⇒
a
- 假設 a < b
a ^ ((a ^ b) & -(a < b))
- ⇒
a ^ ((a ^ b) & -(1))
- ⇒
a ^ ((a ^ b) & 0xffffffff)
- ⇒
a ^ (a ^ b)
- ⇒
(a ^ a) ^ b
- ⇒
(0) ^ b
- ⇒
b
- 假設 a = b
a ^ ((a ^ b) & -(a < b))
- ⇒
a ^ ((a ^ a) & -(a < a))
- ⇒
a ^ ((0) & -(1))
- ⇒
a ^ (0x00000000 & 0xffffffff)
- ⇒
a ^ (0)
- ⇒
a
- 參考資料:
延伸問題 2. 針對 32 位元無號/有號整數,撰寫同樣 branchless 的實作
延伸問題 3. Linux 核心也有若干 branchless / branch-free 的實作,例如 lib/sort.c。
請在 Linux 核心原始程式碼中,找出更多類似的實作手法。請善用 git log 檢索。
測驗 3
題目
考慮以下 64 位元 GCD (greatest common divisor, 最大公因數) 求值函式:
註: GCD 演算法
- If both x and y are 0, gcd is zero .
- and because everything divides 0.
- If x and y are both even, because 2 is a common divisor. Multiplication with 2 can be done with bitwise shift operator.
- If x is even and y is odd, .
- On similar lines, if x is odd and y is even, then . It is because 2 is not a common divisor.
改寫為以下等價實作:
作答
COND
= v
RET
= u << shift
延伸問題 1. 解釋上述程式運作原理
延伸問題 2. 在 x86_64 上透過 __builtin_ctz 改寫 GCD,分析對效能的提升
延伸問題 3. Linux 核心中也內建 GCD (而且還不只一種實作),例如 lib/math/gcd.c,請解釋其實作手法和探討在核心內的應用場景。
測驗 4
題目
在影像處理中,bit array (也稱 bitset) 廣泛使用,考慮以下程式碼:
考慮 GNU extenstion 的 __builtin_ctzll的行為是回傳由低位往高位遇上連續多少個 0 才碰到 1。
範例: 當 a = 16
16 這個十進位數值的二進位表示法為 00000000 00000000 00000000 00010000
從低位元 (即右側) 往高位元,我們可發現 0 → 0 → 0 → 0 → 1 ,於是 ctz 就為 4,表示最低位元往高位元有 4 個 0
用以改寫的程式碼如下:
其中第 9 行的作用是找出目前最低位元的 1
,並紀錄到 t
變數。舉例來說,若目前 bitset
為 000101b,那 t
就會變成 000001b,接著就可以透過 XOR 把該位的 1
清掉,其他保留 (此為 XOR 的特性)。
若 bitmap 越鬆散 (即 1
越少),於是 improved
的效益就更高。
請補完程式碼。書寫規範:
- bitwise 運算子和運算元之間用一個半形空白區隔,如: bitset | 0x1
- 考慮到 -bitwise 的特性
- 不要包含任何小括號,即 ( 和 )
- 以最精簡的形式撰寫程式碼
作答
延伸問題 1. 解釋上述程式運作原理,並舉出這樣的程式碼用在哪些真實案例中
-
運作原理
- 假設
bitset
的二進位表示法中,由 LSB 往 MSB 數,遇到第一個 1
前,有 x 個 0
。目標就是保留位元 x 為 1。其餘位元皆設為 0
。
- 假設
bitset
= 131210 = 0000010100100000b
- 則
-bitset
= -131210 = 1111101011100000b
- 所以,
-bitset & bitset
結果如下。
-
用在哪些真實案例中
延伸問題 2. 設計實驗,檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進?應考慮到不同的 bitmap density
延伸問題 3. 思考進一步的改進空間
延伸問題 4. 閱讀 Data Structures in the Linux Kernel 並舉出 Linux 核心使用 bitmap 的案例
測驗 5
題目
以下是 LeetCode 166. Fraction to Recurring Decimal 的可能實作:
請補完,使得程式碼符合預期,儘量以最簡短且符合一致排版的形式來撰寫。
PPP = ? (表示式)
MMM = ? (巨集)
EEE = ? (表示式)
作答
PPP
= pos--
MMM
= list_add
EEE
= &heads[remainder % size]
延伸問題 1. 解釋上述程式碼運作原理,指出其中不足,並予以改進
例如,判斷負號只要寫作 bool isNegative = numerator < 0 ^ denominator < 0;
搭配研讀 The simple math behind decimal-binary conversion algorithms
- 第 26~24 行。
- 用
malloc
動態宣告一個長度為 1024 bytes 的記憶體空間。用這個記憶體空間存字串。並用 result
這個指標指向這個記憶體空間的起始位址。然後再宣告一個指標 p
用來操作 result
所指向的記憶體空間。原則上,就是用 result
所指向的記憶體空間做出一個 C sytle string。
- 根據題意,將計算結果表示為字串,此字串長度小於 104。所以,將變數
size
初始化為 1024 並以此宣告記憶體大小,顯然有問題。
It is guaranteed that the length of the answer string is less than 104 for all the given inputs.
- 若考慮 C style string 的 null terminator。
size
應初始化為 10001 較為恰當。
- 第 30~32 行。
- 若
denominator
(分母)為 0,則回傳空字串。
- 事實上,這個判斷可以刪除,不需要實作這三行。因為題目的 constraints 中已經明白的說明了分子與分母的數值範圍。根據題意,分母不可能為 0。
Constraints:
- -231 <= numerator, denominator <= 231 - 1
- denominator != 0
- 第 35~39 行。
- 若
numerator
為 0,則計算結果必為 0。所以直接在 result
所指向的記憶體空間的第一個字元填 0
,第二個字元填 \0
(null terminator)。並回傳此 C style string。
- 第 41~53 行。
- 用兩個型態為
long long
的變數 n
與 d
分別儲存 numerator
與 denominator
的數值。並對 n
與 d
取絕對值。若 numerator
除以 denominator
是負數,在第 51~53 行中,把負號填入 result
所指向的記憶體空間的第一個字元。然後,指標 p
往後移一個 byte。
- 第 51~53 行中判斷最後的答案是否有負號,可改為下列的實作。因為
numerator
和 denominator
不同時為正數或不同時為負數,最後的答案就會有負號。所以可用 XOR 實作。
- 第 55~63 行。
- 分別把
n
除以 d
的餘數與商數指派給 remainder
與 division
兩個變數中。
- 以指標
p
所指的記憶體位址為起始,用 sprintf
與格式化字串把 division
列印到 result
所指向的記憶體空間。
- 因為第 46~53 已經處理了正負號的問題,所以執行到第 58 行時,
division
必為正數。第 58 行應改為:
- 若
remainder
(餘數)為 0 ,表示整除。可以直接回傳 result
所指向的記憶體空間內的字串。
- 若
remainder
(餘數)不為 0 ,表示有小數位數。所以將指標 p
移到字串的尾端(第 62 行)後,在字串尾端加入小數點。
- 第 68~70 行。
- 以指標
decimal
指向以 size
為大小所動態宣告的記憶體空間。並將此記憶體空間的內容清為 0。
- 以指標
q
為操作 decimal
所指向的記憶體空間。
- 因為題目已經保證最後的答案部會超過 104,所以第 68~69 行可以改為
- 第 72~75 行。
- 建立並初始化一個有 1333 個 bucket 的 hash table (指標
heads
所指的記憶體空間)。每個 bucket 都是一個環狀雙向鏈結串列。
- 不了解為什麼要 1333 個 bucket。
- 第 77~97 行。
- 這個
for
迴圈會一直執行到 remainder
等於 0 為止。
for
迴圈的 i 等於 0,表示小數點後第一位;i 等於 1,表示小數點後第二位
- 若在 hash table 中找到
remainder
,代表發生循環小數。
- 透過指標
p
的操作,把 decimal
裡的資料複製到 result
所指向的記憶體空間中。 (第 80~81 行)
- pos 是循環小數開始的位置,所以先將尚未循環的小數位數填到
result
所指向的記憶體空間中。
- 透過指標
p
的操作,在字串最後加上 open parenthesis。(第 82 行)
- 透過指標
p
的操作,再把 decimal
中剩下的循環小數填到 result
所指向的記憶體空間中。(第 83~84 行)
- 透過指標
p
的操作,在字串最後加上 closing parenthesis。(第 85 行)
- 最後,透過指標
p
的操作,填上 '\0'
(null terminator)。然後回傳結果(就是 result` 所指向的記憶體空間中的 C style string)。 (第 86~87 行)
- 若在 hash table 中找不到
remainder
,代表沒有發生循環小數。
- 用動態記憶體宣告產生一個
struct rem_node
型態的 object,並以指標 node
指向它。利用此物件把這一次的 numerator
與 i
記錄在 hash table (指標 heads
所指的記憶體空間)中。 (第 89~91 行)
- 透過指標
q
的操作,將小數點後的第一位寫入 decimal
所指向的記憶體空間中的字串的尾端。 (第 95 行)
- 更新
remainder
。 (第 96 行)
- 第 99~100 行
- 若第 77~97 行的
for
迴圈結束(remainder
歸 0),表示沒有循環小數發生。把 decimal
裡的所有字元全部複製到 result
所指向的記憶體空間中的字串的尾端。
- 回傳最後結果。
完整程式碼
struct list_head {
struct list_head *prev;
struct list_head *next;
};
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#define list_entry(node, type, member) container_of(node, type, member)
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member))
#define list_for_each_entry(entry, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member); \
&entry->member != (head); \
entry = list_entry(entry->member.next, __typeof__(*entry), member))
#define list_last_entry(head, type, member) \
list_entry((head)->prev, type, member)
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
}
static inline void list_move(struct list_head *node, struct list_head *head)
{
list_del(node);
list_add(node, head);
}
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 = 10001;
char *result = malloc(size);
char *p = result;
if (numerator == 0) {
result[0] = '0';
result[1] = '\0';
return result;
}
long long n = numerator;
long long d = denominator;
if (n < 0)
n = -n;
if (d < 0)
d = -d;
bool sign = (numerator < 0) ^ (denominator < 0);
if (sign)
*p++ = '-';
long long remainder = n % d;
long long division = n / d;
sprintf(p, "%ld", (long) division);
if (remainder == 0)
return result;
p = result + strlen(result);
*p++ = '.';
char *decimal = malloc(size - strlen(result));
memset(decimal, 0, size - strlen(result));
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 (pos-- > 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;
list_add(&node->link, &heads[remainder % size]);
*q++ = (remainder * 10) / d + '0';
remainder = (remainder * 10) % d;
}
strcpy(p, decimal);
return result;
}
延伸問題 2. 在 Linux 核心原始程式碼的 mm/
目錄 (即記憶體管理) 中,找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例,予以探討和解說其應用場景
測驗 6
題目
alignof 是 GNU extension,以下是其可能的實作方式:
請補完上述程式碼,使得功能與 alignof 等價。
請補完,使得程式碼符合預期,儘量以最簡短且符合一致排版的形式來撰寫
M = ?
X = ?
作答
M
= _h
X
= 0
- test my answer
#include <stdio.h>
#include <stddef.h>
#define ALIGNOF(t) \
((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0)
int main()
{
printf("char, %ld\n", __alignof__(char));
printf("unsigned char, %ld\n", __alignof__(unsigned char));
printf("int, %ld\n", __alignof__(int));
printf("long, %ld\n", __alignof__(long));
printf("long long, %ld\n", __alignof__(long long));
printf("unsigned ing, %ld\n", __alignof__(unsigned int));
printf("unsigned long, %ld\n", __alignof__(unsigned long));
printf("unsigned long long, %ld\n", __alignof__(unsigned long long));
printf("double, %ld\n", __alignof__(double));
printf("float, %ld\n", __alignof__(float));
printf("---------------\n");
printf("char, %ld\n", ALIGNOF(char));
printf("unsigned char, %ld\n", ALIGNOF(unsigned char));
printf("int, %ld\n", ALIGNOF(int));
printf("long, %ld\n", ALIGNOF(long));
printf("long long, %ld\n", ALIGNOF(long long));
printf("unsigned ing, %ld\n", ALIGNOF(unsigned int));
printf("unsigned long, %ld\n", ALIGNOF(unsigned long));
printf("unsigned long long, %ld\n", ALIGNOF(unsigned long long));
printf("double, %ld\n", ALIGNOF(double));
printf("float, %ld\n", ALIGNOF(float));
return 0;
}
- 參考資料:
延伸問題 1. 解釋上述程式碼運作原理
(char *)(&((struct { char c; t _h; } *)0)->_h)
- 先將
struct { char c; t _h; }
型態結構體的位址變更為 0。
- 然後再提取型態為
t
的成員 _h
的記憶體位址。
- 然後再轉成
char *
,也就是由位址 0 到成員 _h
的 offset。
- 同理,
(char *)0
就是取得位址 0 。
- 兩者相減就是型態
t
的 alignment。
- 編譯器處理
&((TYPE *)0)->MEMBER
時,不會真正去存取地址為 0 的記憶體區段,只是將 0 看做指標操作的一個運算元。也就是說,編譯器只是把記憶體位址拿來當數字一樣做運算。並不會真的對記憶體位址所表示的記憶體區間做存取的動作。
延伸問題 2. 在 Linux 核心原始程式碼中找出 alignof 的使用案例 2 則,並針對其場景進行解說
延伸問題 3. 在 Linux 核心源使程式碼找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集,探討其實作機制和用途,並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻,儘量共用相同的巨集
測驗 7
題目
作答
KK1
= div3
KK2
= div5
KK3
= div3 << 2
- note: 第 17 行應改為
否則,當 i 不為 3、5 或 15 的倍數時,無法印出 i 的值。
完整程式碼
延伸問題 解釋上述程式運作原理並評估 naive.c
和 bitwise.c
效能落差 (避免 stream I/O 帶來的影響,可將 printf 更換為 sprintf)
延伸問題 4. 解析 Linux 核心原始程式碼 kernel/time/timekeeping.c 裡頭涉及到除法運算的機制,探討其快速除法的實作 (注意: 你可能要對照研讀 kernel/time/
目錄的標頭檔和程式碼)
過程中,你可能會發現可貢獻到 Linux 核心的空間,請充分討論
答案卷