# 2020q3 Homework2 (quiz2)

contributed by < `blueskyson` >

###### tags: `linux2020`

## 測驗 `1`

目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (ANSI) 制定的 ASCII 碼，被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。如果我們明確界定 7 位元編碼的字元隸屬於 ASCII，可透過以下函式來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元:

#include <stddef.h>
bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    for (int i = 0; i < size; i++)
        if (str[i] & 0x80) /* i.e. (unsigned) str[i] >= 128 */
            return false;
    return true;
}

其中 str 是開頭的記憶體地址，size 則是要檢驗的範圍。逐一字元比對的效率低，在 64 位元的架構下，我們嘗試一次比對 64 位元的資料 (即 word size)，程式碼改寫如下:

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    int i = 0;
    while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        if (payload & MMM)
            return false;
        i += 8;
    }
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}

### 解題

已知一個 8 bit 大小的 ascii 碼的第 8 個位元必須為 0 ，也就是 `str[i] & 0x80 == 0x0` ，否則該字元就超過 ascii 的範圍。現以 64 bit 的變數 payload 儲存 8 個連續的 8 bit 大小的字元，我們就檢查第 8, 16, 24, ..., 64 位元是否有有位元為 1 ，即 ==MMM== = 0x8080808080808080 。最後，如果無法一次檢查八個字元，再改回一個一個檢查。

## 測驗 `2`

開發解析器 (parser) 時，常會將十六進位表示的字串 (hexadecimal string) 轉為數值，例如 '0xF' (大寫 F 字元) 和 '0xf' (小寫 f 字元) 都該轉換為 15。考慮以下不需要分支 (branchless) 的實作:

uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & MASK;
    const uint8_t shift = (letter >> AAA) | (letter >> BBB);
    return (in + shift) & 0xf;
}

已知 in 一定隸屬於 '0', '1', '2', …, '9' 及 'a', 'b', 'c', …, 'f' (小寫) 及 'A', 'B', 'C', …, 'F' (大寫) 這些字元。預期 hexchar2val('F') 和 hexchar2val('f') 回傳 15，且 hexchar2val('0') 回傳 0，其他輸入都有對應的數值。

以下摘自 ASCII 表格

- '0', '1', '2', …, '9' 對應到 0x30, 0x31, 0x32, … 0x39
- 'a', 'b', 'c', …, 'f' (小寫) 對應到 0x61, 0x62, 0x63, …, 0x66
- 'A', 'B', 'C', …, 'F' 對應到 0x41, 0x42, 0x43, …, 0x46
請補完程式碼。

### 解題

分別觀察 0, a, A 的 ascii 碼:

| ascii | binary |
|-------|---------|
|0 |0011 0000|
|a |0110 0001|
|A |0100 0001|

我猜測第三行的 `letter` 是用來判斷該字元是否為英文字母，而由上表可以發現: 英文字母 a ~ f 和 A ~ F 的二進位碼都是 01XXXXXX ，所以 ==MASK== = 0x40

接下來先觀察第五行的回傳方式 `return (in + shift) & 0xf;` 可以發現回傳值與 `0xf`，也就是 `0000 1111` 做 `&` 運算，所以回傳值會強制將第 8 到第 5 bit 設為 0 ，對於數字的字元，不須做平移即可與 `0xf` 運算出正確的數值，由此可以推論， `shift` 是為英文字母 A ~ F 做的處理。

再來觀察字母 `A` 與 `0xf` 做 `&` 運算，結果為 `0000 0001` ，與預期結果 `0000 1010` 的差值為 9 ，所以可以推論在字元為英文字母的狀況下， `shift` 的值為 `0000 1001` ，即 ==AAA== = 3 、 ==BBB== = 6 ，便可製造出所求`shift` 值。

## 測驗 `3`

除法運算的成本往往高於加法和乘法，於是改進的策略被引入。其中一種策略是將除法改為乘法運算，例如 $n/d$ 在分子和分母分別乘上 $2^N$後，得到等價的 $n\times\dfrac{\dfrac{2^N}{d}}{2^N}$，其中對 2 的 N 次方 (power of 2) 進行除法，在無號整數的操作就等同於右移 (shift) N 個位元，又當 d (除數) 的數值是已知的狀況下， $\dfrac{2^N}{d}$ 可預先計算，也就是說， $\dfrac{n}{d}$ 可轉換為乘法和位移操作，進而減少運算成本。不過，顯然 $\dfrac{2^N}{d}$ 無法總是用整數來表達 (僅在 d 是 power of 2 的時候才可)，因此，我們可先估算，並將差值補償回去。

重新檢視 $\dfrac{n}{d} = n \times \dfrac{\dfrac{2^N}{d}}{2^N}$，當我們想將 n 除以 4 時，就相當於乘以 0.25，所以我們可將 $\dfrac{5}{4}$ 改為 $5 \times 0.25$，我們得到整數的部分 (即 1 )，和小數部分 (即 0.25 )，後者乘以 4 就是 1，也就是餘數。下方程式碼展示這概念:

const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1))

/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n)
{
    uint64_t quotient = ((__uint128_t) M * n) >> 64;
    return n - quotient * D;
}

其中 `__uint128_t` 是 GCC extension，用以表示 128 位元的無號數值。

>[GCC: C Extensions: 128-bit Integers](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html)

預期 `quickmod(5)` 會得到 `2`, `quickmod(55)` 得到 `1`, `quickmod(555)` 得到 `0` (555 是 3 的倍數)。

請補完程式碼。

### 解題

第七行的 `>> 64` 可以視為「除以 $2^{64}$」，我們可以將第七行改寫為:

$$quotient = \dfrac{n \times M}{2^{64}}$$

$$\Rightarrow quotient = n \times \dfrac{\dfrac{XXX}{D} + 1}{2^{64}}$$

$$\Rightarrow quotient = \dfrac{n}{D} \times \dfrac{XXX + D}{2^{64}}$$

$$\Rightarrow quotient \times D = n \times \dfrac{XXX + D}{2^{64}}$$

此時 ==XXX== 應該要為 $2^{64}$ 但是 64 bit 最大只能儲存 $2^{64} - 1$ ，所以答案為 0xFFFFFFFFFFFFFFFF

## 測驗 `4`

延伸測驗 `3`，我們想判斷某個數值能否被指定的除數所整除，在 D 和 M 都沿用的狀況下，程式碼如下:

bool divisible(uint32_t n)
{
    return n * M <= YYY;
}

以 `D = 3` 來說， `divisible(7)` 要得到 `0` (即 7 無法被 3 整除)，`divisible(87)` 要得到 1 (即白痴是三的倍數)

請補完程式碼。

### 解題

$$n \times M = n \times (\dfrac{2^{64} - 1}{D} + 1) \\
= \dfrac{n}{D} \times 2^{64} - \dfrac{n}{D}＋1$$

觀摩 [ccs100203](https://hackmd.io/@cccccs100203/linux2020-quiz2#%E6%B8%AC%E9%A9%97-4) 的解法，首先計算 $M = \dfrac{2^{64} - 1}{3} =$ 0x55..56

n * m 即 n * (0x5555555555555555 + 1)，此時將 n 歸納為三種情況:

- n = 3k: n * m = k * (0xffffffffffffffff + 3) = 2k
- n = 3k + 1: n * m = k * (0xffffffffffffffff + 3) + (0x5555555555555555 + 1) = 2k + M
- n = 3k + 2: n * m = k * (0xffffffffffffffff + 3) + 2 * (0x5555555555555555 + 1) = 2k + 2M

當 ==YYY== = M - 1 時，可以篩選出 n = 3k 的情況

## 測驗 `5`

考慮 `strlower` 函式的作用是將指定的字串 (或部分字串) 的英文字母全改為小寫，其 [in-place](https://en.wikipedia.org/wiki/In-place_algorithm) 的實作如下:

#include <ctype.h>
#include <stddef.h>
/* in-place implementation for converting all characters into lowercase. */
void strlower(char *s, size_t n)
{
    for (size_t j = 0; j < n; j++) {
        if (s[j] >= 'A' && s[j] <= 'Z')
            s[j] ^= 1 << 5;
        else if ((unsigned) s[j] >= '\x7f') /* extended ASCII */
            s[j] = tolower(s[j]);
    }
}

針對 extended ASCII，我們呼叫 C 語言標準函式庫的 [tolower](https://man7.org/linux/man-pages/man3/tolower.3.html)，需要留意到在不同的語系 (locale)，字母順序和大小寫的定義可能異於我們認知的英文字母。以下摘自手冊:

>If c is a lowercase letter, toupper() returns its uppercase equivalent, if an uppercase representation exists in the current locale. Otherwise, it returns c.

語系對程式碼的影響不能輕忽，舉例來說，若語系設定為捷克語，以 “Ch” (屬於 digraph，二合拉丁字母，常見於西歐語言) 開頭的字串要排在 “H” 之後，但單看字母的話，“C” 要在 “B” 之後。不過，如果明確只處理英美語系 (American/British English)，上述程式碼列表的第 9 及第 10 行可略去。

> 捷克字母 (依序)
A a Á á B b C c Č č D d Ď ď E e É é Ě ě F f G g H h Ch ch I i
Í í J j K k L l M m N n Ň ň O o Ó ó P p Q q R r Ř ř S s Š š
T t Ť ť U u Ú ú Ů ů V v W w X x Y y Ý ý Z z Ž ž

在 64 位元處理器架構 (以下針對 `x86_64`, little endian)，我們可引入向量化 (vectorized) 的手段，避免一次比對一個字元，而是直接操作一整個 word (對 x86_64 來說，就是 64 bits，或 8 個位元組)。沿用上述的 `strlower` 函式，我們用這樣的思路實作向量化的 `strlower`，程式碼列表如下:

#include <ctype.h>
#include <stddef.h>
#include <stdint.h>

#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)

/* vectorized implementation for in-place strlower */
void strlower_vector(char *s, size_t n)
{
    size_t k = n / 8;
    for (size_t i = 0; i < k; i++, s += 8) {
        uint64_t *chunk = (uint64_t *) s;
        if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */
            uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2); 
            uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3);
            uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2;
            *chunk ^= mask;
        } else
            strlower(s, 8);
    }
    
    k = n % 8;
    if (k)
        strlower(s, k);
}

對應的測試程式碼如下:

#include <stdio.h>
#include <string.h>
int main()
{
    /* quote from https://www.gutenberg.org/files/74/74-h/74-h.htm */
    char str[] =
        "This eBook is for the use of anyone anywhere at no cost and with \
almost no restrictions whatsoever.  You may copy it, give it away or \
re-use it under the terms of the Project Gutenberg License included \
with this eBook or online at www.gutenberg.net";
    int n = strlen(str);
    strlower_vector(str, n);
    puts(str);
}

參考執行輸出:

> this ebook is for the use of anyone anywhere at no cost and with almost no restrictions whatsoever. you may copy it, give it away or re-use it under the terms of the project gutenberg license included with this ebook or online at `www.gutenberg.net`

請補完程式碼。

### 解題

首先觀察 `PACKED_BYTE` 的作用是讓 `b` 的最尾端 8 個 bit 重複填入 8 個 byte 裡面，接下來看到函示 `strlower_vector` ，第 11 行的 for 迴圈會 8 個 byte 為單位檢查是否有 extended ASCII ，而 extended ASCII 的特點就是第 8 個 bit 為 1 ，所以 ==VV1== = 0x80 ，將 0x80 擴展為 8 byte 以利一次檢查 8 個字元。

分別觀察 a, A 的 ascii 碼:

| ascii | binary |
|-------|---------|
|a |0110 0001|
|A |0100 0001|

第 13 行，假設 `chunk` 裡的字元為 A 或之後的字元，則變數 `A` 中每個字元的值都將大於等於 128 + VV2，也就是每個字元的 MSB 幾乎都是 1

第 14 行，假設 `chunk` 裡的字元為 Z 或之後的字元，則變數 `Z` 中每個字元的值都將大於等於 128 + VV3，也就是每個字元的 MSB 幾乎都是 1

到此，我推理出此兩行的程式碼用意為判斷 `chunk` 中的字元是否在 A~Z 的範圍內:

- 若字元小於 A ，則 `A` 的 MSB 為 0 且 `Z` 的 MSB 為 0，`A ^ Z = 0xxx xxxx`
- 若字元屬於 ['A', 'Z']，則 `A` 的 MSB 為 1 且 `Z` 的 MSB 為 0，`A ^ Z = 1xxx xxxx`
- 若字元大於 Z ，則 `A` 的 MSB 為 1 且 `Z` 的 MSB 為 1，`A ^ Z = 0xxx xxx`

由此很明顯可以看出 ==VV2== = 0 、 ==VV3== = -1

第 15 行只要將 MSB 的 1 往下移兩位並與原來的字元做 `^` 即可得到小寫字母，所以 ==VV4== = 0x80 ，也就是 1000 0000

## 測驗 `6`

LeetCode 137. [Single Number II](https://leetcode.com/problems/single-number-ii/):

>Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:
Input: `[2,2,3,2]`
Output: 3

Example 2:
Input: `[0,1,0,1,0,1,99]`
Output: 99

考慮以下程式碼為 [LeetCode 137. Single Number II](https://leetcode.com/problems/single-number-ii/) 的題解:

int singleNumber(int *nums, int numsSize)
{
    int lower = 0, higher = 0;
    for (int i = 0; i < numsSize; i++) {
        lower ^= nums[i];
        lower &= KKK;
        higher ^= nums[i];
        higher &= JJJ;
    }
    return lower;
} 

請補完程式碼。

### 解題

我在考試時是靠刪去法猜出正確答案，首先 KKK 不可能是 (d) ~lower (e) 0xFFFFFFFF ，前者運算過後會讓 `lower` 變成 0xffffffff ，沒有實質上的意義；後者運算並不會改變 `lower` 的值。

再來，(b) lower 也不會改變 `lower` 的值。最後，如果選擇 (a) higher 的話，在第一次執行迴圈時會讓 `lower` 歸零，如果 `nums` 裡面只有 1 個數字，最後 `return lower` 會直接回傳 0，也不對。

所以刪到最後 ==KKK== = ~higher，用類似的刪去法推論 ==JJJ== = ~lower

---

為了確實理解程式的邏輯，我參考 [RinHizakura](https://hackmd.io/@RinHizakura/SJ5NuIANP#%E6%B8%AC%E9%A9%97-6) 的思路，使用 `higher` 、 `lower` 儲存每個 bit 的三種狀態，並且讓 1 出現三次後的 `higher` 、 `lower` 歸零。

現在假設 `nums[i]` 、 `higher` 、 `lower` 都只有 **1 bit**，我們希望:

- 初始狀態: `lower` = 0
- 狀態 1: `nums` 中有 3n + 1 個 1 時， `lower` = 1
- 狀態 2: `nums` 中有 3n + 2 個 1 時， `lower` = 0
- 狀態 3: `nums` 中有 3(n+1) 個 1 時， `lower` = 0

只靠 `lower` 無法完全記錄以上三種狀態，這時引入 `higher` 輔助:

- 初始狀態: `lower` = 0, `higher` = 0
- 狀態 1: `nums` 中有 3n + 1 個 1 時， `lower` = 1, `higher` = 0
- 狀態 2: `nums` 中有 3n + 2 個 1 時， `lower` = 0, `higher` = 1
- 狀態 3: `nums` 中有 3(n+1) 個 1 時， `lower` = 0, `higher` = 0

透過 `lower` 和 `higher` 控制三種狀態

畫出真值表:

|lower|higher|input|lower_out|higher_out|
|-----|------|-----|---------|----------|
|0 |0 |0 |0 |0 |
|0 |0 |1 |1 |0 |
|1 |0 |0 |1 |0 |
|1 |0 |1 |0 |1 |
|0 |1 |0 |0 |1 |
|0 |1 |1 |0 |0 |

由上表可以推導:

$$ lower\_out = (lower' \times higher' \times input) + (lower \times higher' \times input') \\
= higher' \times ((lower' \times input) + (lower \times input')) \\
= higher' \times (lower \oplus input)$$

拓展到多位元，即 $lower\_out = \overline{higher} \times (lower \oplus input)$

同理:

$$ higher\_out = (lower \times higher' \times input) + (lower' \times higher \times input')$$

然而這並不利於化簡，所以我們小幅修改了規則:

|lower|higher|input|lower_out|higher_out|
|-----|------|-----|---------|----------|
|0 |0 |0 |0 |0 |
|0 |0 |1 |1 |==1== |
|1 |0 |0 |1 |0 |
|1 |0 |1 |0 |==0== |
|0 |1 |0 |0 |1 |
|0 |1 |1 |0 |0 |

調換此兩個 `higher_out` 數值並不會影響 `lower_out` 的結果，並且利於化簡:

$$ higher\_out = (lower' \times higher' \times input) + (lower' \times higher \times input') \\
= lower' \times ((higher' \times input)+(higher \times input')) \\
= lower' \times (higher \oplus input)$$

拓展到多位元，即 $higher\_out = \overline{lower} \times (higher \oplus input)$