# 2022q1 Homework2 (quiz2)
contributed by < [2020leon](https://github.com/2020leon) >
## [作業要求](https://hackmd.io/@sysprog/linux2022-homework2)
- [ ] 重新回答[第 2 周測驗題](https://hackmd.io/@sysprog/linux2022-quiz2)^從測驗一到測驗七^，附帶的「==延伸問題==」也需要完成
- 解釋程式運作原理時，應提供對應的 [Graphviz](https://graphviz.org/) 圖例，可參照 [Linked List 題目 1 + 分析](https://hackmd.io/@sysprog/linked-list-quiz)
- [ ] 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb), [Linked list 題目分析](https://hackmd.io/s/HyELy5bTz) 和 [參考題解](https://hackmd.io/@RinHizakura/BysgszHNw) 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及==進行相關實驗==。
- [x] 將你的共筆加到 [2022q1 Homework2 (作業區)](https://hackmd.io/@sysprog/linux2022-homework2)
- [x] 截止日期：
- Mar 13, 2022 (含) 之前
## [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz2)
### 測驗 `1`
本題之函式均在求二整數之平均值。
#### 測驗 `1` 填空
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
觀察陳述式 `(a >> 1) + (b >> 1) + (EXP1)` 可以了解到 `EXP1` 的功能為判斷其是否進位，即其範圍為零到一之間。將奇數和偶數分別代入變數 `a` 和變數 `b` 後可發現，唯一需要進位的情況為 `a` 和 `b` 同時為奇數之時。
由於現代電腦是以二進位表示數值，數值之最低有效位可用於判斷整數之奇偶性。目前目標為分別「兩個變數同時為奇數」及「其他」以上二者，因此使用 `&` 運算子；又僅需取出最低有效位，因此再與 `1` 做 `&` 運算。 `EXP1` 應填入 `a & b & 1` 。
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
首先觀察 `EXP3` ，對其進行右移一的運算可推得其可能與類似加號的位元運算有關，而 XOR 可是為位元和，因此 `EXP3` 應填入 `a ^ b` 。
然 `a ^ b` 未考慮進位問題，我們可以觀察到當兩個位元均為一時才需進位。在加法時可用 `(a & b) >> 1` 表示 `a + b` 的進位。而本題旨在計算平均，因此應為 `(a & b) >> 1 << 1` 。所以 `EXP2` 應填入 `a & b` 。
| 陳述式 | 答案 |
| ------ | ----------- |
| `EXP1` | `a & b & 1` |
| `EXP2` | `a & b` |
| `EXP3` | `a ^ b` |
:::info
參見：[數值系統篇#運用 bit-wise operator](https://hackmd.io/@sysprog/c-numerics#%E9%81%8B%E7%94%A8-bit-wise-operator)
:::
#### 測驗 `1` 組合語言
將所有在測驗 `1` 名為 average 的函式以 `gcc -S -masm=intel -Os foo.c` 化為組合語言，並去蕪存菁，僅保留指令部份。
首先是相加除以二的版本。
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (a + b) / 2;
}
```
```asm
average:
lea eax, [rdi+rsi]
shr eax
ret
```
:::info
以下是未去蕪存菁， `gcc` 的原始輸出：
```asm
.globl average
.type average, @function
average:
.LFB0:
.cfi_startproc
endbr64
lea eax, [rdi+rsi]
shr eax
ret
.cfi_endproc
.LFE0:
.size average, .-average
```
<!-- endbr64 https://lpc.events/event/2/contributions/147/attachments/72/83/CET-LPC-2018.pdf -->
<!-- https://stackoverflow.com/questions/15284947/understanding-gcc-s-output -->
:::
`lea` 即「 load effective address 」，後者為所謂「 effective address 」，中文謂之「[有效位址](https://terms.naer.edu.tw/detail/1277537/)」，其功能為將後者做完運算後賦值予前者。此例即 `eax` 的值會被賦為 `rdi + rsi` 。
`shr` 即「 shift right 」，將暫存器內的值向右移一位後存回。此例即將 `eax` 的值除以二。
`ret` 即「 return from procedure 」，回到原呼叫函式之處。
接著是避免 overflow 版。
```c
uint32_t average(uint32_t low, uint32_t high)
{
return low + (high - low) / 2;
}
```
```asm
average:
mov eax, esi
sub eax, edi
shr eax
add eax, edi
ret
```
此處指令命名皆直觀易解，即 `eax = esi - edi` ， `eax >>= 1` ， `eax += edi` ，最後結果存於 `eax` 。
接著是第一次改寫版。
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (a & b & 1);
}
```
```asm
average:
mov eax, edi
mov edx, esi
and edi, esi
shr eax
shr edx
and edi, 1
add eax, edx
add eax, edi
ret
```
第三個指令實做 `a & b` 並存在 `edi` ，第四和第五個指令實做 `a >> 1` 和 `b >> 1` 並存回原位，第六個指令實做 `edi & 1` 並存回 `edi` ，第七和第八個指令將三者相加後存在 `eax` 。
最後是第二次改寫版。
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (a & b) + ((a ^ b) >> 1);
}
```
```asm
average:
mov eax, edi
and edi, esi
xor eax, esi
shr eax
add eax, edi
ret
```
第二個指令實做 `a & b` 並存於 `edi` ，第三個指令實做 `a ^ b` 並存於 `eax` ，第四個指令實做 `eax >> 1` 並存回原位，第五個指令將二者相加後存於 `eax` 。
在此可觀查到此版本比上一個版本的指令數還少。
#### 研讀 `include/linux/average.h`
`include/linux/average.h` 內定義一個名為 `DECLARE_EWMA` 的巨集以實現固定精度的 EWMA 演算法。 EWMA 演算法求取移動平均﹐並對越久的歷史資料給予越低的權重。如下式。
$S_t = \begin{cases}
Y_0, & t = 0 \\
\alpha Y_t + (1 - \alpha) \cdot S_{t-1}, & t > 0
\end{cases}$
其中 $S_t$ 是在時間 $t$ 上的 EWMA 值， $Y_t$ 是在時間 $t$ 上的值， $\alpha$ 則是一個介於 0 和 1 的參數。
在來看 `DECLARE_EWMA` 的部份。
```c
#define DECLARE_EWMA(name, _precision, _weight_rcp) \
struct ewma_##name { \
unsigned long internal; \
}; \
static inline void ewma_##name##_init(struct ewma_##name *e) \
{ \
BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
/* \
* Even if you want to feed it just 0/1 you should have \
* some bits for the non-fractional part... \
*/ \
BUILD_BUG_ON((_precision) > 30); \
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
e->internal = 0; \
} \
static inline unsigned long \
ewma_##name##_read(struct ewma_##name *e) \
{ \
BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
BUILD_BUG_ON((_precision) > 30); \
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
return e->internal >> (_precision); \
} \
static inline void ewma_##name##_add(struct ewma_##name *e, \
unsigned long val) \
{ \
unsigned long internal = READ_ONCE(e->internal); \
unsigned long weight_rcp = ilog2(_weight_rcp); \
unsigned long precision = _precision; \
\
BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
BUILD_BUG_ON((_precision) > 30); \
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
\
WRITE_ONCE(e->internal, internal ? \
(((internal << weight_rcp) - internal) + \
(val << precision)) >> weight_rcp : \
(val << precision)); \
}
```
大致觀看程式碼可發現該巨集可謂「程式碼產生器」，產生一個結構及數個函式。再看巨集參數的部份，第一個參數為 `name` ，可為巨集中的結構即函式命名；第二個參數為 `_precision` ，定義小數精度，其單位為位元；第三個參數為 `_weight_rcp` ，即上方公式所提及之 $\alpha$ 的倒數，而其須為二的冪。
接著詳閱 `DECLARE_EWMA` 巨集。
在此定義一個名為 `ewma_##name` 的結構，內部僅定義一個 `unsigned long` 的成員。
```c
struct ewma_##name {
unsigned long internal;
};
```
:::info
注： `##` 即串接。若將 `name` 帶入 `a` ，則結構名為 `ewma_a` 。
:::
接著是 `ewma_##name##_init` 函式。
```c
static inline void ewma_##name##_init(struct ewma_##name *e)
{
BUILD_BUG_ON(!__builtin_constant_p(_precision));
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));
/*
* Even if you want to feed it just 0/1 you should have
* some bits for the non-fractional part...
*/
BUILD_BUG_ON((_precision) > 30);
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);
e->internal = 0;
}
```
內部可發現名為 `BUILD_BUG_ON` 的巨集，其定義在 [`include\linux\build_bug.h`](https://github.com/torvalds/linux/blob/master/include/linux/build_bug.h) 中，其功能為在編譯時期確認其參數是否為真，若為真則停止編譯。其中還可發現名為 `__builtin_constant_p` 的 `gcc` 內建函式，其功能為確認該參數是否為編譯時期常數。
該函式唯一的功能為將結構中的成員設為 0 ，且須在呼叫以下函式之前被呼叫。
再來是 `ewma_##name##_read` 函式，其功能便是讀取 EWMA 值的整數部份。
```c
static inline unsigned long
ewma_##name##_read(struct ewma_##name *e)
{
BUILD_BUG_ON(!__builtin_constant_p(_precision));
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));
BUILD_BUG_ON((_precision) > 30);
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);
return e->internal >> (_precision);
}
```
最後是 `ewma_##name##_add` 。
```c
static inline void ewma_##name##_add(struct ewma_##name *e,
unsigned long val)
{
unsigned long internal = READ_ONCE(e->internal);
unsigned long weight_rcp = ilog2(_weight_rcp);
unsigned long precision = _precision;
BUILD_BUG_ON(!__builtin_constant_p(_precision));
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));
BUILD_BUG_ON((_precision) > 30);
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);
WRITE_ONCE(e->internal, internal ?
(((internal << weight_rcp) - internal) +
(val << precision)) >> weight_rcp :
(val << precision));
}
```
在函式內的實做可以發現 `READ_ONCE` 和 `WRITE_ONCE` 巨集。此二巨集是為了避免編譯器過度優化，即避免其合併指令和調換順序。
此函式的功能為藉由 `val` 算出下一個 EWMA 值並存回結構的 `internal` 中。其實做關鍵之處為 `(((internal << weight_rcp) - internal) + (val << precision)) >> weight_rcp` ，其利用位移的技巧巧妙地算出下一個時間的值。
其在 Linux 核心內的應用如 `net/mac80211/sta_info.h` 等，與計算[來回通訊延遲](https://en.wikipedia.org/wiki/Round-trip_delay)有關。
### 測驗 `2`
#### 測驗 `2` 填空
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
在填空之前，先嘗試將上述改成有分支的實做。
```c
uint32_t max(uint32_t a, uint32_t b)
{
if (a > b)
return a ^ (0);
else
return a ^ (a ^ b);
}
```
再嘗試展開。
```c
uint32_t max(uint32_t a, uint32_t b)
{
if (a > b)
return a ^ ((0) & -(0));
else
return a ^ ((a ^ b) & -(1));
}
```
最後經過比較後，分別於 `EXP4` 和 `EXP5` 中填入對應的程式碼。
```c
uint32_t max(uint32_t a, uint32_t b)
{
// if (a > b)
// return a ^ ((a ^ b) & -(a <= b));
// else
// return a ^ ((a ^ b) & -(a <= b));
return a ^ ((a ^ b) & -(a < b));
}
```
| 陳述式 | 答案 |
| ------ | ------------------- |
| `EXP4` | `a ^ b` |
| `EXP5` | `a < b` 或 `a <= b` |
#### 測驗 `2` branchless 實作
即如下。
```c
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((a ^ b) & -(a < b));
}
```
#### Linux 核心的 branchless 實做
[arch/x86/kvm/mmu.h](https://github.com/torvalds/linux/blob/79e06c4c4950be2abd8ca5d2428a8c915aa62c24/arch/x86/kvm/mmu.h#L271) 為其中一個 branchless 實做。
```c
/*
* If CPL < 3, SMAP prevention are disabled if EFLAGS.AC = 1.
*
* If CPL = 3, SMAP applies to all supervisor-mode data accesses
* (these are implicit supervisor accesses) regardless of the value
* of EFLAGS.AC.
*
* This computes (cpl < 3) && (rflags & X86_EFLAGS_AC), leaving
* the result in X86_EFLAGS_AC. We then insert it in place of
* the PFERR_RSVD_MASK bit; this bit will always be zero in pfec,
* but it will be one in index if SMAP checks are being overridden.
* It is important to keep this branchless.
*/
unsigned long smap = (cpl - 3) & (rflags & X86_EFLAGS_AC);
```
### 測驗 `3`
#### 測驗 `3` 填空
```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 (COND);
return RET;
}
```
首先第一句 `if` 陳述式用以判斷所傳入之參數是否為零，若其中之一為零則回傳另一參數之值。即 $gcd(0, 0) = 0$ 、 $gcd(x, 0) = x$ 和 $gcd(0, y) = y$ 。
接下來的 `for` 迴圈判斷所傳入之參數是否皆為偶數，若皆為偶數則將其同時除以二，並以 `shift` 記錄迴圈次數（即除以幾個二）。在經過 `for` 迴圈後，即可保證 `u` 和 `v` 其中之一為奇數，且可以推論經過處理過的 `u` 和 `v` 目前最大公因數為奇數。以上對應到以下數學式：$gcd(x, y) = 2 ∗ gcd(x / 2, y / 2)$ 。
由於目前最大公因數為奇數，再來的 `while` 迴圈則將 `u` 關於二的因數去除。（ $gcd(x, y) = gcd(x / 2, y)$ ）
緊接著的 `do` `while` 迴圈的第一步則同上方的 `while` 迴圈，只是針對不同的變數做操作。再來的 `if` `else` 則是將二數相減，取其差的絕對值存入 `v` ，取二數較小者存入 `u` ，即輾轉相除法。
接著是 `do` `while` 的迴圈條件 `COND` 。輾轉相除法的結束條件為其中之一為零。由於 `v` 為二數之差，故以 `v` 作為檢查條件，而 `u` 則為經過處理過的二數之最大公因數。
最後在回傳值的部份需將偶數部份還原，也就是回傳 `u << shift` 。
| 陳述式 | 答案 |
| ------ | ------------ |
| `COND` | `v` |
| `RET` | `u << shift` |
#### 改寫 GCD
嘗試用 `__builtin_ctz` 改寫 GCD 。
```c
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v)
return u | v;
int shift_u = __builtin_ctzl(u);
int shift_v = __builtin_ctzl(v);
u >>= shift_u, v >>= shift_v;
do {
v >>= __builtin_ctzl(v);
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << (shift_u ^
((shift_u ^ shift_v) &
-(shift_u > shift_v))); // u << min(shift_u, shift_v)
}
```
#### Linux 核心中也內建 GCD
[lib/math/gcd.c](https://github.com/torvalds/linux/blob/457c89965399115e5cd8bf38f9c597293405703d/lib/math/gcd.c) 中其中一個實做如下。
```c
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;
}
}
```
其中 `__ffs` 為 find first set ，在此功能同 `ctz` 相關函式。
`r & -r` 即對於自己的二補數（一補數加一）進行 AND 運算，所以其結果為 `1 << __builtin_ctzl(r)` ，必為二的冪，可類比上方實做的 `shift` 。
其餘邏輯與上方實做相似。
在核心內的應用如 [lib/math/lcm.c](https://github.com/torvalds/linux/blob/457c89965399115e5cd8bf38f9c597293405703d/lib/math/lcm.c#L11) 、 [sound/core/pcm_timer.c](https://github.com/torvalds/linux/blob/df76996a2c5369769b23a017b6303f7ecacb277b/sound/core/pcm_timer.c#L28) 等。
### 測驗 `4`
#### 測驗 `4` 填空
```c
#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` 變數。
我們可以利用二補數的特性來完成 `EXP6` 的需求。考慮到 `xx100` （ `x` 代表 [don't-care term](https://en.wikipedia.org/wiki/Don%27t-care_term) ），其二補數亦為 `xx100` 。兩者做 AND 運算後亦為 `xx100` 故填入答案 `bitset & -bitset` 。
| 陳述式 | 答案 |
| ------ | ---------------------------------------- |
| `EXP6` | `bitset & -bitset` 或 `-bitset & bitset` |
### 測驗 `5`
#### 測驗 `5` 填空
```c
#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` | `pos--` |
| `MMM` | `list_add` |
| `EEE` | `&heads[remainder % size]` |
### 測驗 `6`
#### 測驗 `6` 填空
```c
/*
* 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)
```
可以觀察到其是利用 `struct` 對齊性質來實做 `alignof` 。首先觀察 `M` ，可發現其接在 `->` 運算子之後，所以應為 `c` 或 `_h` 其一；又若填入 `c` 則 `&((struct { char c; t _h; } *)0)->c` 恆為零，無法體現出 `t` 的型態，因此填入 `_h` 。而事實上 `&((struct { char c; t _h; } *)0)->c` 的值已是正確答案，將 `X` 填入 `0` 則不會影響結果。其回傳型態為 `ptrdiff_t` 。
| 陳述式 | 答案 |
| ----- | ---- |
| `M` | `_h` |
| `X` | `0` |
#### 找出 `ALIGN`, `ALIGN_DOWN`, `ALIGN_UP` 等巨集
`ALIGN` 、 `ALIGN_DOWN` 在 [include/linux/align.h](https://github.com/torvalds/linux/blob/08c5188ef40ff82aed559123dc0ab2d2254b1b1c/include/linux/align.h) 可見； `ALIGN_UP` 則在 [tools/testing/selftests/vm/pkey-helpers.h](https://github.com/torvalds/linux/blob/e89908201e2509354c40158b517945bf3d645812/tools/testing/selftests/vm/pkey-helpers.h) 可見。
### 測驗 `7`
#### 測驗 `7` 填空
```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;
}
```
上方程式碼的 `length` 變數表示 `fmt` 的長度。由規則可知，若為三的倍數需印出 Fizz 、五的倍數需印出 Buzz 、十五的倍數需印出 FizzBuzz 、其餘印出該數。因此可製成下表。
| 數值 | `length` |
| -------- | -------- |
| 三的倍數 | 4 |
| 五的倍數 | 4 |
| 十五的倍數 | 8 |
| 其他 | 2 |
由上表可推論 `(2 << KK1) << KK2` 為 `(2 << div3) << div5` 或 `(2 << div5) << div3` 。
接下來觀察 `(9 >> div5) >> (KK3)` 的值。
| 數值 | `(9 >> div5) >> (KK3)` | `KK3` |
| -------- | ---------------------- | ----- |
| 三的倍數 | 0 | 4 |
| 五的倍數 | 4 | 0 |
| 十五的倍數 | 0 | 4 |
| 其他 | 8 | ?(0) |
:::danger
校：上方程式碼之 `(9 >> div5) >> (KK3)` 應為 `(8 >> div5) >> (KK3)` ，否則該印數字之處會錯誤印出 `u` 字樣。
:::
可知 `KKK3` 為 `div3 << 2` 。
| 陳述式 | 答案 |
| ----- | ----------- |
| `KK1` | `div3` |
| `KK2` | `div5` |
| `KK3` | `div3 << 2` |
Sign in with Wallet
Connect another wallet