# 2020q3 Homework2 (quiz2)
contributed by < `chwchao` >
> [2020q3 第 2 週測驗題](https://hackmd.io/@sysprog/2020-quiz2)
###### tags: `sysprog2020`
## 測驗一
### 題目解析
```cpp=1
#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;
}
```
標準 ASCII 編碼以一個 byte 儲存空間，並使用 7 個 bits 進行編碼，即 00000000 至 01111111 ，
因此若需判斷一字元是否為標準 ASCII 編碼，可以僅確認 MSB 是否為 0 進行判斷。
如第 18 行，即利用一字元與二進位編碼 10000000 進行 AND 運算，若該字元的 MSB 同樣為 1，AND 運算結果則會同樣是 10000000，若否則是 00000000，並可以此進行 if 判斷。
```cpp=18
if (str[i] & 0x80)
return false;
```
回到題目程式碼，可看到在第 12 行，使用 memcpy 將 8 bytes 儲存至 payload 以一次進行八個字元的比對，因此此處可輕易判斷使用的 mask 應選擇 **`(d)` `0x8080808080808080`** ，對八個字元進行 AND 運算，唯有全數字元的 MSB 皆為 0，即皆為 ASCII 編碼，才可避免判斷為否。
```cpp=11
uint64_t payload;
memcpy(&payload, str + i, 8);
if (payload & MMM)
return false;
```
### Why `memcpy` ?
由於編譯器會根據變數型別，包含其內容長度，決定變數間的運算方式和內容。若直接以 `char` 型別進行 `&` 運算，則只能單次比對 8 個位元的資料。
程式碼中的 `uint_64_t payload` 用途則是以一個 64 位元的載體，一次儲存 8 個字元進行判斷，而此處 `memcpy` 便是用於實作出將字串中連續特定 8 個字元的記憶體內容複製至 `payload` 的儲存空間中。
### 進階使用一
定義一函式，給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母。
實作程式碼 ([is_alpha.c](https://github.com/chwchao/Course-SysProg2020/blob/master/quiz02/is_alpha.c))：
```cpp=1
bool is_alpha(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);
uint64_t A = payload + PACKED_BYTE(128 - 'A');
uint64_t Z = payload + PACKED_BYTE(128 - 'Z' - 1);
uint64_t a = payload + PACKED_BYTE(128 - 'a');
uint64_t z = payload + PACKED_BYTE(128 - 'z' - 1);
uint64_t lower_mask = ((a ^ z) & PACKED_BYTE(0x80));
uint64_t upper_mask = ((A ^ Z) & PACKED_BYTE(0x80));
if ((lower_mask | upper_mask) ^ PACKED_BYTE(0x80))
return false;
i += 8;
}
while (i < size) {
if (str[i] < 'A' || (str[i] > 'Z' && str[i] < 'a') || str[i] > 'z')
return false;
i++;
}
return true;
}
```
此程式碼使用了測驗五中的技巧以判斷一字元是否大小寫字母，詳細解釋可直接參照該題說明。
## 測驗二
### 題目解析
定義一函式，可將輸入的十六進位表示字元 0~9, a~f or A~F，轉換為十進位數值 0~15。
```cpp=1
uint8_t hexchar2val(uint8_t in)
{
const uint8_t letter = in & MASK;
const uint8_t shift = (letter >> AAA) | (letter >> BBB);
return (in + shift) & 0xf;
}
```
並根據題目中引述：
> 以下摘自 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
```cpp=3
const uint8_t letter = in & MASK;
```
首先判斷是否為英文字母，並以一變數 `letter` 儲存。由 ASCII 編碼中可發現，數字的由左第二個位元為 0，而英文為 1。
> '0': 0b00110000
> '9': 0b00111001
> 'A': 0b01000001
> 'F': 0b01000110
> 'a': 0b01100001
> 'f': 0b01100110
因此此處 **MASK 應選擇 `(c)` `0x40`**，
將該位元分離出來，若為數字則為 0b00000000，英文字母則為 0b01000000。
```cpp=4
const uint8_t shift = (letter >> AAA) | (letter >> BBB);
```
同樣由 ASCII 編碼中可以發現，若僅看右四位元，
'0' ~ '9' 可直接對應到數值 0 ~ 9，
'a' ~ 'f' 和 'A' ~ 'F' 則是直接對應到數值 1 ~ 6，而再加 9 即為目標值。
因此此處的 `shift` 變數則是使其若為數字時為 0，英文字母則為 9 作為偏移量，所以
**AAA 選擇 `(a)` `3`**，將字母特有左二的 1 移至右四變為 0b00001000
**BBB 選擇 `(b)` `6`**，將字母特有左二的 1 移至右一變為 0b00000001
再進行 OR 運算變成 0b00001001，即為位移量 9 (若為數字則會是 0b00000000)。
```cpp=5
return (in + shift) & 0xf;
```
最後將輸入字元加上該位移量，並與 `0xf` 做 AND 運算取右四位元，結果即會符合函式需求。
### Hexspeak
將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值。
實作程式碼([hexspeak.c](https://github.com/chwchao/Course-SysProg2020/blob/master/quiz02/hexspeak.c))：
```cpp=1
uint8_t hexchar2val(uint8_t in) {
const uint8_t letter = in & 0x40;
const uint8_t shift = (letter >> 3) | (letter >> 6);
return (in + shift) & 0xf;
}
uint64_t hexspeak(char str[]) {
int len = strlen(str);
assert(len <= 18 && len > 2);
assert(str[0] == '0' && (str[1] == 'x' || str[1] == 'X'));
uint64_t result = 0;
for (int i = len - 1; i >= 2; --i) {
result |= (uint64_t)hexchar2val(str[i]) << ((len - i - 1) << 2);
}
return result;
}
```
首先檢查字串格式，此處限制為 `"0x"` 或 `"0X"` 開頭，且字串長度須大於 2 且不超過 18 (16 個數值字元，上限 64 位元)。
接著將字串由後往前處理，每一字元先利用題目提供 `hexchar2val` 函式轉換為 0~15 的 `uint8_t` 數值，並轉型為 `uint_64` 避免 bitwise 操作超出位元限制。
`(len - i - 1) << 2` 等同 `(len - i - 1) * 4`，目的為將個字元數值移動至其所屬的位置，最右字元須放在最右四位元，右二字元須保留最右四位元為 0，....... 以此類推。
最後再藉由 `|=` 或 `+=` 運算子將其加總，並回傳正確結果。
## 測驗三
### 題目解析
快速除法原理為：
$$
\dfrac{n}{d} = n \times (\dfrac{2^N / d}{2^N})
$$
並以下方程式碼實作：
```cpp=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;
}
```
由第七行的回傳值 `n - quotient * D` 可看出 `quotient` 為此餘除的商，即為 $\dfrac{n}{d}$。
而第六行中對 `M * n` 向右偏移 64 位元，即為除以 $2^{64}$，因此可得知 $N$ 應為 64。因此此處 **XXX 應選擇 `(f)` `0xFFFFFFFFFFFFFFFF`**，即 $2^{64} - 1$
## 測驗四
### 題目解析
```cpp=1
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
由上題，`M * n` 128位元數字中，左 64 位元視為整數部分，右 64 位元則視為小數部分，且此題中並無擴展並向右偏移的動作，因此可知道此處的 `n * M` 為 $\dfrac{n}{d}$ 的小數部分。另外，`M - 1` 應為 $\dfrac{1}{d}$ 的小數部分，且若能整除，不可能會有比其更小小數，因此 **YYY 應選擇 `(c)` `M - 1`**
## 測驗五
### 題目解析
```cpp=1
#include <ctype.h>
#include <stddef.h>
#include <stdint.h>
#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)
/* 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]);
}
}
/* 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);
}
```
#### `strlower`
根據 ASCII 編碼，可以發現大小寫同一英文字母的十進位差為 32，即二進位的 0010 0000。
> 'A' 的二進位編碼為 0100 0001，'a' 則為 0110 0001
> 'Z' 的二進位編碼為 0101 1010，'z' 則為 0111 1010
因此在 `strlower` 函式中，當確認一字元範圍在 A~Z 中，則直接利用 0010 0000 做 XOR 運算，將字元中由右第三位元改為 1，結果即為該英文字母的小寫。而若字元為擴展 ASCII 中的編碼，則使用 C 提供的 `tolower` 函式進行轉換。
#### `strlower_vector`
```cpp=23
uint64_t *chunk = (uint64_t *) s;
```
此處使用類似測驗一中 `payload` 的手法進行實作，並以 `(uint_64_t *)` 的強制轉型取代 `memcpy`，目的上同樣為以 8 個字元的同時比對提升效率。
```cpp=24
if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */
```
接著先以一判斷式辨別該字串是否皆為標準 ASCII 編碼，此處使用測驗一中使用的技巧，和 0x80 進行 AND 運算以辨認 MSB 是否為 0，因此 **`VV1` 應填入 `(e)` `0x80`**
```cpp=27
uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2;
*chunk ^= mask;
```
首先看到此判斷式中的最後一行，可看到最終須對 mask 做 XOR 運算，由 `strlower` 函式中的原理可以知道，此處若一字元為大寫英文字母，`mask` 須為 0b00100000，反之則為 0b00000000。
再由上方行可看到，`mask` 在計算後被右移了兩位，因此可重新調整條件：若一字元為大寫英文字母，`(A ^ Z) & PACKED_BYTE(VV4)` 須為 0b10000000，反之則為 0b00000000。
```cpp=25
uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2);
uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3);
```
此兩變數宣告則是作為該字元是否為大寫英文字母的判斷範圍，
`128 - 'A'` 為字元 'A' 到 0b10000000 的距離，若字元為大寫字母，即 >= 'A'，則應 >= 128
`128 - 'Z'` 為字元 'Z' 到 0b10000000 的距離，若字元為大寫字母，及 <= 'Z'，則應 <= 128
而此處若字元在 A~Z 中，應要使 `A` 和 `Z` 其一小於 128，另一大於等於 128，以在最大位元進行 XOR 運算後為 1。
因此 **VV3 應選擇 `(a)` `-1`**，避免字元為 'Z' 時`Z`等於 128，因為此時 `A` 必須大於 128。
而 **VV2 應選擇 `(b)` `0`**，若為 1，將多判斷 '@' 字元，若為 -1，則無法判斷 'A' 字元。
最後 **VV4 則選擇 `(e)` `0x80`**，用以分離出 MSB。
### char str[] or char *str ?
在修改題目提供程式碼中 `char str[]` 為 `char *str` 後，執行時出現`bus error` 的錯誤。
:::danger
文字訊息不要用圖片去展現！
:notes: jserv
:::
在 ISO/IEC 9899 的第 494 頁的 undefined behavior 列表中有提到
> — The program attempts to modify a string literal (6.4.5)
在 ISO/IEC 9899 的第 130 頁 (6.7.8)
>EXAMPLE 8 The declaration
>
>**char s[] = "abc", t[3] = "abc";**
>
>defines ‘‘plain’’ char array objects s and t whose elements are >initialized with character string literals.
>
>This declaration is identical to
>**char s[] = { 'a', 'b', 'c', '\0' },**
>
>**t[] = { 'a', 'b', 'c' };**
>
>The contents of the arrays are modifiable. On the other hand, the >declaration
>
>**char \*p = "abc";**
>
>defines p with type ‘‘pointer to char’’ and initializes it to point to an object with type ‘‘array of char’’ with length 4 whose elements are initialized with a character string literal. If an attempt is made to use p to modify the contents of the array, the behavior is undefined.
不難看出，在 `char *p = "abc";` 的操作上，`"abc"` 是一系統自動分配且無法修改的 string literal，而 `p` 則僅是儲存此區段的記憶體位置，而非如 `memcpy` 的操作是另外複製內部內容，因此若試圖今天要讓程式修改一 string literal 本身的內容，此一行為屬於 undifined behavior，因此此處才會出現錯誤。
## 測驗六
### 題目解析
>Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
```cpp=1
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;
}
```
#### 討論出現兩次的情況
若提議只要求單一元素最多出現兩次，此時可僅以一變數儲存各 bit 的出現情況，即有 (1) 或無 (0)，因此只需利用簡單 XOR 運算實作即可，範例如下([singleNumber_two.c](https://github.com/chwchao/Course-SysProg2020/blob/master/quiz02/singleNumber_two.c))：
```cpp=1
int singleNumber(int *nums, int numSize) {
int result = 0;
for (int i = 0; i < numSize; ++i)
result ^= nums[i];
return result;
}
```
由以上範例可看出，對於每一位元的出現次數，藉由 XOR 0 會是其本身，並且其本身 XOR 其本身會回歸 0，以此方式去找出最後僅出現一次的位元組合。
#### 討論本題出現三次的情況
由上方討論，我們利用單一位元的 0、1 兩個狀態，來表示出現次數，因此延伸思考，是否當最高次數為三次時，可以用兩個位元來進行表示呢？
因此我們試圖實作以下方式：
* 當尚未出現 (初始狀態)：00
* 出現第一次：01
* 出現第二次：10
* 出現第三次：11，但這時因為已達上限，可將其進行處理回歸為 00
#### 回到題目原始碼
```cpp=3
int lower = 0, higher = 0;
```
在程式碼中可以看到兩個變數 `higher`、`lower`，用於儲存如上方所述兩位元表示的狀態，並且初始值均為 0。
```cpp=5
lower ^= nums[i];
```
當一位元在特定位置出現第一次時，和判斷兩次的方式一樣，用 XOR 將此次數紀錄至 `lower` 低位元。
```cpp=6
lower &= KKK;
```
而回顧我們的目標，
當 `lower` 為 0，會發生在記錄到第二次出現的情況，但此 `&=` 運算子將不會對其造成影響，略過。
當 `lower` 為 1，會發生在第一次和第三次出現，而兩時間點 `higher` 的值會分別是 0 和 1，我們希望當此時 `higher` 已為 1 時，要將 `lower` 歸至 0，可視為以下判斷式：
```cpp
if(higher) lower = 0;
```
因此此處 **KKK 應選擇 `(c)` `~higher`**，當 `higher` 為 1 時，使 `lower` 為 0。
```cpp=7
higher ^= nums[i];
higher &= JJJ;
```
接著看到 `higher` 的處理，注意此處 `lower` 的狀態皆為已處理完畢，並由於是 XOR 運算，現在也只考慮當有 input (某數字出現特定次數) 的情況。
可條列出以下情況：
* 出現第一次： `lower` 為 1，`higher` 原為 0，結果須為 0
* 出現第二次： `lower` 為 0，`higher` 原為 0，結果須為 1
* 出現第三次： `lower` 為 0 (已歸零)，`higher` 原為 1，結果須為 0
在第七行運算完後，則是以下情況 (已假設 `nums[i]` 為 1)：
* 出現第一次： `lower` 為 1，`higher` 為 1，結果須為 0
* 出現第二次： `lower` 為 0，`higher` 為 1，結果須為 1
* 出現第三次： `lower` 為 0，`higher` 為 0，結果須為 0
因此此處 **JJJ 即可選出為 `(d)` `~lower`**，當 `lower` 為 1 時，使 `higher` 為 0。
### 其他解題思路
由於每數最多出現 3 次，且會有一數僅出現 1 次，因此可以推測，若加總判斷特定位元位置上的所有 bit 值，並對 3 餘除，應可僅得到 1 或 0，且正好為該單一數的該位元值，因此可改寫 ([singleNumber_three.c](https://github.com/chwchao/Course-SysProg2020/blob/master/quiz02/singleNumber_three.c))：
```cpp=1
int singleNumber(int *nums, int numSize)
{
int result = 0;
for (int i = 0; i < 32; ++i) {
int sum = 0;
for (int j = 0; j < numSize; ++j)
sum += (nums[j] >> i) & 1;
result += (unsigned)(sum % 3) << i;
}
return result;
}
```
即將一特定 bit 加總後餘除 3，並將其加總至最終結果的正確 bit 上。
以下為在 [LeetCode 137. Single Number II](https://leetcode.com/problems/single-number-ii/) 的執行結果。
### 實作可擴展次數
實作程式碼 ([singleNumber_n.c](https://github.com/chwchao/Course-SysProg2020/blob/master/quiz02/singleNumber_n.c))：
```cpp=1
int singleNumber(int *nums, int numsSize, int time)
{
int result = 0;
for (int i = 0; i < 32; ++i) {
int sum = 0;
for (int j = 0; j < numsSize; ++j)
sum += (nums[j] >> i) & 1;
result += (sum % time) << i;
}
return result;
}
```
若利用上方餘除的方式進行判斷，只需要改變除數即可將限制次數擴展至任意數，因此在函式中再額外新增了一參數作為除數。
:::warning
TODO: 思考避免 modulo 運算的實作
:notes: jserv
:::
Sign in with Wallet
Connect another wallet