# 2020q3 Homework2 (quiz2)
contributed by < `OscarShiang` >
## 作業要求
* [ ] 重新回答[第 2 周測驗題](https://hackmd.io/@sysprog/2020-quiz2)，連同附帶的「延伸問題」。
## 測驗一
因為我們的目的是判斷是不是介於 0 ~ 127 的 7 位元 ASCII 的有效字元，因此只需要判斷該字元的 MSB 是否為 1 就可以了，就如同下列的程式碼一樣
```cpp
#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;
}
```
上述的程式碼一次只會判斷一個字元的數值是否介於 128 ~ 255，但是因為我們一次要判斷 8 個字元，所以我們需要把上述程式碼的 bit mask 擴充到 64 個 bit，因此 `MMM` 的答案就會是
> MMM = `0x8080808080808080`
## 測驗二
第二題的部分是要實作一個將十六進位的字元轉換為 int 數值的函式，部分的實作如下：
```c
uint8_t hexchar2val(uint8_t in)
{
const uint8_t letter = in & MASK;
const uint8_t shift = (letter >> AAA) | (letter >> BBB);
return (in + shift) & 0xf;
}
```
### MASK
在本題中 `letter` 的用途是從 bit pattern 的角度判斷該字元是不是一個字母。
根據 ASCII 表格的資料可以得知字母以及數字對應的 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'` 對應的 bit pattern 是 0011_0000，而 `'A'` 對應的 pattern 是 0100_0001，且因為 `'0'` 到 `'9'` 介於十六進位的 `0x30` 到 `0x39`，並不會使用 0==1==00_0000 這個 bit
因為只有 `'a'` ~ `'z'` 與 `'A'` ~ `'Z'` 會有上述的 bit，因此可以透過 AND 運算知道輸入的該字元是否為英文字母。
由此可知該題的 `MASK` 的數值為
> MASK = `0x40`
### AAA
根據 `MASK` 的數值可以知道，如果該字元是英文字母的話， `MASK` 就會是 `0x40` 也就是二進位的 `0100_0000`。
假設我們傳入的字元是 `'a'` 即 `0110_0001` 因為最後經過使用 `0xf`進行 AND 運算之後只會剩下最後的 4 的 bit，所以需要利用 `MASK` 的位移組合出十進位的 `10`，也就是二進位的 `1010`，因此可以推得 `shift` 應該為 `1010`，而 `shift = (letter >> AAA) | (letter >> BBB)` ，所以可以知道 `1010` 是由 `letter >> 3` 與 `letter >> 6` 組成的。
因此 `AAA` 的答案就會是
> AAA = `3`
### BBB
根據上述結果可以知道 `BBB` 就會是
> BBB = `6`
### 延伸問題
:::info
將 `hexchar2val` 擴充為允許 `"0xFF"`, `"0xCAFEBABE"`, `"0x8BADF00D"` 等字串輸入，且輸出對應的十進位數值
:::
因為原始的實作只會計算單一字元對應到的數值，所以我將其改以迴圈的方式重複計算。
需要特別注意的是：因為字串的排列方式是編號較小的字元排在左邊，但是在數值運算的時候較小的位數則擺在右側，所以在使用迴圈讀取的時候應該要留意讀取的方向應該為由字元陣列編號較大者往小。因此可以實作出輸入 `a0` 則回傳 `160` 的實作：
```cpp
uint64_t hexchar2val(uint8_t in[], size_t len)
{
uint64_t result = 0;
uint8_t size = 0;
for (int i = len - 1; i >= 0; i--) {
const uint8_t letter = in[i] & 0x40;
const uint8_t shift = (letter >> 3) | (letter >> 6);
result |= (((uint64_t) in[i] + shift) & 0xf) << size;
size += 4;
}
return result;
}
```
利用 `size` 變數將 `(((uint64_t) in[i] + shift) & 0xf)` 的計算結果推移到對應的位元。
而考慮到輸出是 `"0xf"` 或是 `"0xCAFEBABE"` 等等有 `"0x"` 這樣前綴的字串形式，所以在輸入的時候需要先將字串中 `"0x"` 的部分去除掉才能呼叫 `hexchar2val` 來進行計算
所以在 `main` 函式中，我使用指標搭配迴圈的方式達到略過 `"0x"` 的功能
```cpp
int main(int argc, char *argv[])
{
if (argc < 2) {
printf("Usage: ./hexchar2val [hex]\n");
exit(-1);
}
/* get rid of the prefix "0x" */
char *ptr = argv[1];
while (*ptr && *(ptr++) != 'x')
/* iterate */;
printf("the value is: %lu\n", hexchar2val(ptr, strlen(ptr)));
return 0;
}
```
實際執行的結果如下
```shell
$ ./hexchar2val 0xFF
the value is: 255
$ ./hexchar2val 0xCAFEBABE
the value is: 3405691582
```
完整的程式碼可以參考 [hexchar2val.c](https://gist.github.com/OscarShiang/b31a79164ac700ab65f15c4e7440cf74)
## 測驗三
測驗三是在實作取餘數的運算，因為取餘的過程中首先我們要先計算出對應的商數是多少，我們才能進一步透過商數來算出餘數是多少。
就像是在做 $a \ mod \ b$ 的時候，首先我們需要先計算出 $a \div b$ 的商數也就是 `a / b` 的數值為多少，我們才能透過 `mod = a - b * quotient` 算出 $a \ mod \ b$
而在實作程式碼的部分如下所示，因為若我們要直接做 $\frac{n}{d}$ 的計算時，可能導致 underflow 的狀況，進而導致計算的結果不精準。
```c
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;
}
```
因此在該實作上將計算商數的步驟進行修改
$$
\begin{align}
\frac{n}{d} &= \frac{n}{d} \times \frac{2^N}{2^N} \\
&= n \times \frac{\frac{2^N}{d}}{2^N} \\
&= \frac{n \times \frac{2^N}{d}}{2^N}
\end{align}
$$
先使用一個大數值 $2^N$ 除以 $d$ 再乘以 $n$，最後才除以 $2^N$ 修正回 $\frac{n}{d}$ 的數值。
透過這樣的方式，我們可以保留最多的結果而不會因為 Underflow 而失去精度，因為可以在計算完 $n \times \frac{2^N}{d}$ 之後才捨棄掉多餘的精度，所以能夠讓取商數的計算變得更加精準。
而在該實作中使用的 $N = 64$，因此若根據上述的作法，`XXX` 應該為 $2^{64}$，但因為 `M` 在 macro 的定義裡提到
```c
#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1))
```
根據 [libcdio: types.h File Reference](https://www.gnu.org/software/libcdio/doxygen/types_8h.html) 的說明，可以知道 `UINT64_C` 的實作類似
```c
UINT64_C(c) c ## ULL
```
即利用 macro 產生一個 64 位元的無號整數的 literal。
而 `M` 本身是一個 `uint64_t` 的數值，而在 `uint64_t` 的數值中接近 $2^{64}$ 的數值是 `0xFFFFFFFFFFFFFFFF`，因此 `XXX` 的答案就是
> XXX = `0xFFFFFFFFFFFFFFFF`
## 測驗四
在本題中想要實作的是沿用測驗三中的 `D` 以及 `M` 判斷給定數字是否為 `D` 的倍數。
實作的部分如下
```c
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
根據上一題可以知道 `n * M` 就是 $(n \ mod \ d) \times 2^{64}$ 的數值，因此如果 `n` 是 3 的倍數的話，則 `(n * M) >> 64` 的數值應該是 `0`。所以在放大 $2^{64}$ 倍後若小於 `M - 1` 則表示給定 `n` 是 `D` 也就是 3 的倍數。
因此答案會是
> YYY = `M - 1`
## 測驗五
測驗五的目的在於將 ASCII 字元從大寫轉為小寫，因為在 ASCII 的編碼中，大寫與小寫的差別只有在一個位元的不同而已，像是 `'a'` 對應的 bit pattern 為 01==1==0_0001 ，而 `'A'` 對應到的則是 01==0==0_0001，因此在確定給定的字元是介於 `'A'` ~ `'Z'` 之間後，透過更動前述的位元，就可以達到大寫變小寫的功能。
如同下面的實作
```c
/* 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]);
}
}
```
但在上述的實作中，每次我們都只針對單一字元進行判斷與調整，為了同時進行多個字元的處理，即向量化的操作，因此改成測驗題的實作方式
```c
/* 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);
}
```
### VV1
在這個實作中，我們一次會將 8 的字元轉換為 `uint64_t` 的形式以同時進行轉換，而在轉換為小寫以前，我們需要先確定我們目前要處理的 8 個字元是否皆非 extended ASCII 的話，就會需要透過將這 8 個字元與 `PACKED_BYTE(VV1)` 進行 AND 運算，而在測驗一中我們可以知道因為非 extended ASCII 的數值介於 0 ~ 127 之間，所以若這是一個標準的 ASCII 字元，則在這一個字元中最大的位元一定是 `0`。
而再看到 `PACKED_BYTE` 的定義
```c
#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)
```
若我們在 `PACKED_BYTE` 中給定一字元 `'a'` 即十六進位的 `0x61` 則我們通過 `PACKED_BYTE` 的運算會得到 `0x6161616161616161` 換回 ASCII 字元則是 `'aaaaaaaa'`，因此可以知道 `PACKED_BYTE` 的用途是產生一個 8 個字元都是給定字元 `b` 的字串，與在 Python 中輸入 `'a' * 8` 的結果類似。
而因為我們要檢查這 8 個字元中任意一個字元都必須不是 extended ASCII，所以我們需要透過 `PACKED_BYTE` 產生一個長度為 8 位元組的 bit mask，而因為這個 bit mask 要檢查的是個別位元組中最高位元是否為 0 ，所以答案就會是
> VV1 = `0x80`
### VV2
與測驗一的情況類似，在我們確定其為 ASCII 編碼中介於 0 ~ 127 之間的字元，接著我們需要知道這個字元是不是一個大寫的英文字母。
因此在實作中採用 `A` 與 `Z` 這個變數來幫助我們判斷該字元是否介於 `A` ~ `Z` 之間。
而該實作的原理如下，假設我們單次只處理一個字元，並將給定一字元 `c` 代進程式碼中，則會變成
```cpp
uint8_t A = c + 128 - 'A' + VV2;
```
對應的 `Z` 則為
```cpp
uint8_t Z = c + 128 - 'Z' + VV3;
```
若這個字元介於 ASCII 的 65 ~ 127 之間，也就是 `'A'` ~ `'\127'` 的區間，則 `c - 'A'` 將會大於 0，而導致 `A` 變數最左邊的 bit 為 `1`
同理若給定字元 `c` 介於 91 ~ 127 的區間內，則變數 `Z` 最左邊的 bit 也會為 `1`
而從上述的推論中我們可以知道，為了讓 `c + 128 - 'A' + VV2` 的結果落在 128 ~ 255 的數值區間內，並可以藉此推論 `c >= 'A'` 的結果，因此 `VV2` 的答案就會是
> VV2 = `0`
### VV3
在 `VV3` 中，我們的目的與 `VV2` 類似，就是要判斷給定字元是否落在 91 ~ 127 的區間內，也就是不包含 `'Z'` 這個端點的情況，所以對應的 `VV3` 就會是
> VV3 = `(-1)`
### VV4
從上述的結果我們可以發現：
- 若 `A` 最左邊的 bit 為 `1` 且 `Z` 最左邊的也為 `1` 則表示 `c >= 'A'` 且 `c > 'Z'`，因此可以知道其不是大寫的字母。
- 若 `A` 最左邊的 bit 為 `1` 且 `Z` 最左邊的也為 `0` 則表示 `c >= 'A'` 且 `c <= 'Z'`，則可以知道 `c` 是一個大寫的英文字母。
- 若 `A` 最左邊的 bit 為 `0` 且 `Z` 最左邊的也為 `0` 則表示 `c < 'A'` 且 `c <= 'Z'`，顯示 `c` 並不是一個英文字母。
因此我們可以推論：
- 如果給定字元落在 `'A'` ~ `'Z'` 的區間內，則 `(A ^ Z)` 的結果最左邊的 bit 就會是 ==1==
- 若該字元落在 `'A'` ~ `'Z'` 的區間外，則 `(A ^ Z)` 的結果最左邊的 bit 就會是 ==0==
因為我們只需要最左邊的位元即可，所以使用 AND 運算去除最左邊的位元以外的位元，所以 `VV4` 的答案就會是
> VV4 = `0x80`
則透過將 `(A ^ Z) & 0x80` 的結果向右位移兩個位元，我們就會得到 `0x20` 這個數值，透過將這個 `mask` 與原本的字元進行 XOR 的運算，我們就可以將大寫的字元轉換成小寫了。
### 延伸問題
:::info
將前述測試程式 `main` 函式的 `char str[]` 更換為 `char *str`，會發生什麼事？請參閱 C 語言規格書，說明 `string literal` 的行為
:::
假設當我們宣告一個變數 `str` 如下
```cpp
char str[] = "Hello World";
```
編譯器會計算我們 assign 的字串長度，並在 stack 的區域宣告一個長度為 12 byte 的字元陣列，將 "Hello World" 放到其中。
但是若我們已以下的方式進行宣吿
```cpp
char *str = "Hello World";
```
則等號右邊的字串將被視為 string literal，而不是 char array object ，編譯器會在 heap 中存入 `"Hello World"` 並將該字串以位址的形式存在 `str` 中
在 **Undefined Behaviour** 中有定義：
> The program attempts to modify a string literal (6.4.5).
因此在本題中 `str` 應該以 `char []` 的形式來宣告，而不是 `char *` 的方式，因為這樣在將字元改成小寫的時候會造成 undefined behaviour 的問題產生。
## 測驗六
測驗六的目的在於實作一個可以在線性時間複雜度的情況下，判斷一個只有一個數字出現過兩次，而其他數字皆出現三次的陣列中，只有出現兩次的數字為何
#### 若要找出只有出現過一次的數字
我們可以先思考若我們只需要判斷在一個只有一個數字出現一次，其餘出現兩次的陣列中，只有出現一次的數字是什麼？
若我們使用一個狀態機來記錄數字出現的情況，則情況會如下
- 未出現： `0`
- 出現一次: `1`
則我們可以將一個 integer 視作一個狀態機，因為它可以記錄每次 bit 出現一次或是沒有出現。
而因為 XOR 運算相當於不會產生 carry bit 的加法，所以在只使用一個 bit 的狀況下若有一個位元出現兩次的話，狀態機中所記錄的就會是 `0`，因此可以知道在狀態機讀取所有數字之後，因為只有一個數字只出現一次，所以在狀態機上只會記錄到它的位元，而其他數字因為都出現兩次，因此視同未出現。所以當我們將該狀態機的數值換成 10 進位時就會得到只有出現過一個的數值。
#### 推廣到本題的原理
根據上述的解釋，我們可以知道因為在給定陣列中的數字最多出現 2 次，因此我們可以用 1 個二進位的狀態機來記錄即可（因為只會有 `出現一次` 與 `未出現` 兩種狀態），但在本題中有可能出現 3 種狀態，`出現一次`、`出現二次` 以及 `未出現` 三種狀態，所以我們會需要兩位元的狀態機來記錄這些狀態
則我們的狀態機就會是下表的結構
| input | higher lower | higher' lower' |
| ----- | ------------ | -------------- |
| 1 | 00 | 01 |
| 1 | 01 | 10 |
| 1 | 10 | 00 |
| 0 | 00 | 00 |
| 0 | 01 | 01 |
| 0 | 10 | 10 |
在這樣的前提下，考慮到本題的實作
```cpp
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
為了說明方便，我假設 `lower`, `higher` 與 `nums[i]` 都只有一個位元
若我們輸入的陣列是 `[1, 1, 1]` 時，則對應的 `[higher, lower]` 應該為 `01`, `10` 以及 `00`
我們可以將這些數字代到程式碼中觀察
因為 `nums[i] = 1` ，所以 `lower ^ nums[i]` 就會是 `1`；而在 `lower & KKK` 後，結果應該為 `1` ，所以 `KKK` 有兩種可能： `~higher` 以及 `0xFFFFFFFF`
但考慮到 `lower` 的數值應該要受到 `higher` 的影響，因為若 `higher = 1` 且 `lower = 0` 則根據上述的狀態機，下一個狀態應該為 `higher = 0` 且 `lower = 0` 因此 `KKK` 的數值應該要是
> KKK = `~higher`
### JJJ
而在 `higher ^ nums[i]` 後， `higher` 也變為 `1` ，但是因為經過 `higher & JJJ` 後， `higher` 應該為 `0`，且因為 `lower = 1`，所以 `JJJ` = `~lower`
> JJJ = `~lower`
###### tags: `sysprog2020`
Google Drive
Gist
Clipboard
Sign in with Wallet
