# [2020q3 Homework2 (quiz2)](https://hackmd.io/@sysprog/2020-quiz2)
contributed by < `zhu849` >
## 題目解析
### ASCII table
* 因為下面題目會頻繁使用到,所以放在這裡
![](https://i.imgur.com/OuUdbwP.gif)
### 測驗 `1`
#### 題目
> 目前電腦中用得最廣泛的字元集及其編碼,是美國國家標準局 (ANSI) 制定的 ASCII 碼,被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼,可表示 128 個字元,第 128~255 號為擴展字元 (extended ASCII)。如果我們明確界定 7 位元編碼的字元隸屬於 ASCII,可透過以下函式來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元:
```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;
}
```
```graphviz
digraph structs {
node [shape=record];
rankdir = LR;
{
rank="same";
D[label="{1|0|1|0|0|1|1|1}"];
A[shape=plaintext,fontcolor=black,label = "&"];
E[label="{1|0|0|0|0|0|0|0}"];
}
B[shape=plaintext,fontcolor=black,label = "str[ ]"];
C[shape=plaintext,fontcolor=black,label = "0x80"];
B -> D[style=invisible,dir=none]
C -> E[style=invisible,dir=none]
}
```
> 其中 `str` 是開頭的記憶體地址,`size` 則是要檢驗的範圍。逐一字元比對的效率低,在 64 位元的架構下,我們嘗試一次比對 64 位元的資料 (即 word size),程式碼改寫如下:
```cpp=
#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;
}
```
* line 12:將 `str` 的第 `i` 個位置開始往後數八個位置的資訊搬移到 `payload` 的記憶體空間上
==MMM==
* `(a)` `0x0080008000800080`
```graphviz
digraph structs {
node [shape=record];
rankdir = LR;
A[label="{0|0|0|0|0|0|0|0|1|0|0|0|0|0|0|0|...}"];
B[shape=plaintext,fontcolor=black,label = "0x"];
B->A[style=invisible,dir=none]
}
```
* `(b)` `0x8000800080008000`
```graphviz
digraph structs {
node [shape=record];
rankdir = LR;
A[label="{1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|...}"];
B[shape=plaintext,fontcolor=black,label = "0x"];
B->A[style=invisible,dir=none]
}
```
* `(c)` `0x0808080808080808`
```graphviz
digraph structs {
node [shape=record];
rankdir = LR;
A[label="{0|0|0|0|1|0|0|0|0|0|0|0|1|0|0|0|...}"];
B[shape=plaintext,fontcolor=black,label = "0x"];
B->A[style=invisible,dir=none]
}
```
* ***`(d)` `0x8080808080808080`***
```graphviz
digraph structs {
node [shape=record];
rankdir = LR;
A[label="{1|0|0|0|0|0|0|0|1|0|0|0|0|0|0|0|...}"];
B[shape=plaintext,fontcolor=black,label = "0x"];
B->A[style=invisible,dir=none]
}
```
* `(e)` `0x8888888888888888`
```graphviz
digraph structs {
node [shape=record];
rankdir = LR;
A[label="{1|0|0|0|1|0|0|0|1|0|0|0|1|0|0|0|...}"];
B[shape=plaintext,fontcolor=black,label = "0x"];
B->A[style=invisible,dir=none]
}
```
* `(f)` `0xFFFFFFFFFFFFFFFF`
```graphviz
digraph structs {
node [shape=record];
rankdir = LR;
A[label="{1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|...}"];
B[shape=plaintext,fontcolor=black,label = "0x"];
B->A[style=invisible,dir=none]
}
```
* line 13, 14:為了要檢查從 memcpy 複製到 payload 的內容是有效的 ASCII 字元,每次都檢查 8 個 bits ,即便是已經放到 payload 的內容值也會一併檢查,再參考上面的 `is_ascii()` function,所以選擇 (d)
:::warning
延伸問題: //TODO
1. 解釋上述程式的運作原理,特別是為何用到 memcpy 呢?提示: 與 data alignment 有關,詳閱 C 語言:記憶體管理、對齊及硬體特性
2. 將上述技巧應用於「給予一個已知長度的字串,檢測裡頭是否包含有效的英文大小寫字母」
3. 承 (2),考慮常見的英文標點符號,判斷輸入字串是否為有效的字元集,避免逐一字元比對
>提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令,可加速字串比對,詳見: Schema Validation with Intel® Streaming SIMD Extensions 4
:::
### 測驗 `2`
> 開發解析器 (parser) 時,常會將十六進位表示的字串 (hexadecimal string) 轉為數值,例如 `'0xF'` (大寫 `F` 字元) 和 `'0xf'` (小寫 `f` 字元) 都該轉換為 `15`。考慮以下不需要分支 (branchless) 的實作:
```cpp=
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`
* line 3:將 `in` 和 `MACK` 做 and 運算後指派到 letter。先和 line 7 行為一起做觀察,可以猜測這步得到的 `letter` 可能是某個字元
* line 4:將得到的 `letter` 做 shift 運算,並使用到 or 運算組合成 shift,可以猜測這個步驟是做推移,意即將不論是大小寫輸入統一輸出成小寫
* 因為 line 3 - 5 無法直觀知道在執行什麼動作,這裡我使用帶入法輔助解題
* 考慮用 '0','5','9','a','c','f','A','C',F' 等值當作帶入值
* 題目能夠已知的內容只有 line 5: 將 `in` 跟 `shift` 的結果和 `0x0f` 做&運算,最後得到的值要是字元對應 hexadecimal 的值
* 考慮數字字元不需要做大小寫轉換,所以我們可以先將數字字元和英文字元區分開來再做處理
* 若考慮 `shift` 為 `0x00000000` 則 `'a'` 和 `'A'` 要回傳的值為 `0x0a`
==MASK==
* `(a)` `0x10`
* `(b)` `0x20`
* ***`(c)` `0x40`***
* `(d)` `0x60`
* `(e)` `0x80`
:::danger
文字訊息不要用圖片展現!
:notes: jserv
:::
:::success
已修正用圖表表示
:::
如果選 `(a)`:
| $char_{10}$ | $MASK_{10}$ |$char_2$ | $MASK_2$ | letter |
| -------- | -------- |-------- |-------- |-------- |
| '0' | 0x10 |00110000 |00010000 |00010000 |
| '5' | 0x10 |00110101 |00010000 |00010000 |
| '9' | 0x10 |00111001 |00010000 |00010000 |
| 'a' | 0x10 |01100001 |00010000 |00000000 |
| 'c' | 0x10 |01100011 |00010000 |00000000 |
| 'f' | 0x10 |01100110 |00010000 |00000000 |
| 'A' | 0x10 |01000001 |00010000 |00000000 |
| 'C' | 0x10 |01000011 |00010000 |00000000 |
| 'F' | 0x10 |01000110 |00010000 |00000000 |
* 可以發現位元為數字的 result 皆為 `00010000`,其他英文字元不論大小寫皆為 `00000000`
* 選擇這個選項可以讓我們區分數字和英文字元
如果選 `(b)`:
| $char_{10}$ | $MASK_{10}$ |$char_2$ | $MASK_2$ | letter |
| -------- | -------- |-------- |-------- |-------- |
| '0' | 0x20 |00110000 |00100000 |00100000 |
| '5' | 0x20 |00110101 |00100000 |00100000 |
| '9' | 0x20 |00111001 |00100000 |00100000 |
| 'a' | 0x20 |01100001 |00100000 |00100000 |
| 'c' | 0x20 |01100011 |00100000 |00100000 |
| 'f' | 0x20 |01100110 |00100000 |00100000 |
| 'A' | 0x20 |01000001 |00100000 |00000000 |
| 'C' | 0x20 |01000011 |00100000 |00000000 |
| 'F' | 0x20 |01000110 |00100000 |00000000 |
* 可以發現大寫英文字元 result 皆為 `00000000`,其他字元輸出皆為 `00100000`
* 選擇這個選項可以讓我們區分大寫英文字元和其他字元
如果選 `(c)`:
| $char_{10}$ | $MASK_{10}$ |$char_2$ | $MASK_2$ | letter |
| -------- | -------- |-------- |-------- |-------- |
| '0' | 0x40 |00110000 |01000000 |00000000 |
| '5' | 0x40 |00110101 |01000000 |00000000 |
| '9' | 0x40 |00111001 |01000000 |00000000 |
| 'a' | 0x40 |01100001 |01000000 |01000000 |
| 'c' | 0x40 |01100011 |01000000 |01000000 |
| 'f' | 0x40 |01100110 |01000000 |01000000 |
| 'A' | 0x40 |01000001 |01000000 |01000000 |
| 'C' | 0x40 |01000011 |01000000 |01000000 |
| 'F' | 0x40 |01000110 |01000000 |01000000 |
* 可以發現位元為數字的 result 皆為 `00000000`,其他英文字元不論大小寫皆為 `01000000`
* 選擇這個選項可以讓我們區分數字和英文字元
如果選 `(d)`:
| $char_{10}$ | $MASK_{10}$ |$char_2$ | $MASK_2$ | letter |
| -------- | -------- |-------- |-------- |-------- |
| '0' | 0x60 |00110000 |01100000 |00100000 |
| '5' | 0x60 |00110101 |01100000 |00100000 |
| '9' | 0x60 |00111001 |01100000 |00100000 |
| 'a' | 0x60 |01100001 |01100000 |01100000 |
| 'c' | 0x60 |01100011 |01100000 |01100000 |
| 'f' | 0x60 |01100110 |01100000 |01100000 |
| 'A' | 0x60 |01000001 |01100000 |01000000 |
| 'C' | 0x60 |01000011 |01100000 |01000000 |
| 'F' | 0x60 |01000110 |01100000 |01000000 |
* 可以發現位元為數字的 result 皆為 `00100000`,其他英文小寫字元皆為 `01100000`,英文大學字元皆為 `01000000`
* 選擇這個選項可以讓我們區分數字和大寫英文字元及小寫英文字元
如果選 `(e)`:
| $char_{10}$ | $MASK_{10}$ |$char_2$ | $MASK_2$ | letter |
| -------- | -------- |-------- |-------- |-------- |
| '0' | 0x80 |00110000 |10000000 |00000000 |
| '5' | 0x80 |00110101 |10000000 |00000000 |
| '9' | 0x80 |00111001 |10000000 |00000000 |
| 'a' | 0x80 |01100001 |10000000 |00000000 |
| 'c' | 0x80 |01100011 |10000000 |00000000 |
| 'f' | 0x80 |01100110 |10000000 |00000000 |
| 'A' | 0x80 |01000001 |10000000 |00000000 |
| 'C' | 0x80 |01000011 |10000000 |00000000 |
| 'F' | 0x80 |01000110 |10000000 |00000000 |
* 可以發現所有的 result 皆為 `00000000`
* 選擇這個選項無法讓我們有效辨別字元關係,所以刪去
* 綜合上述分析,為了要區分數字字元和字母字元我們可能的選擇是 `(a)`, `(c)`,但是如果選擇 `(a)` 得到的 letter 會為 `00000000` 在 line 4 的時候無法做有意義的操作(結果會皆為`00000000`),所以這裡選 `(c)`
==AAA==
* `(a)` `3`
* `(b)` `2`
* `(c)` `1`
* `(d)` `0`
==BBB==
* `(a)` `7`
* `(b)` `6`
* `(c)` `5`
* `(d)` `4`
* 已知得到的 `letter` 數字字元會為 `00000000`,英文字元會為 `01000000`,且數字字元在 line 4,5 可以得到正確的值(因為 shift = `00000000`,相當於用 `in` 直接和 `0x0f` 做 &運算),所以以下只考慮大小寫的 `shift` 運算
* 觀察 line 5 可以發現若將 `'a'` 當作 `in` 預期回傳值是 `'0x0a'`,可以推得 `shift` 值要為 `0x00001001` 才能得到正確結果
* 則 `AAA` 的答案選擇 `(a)`, `BBB` 的答案選擇 `(b)` 可以使 `shift` 得到正確的值 `0x00001001`
:::warning
延伸問題://TODO
1. 解釋上述程式的運作原理;
2. 將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入,且輸出對應的十進位數值
>Hexspeak
:::
### 測驗 `3`
> 除法運算的成本往往高於加法和乘法,於是改進的策略被引入。其中一種策略是將除法改為乘法運算,例如 $\dfrac{n}{d}$ 在分子和分母分別乘上 $2^N$ 後,得到等價的 $n$ x $\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 × \dfrac{\dfrac{2^N}{d}}{2^N}$
,當我們想將 n 除以 4 時,就相當於乘以 0.25,所以我們可將 $\dfrac{5}{4}$ 改為 5×0.25,我們得到整數的部分 (即 1),和小數部分 (即 0.25),後者乘以 4 就是 1,也就是餘數。下方程式碼展示這概念:
```cpp=
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 位元的無號數值。
> 預期 `quickmod(5)` 會得到 `2`, `quickmod(55)` 得到 `1`, `quickmod(555)` 得到 `0` (`555` 是 3 的倍數)。
==XXX==
* `(a)` `0x00F000F000F00080`
* `(b)` `0xF000F000F000F000`
* `(c)` `0x0F0F0F0F0F0F0F0F`
* `(d)` `0xF0F0F0F0F0F0F0F0`
* `(e)` `0x8888888888888888`
* `(f)` `0xFFFFFFFFFFFFFFFF`
> [Macros for Integer Constant Expressions](https://pubs.opengroup.org/onlinepubs/009695399/basedefs/stdint.h.html)
The following macros expand to integer constant expressions suitable for initializing objects that have integer types corresponding to types defined in the <stdint.h> header. Each macro name corresponds to a similar type name listed under Minimum-width integer types and Greatest-width integer types.
...
The macro INTN_C( value) shall expand to an integer constant expression corresponding to the type int_least N _t. The macro UINTN_C( value) shall expand to an integer constant expression corresponding to the type uint_least N _t. For example, if uint_least64_t is a name for the type unsigned long long, then UINT64_C(0x123) might expand to the integer constant 0x123ULL.
* 首先針對 `UINT64_C` 這個 macro 釐清,在不同平台或是不同編譯器的使用會使輸入值擴增至適合的長度
:::danger
//TODO
define那行為什麼要 +1 ??? 我需要補充其他知識或參考他人共筆才能回答這題
:::
### 測驗 `4`
:::danger
承上題
:::
### 測驗 `5`
> 考慮 `strlower` 函式的作用是將指定的字串 (或部分字串) 的英文字母全改為小寫,其 in-place 的實作如下:
```cpp=
#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,需要留意到在不同的語系 (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,程式碼列表如下:
```cpp=
#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);
}
```
> 對應的測試程式碼如下:
```cpp=
#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)` 的函數定義是取出輸入 `b` 的後 8 bits,之後再乘型態為 unsigned 的 `0x0101010101010101`,會得到重複循環的 8bit 字節
```graphviz
digraph structs {
node [shape=record];
rankdir = LR;
E[label="{1|0|0|0|1|1|0|0|1|0|0|0|1|1|0|0|...|1|0|0|0|1|1|0|0|...}"]
F[shape=plaintext,fontcolor=black,label = "結果"];
F->E[style=invisible,dir=none]
C[label="{1|0|0|0|1|1|0|0}"]
D[shape=plaintext,fontcolor=black,label = "字節"];
D->C[style=invisible,dir=none]
A[label="{1|0|0|0|0|0|...|1|0|0|0|1|1|0|0}"];
B[shape=plaintext,fontcolor=black,label = "b"];
B->A[style=invisible,dir=none]
}
```
==VV1==
* `(a)` `0x10`
* `(b)` `0x20`
* `(c)` `0x40`
* `(d)` `0x60`
* `(e)` ***`0x80`***
* 由註解搭配 `PACKED_BYTE(b)` 得知 line 13 是要去判斷輸入進來的 8個 bit 所產生的值是否為有效的 ASCII,又已知 ASCII 如果超過 128 就不會是有效字元。所以我們可以選用 `0x80` 來做 mask ,如果結果為1則 if 為 false,否則 if 為 true
==VV4==
* `(a)` `0x10`
* `(b)` `0x20`
* `(c)` `0x40`
* `(d)` `0x60`
* `(e)` **`0x80`**
* 由 variable `A` 和 `Z` 無法了解要做什麼事情,所以先觀察 line 17 的行為,發現很熟悉的 `^` 操作,聯想到課堂上的 `'A' ^ ' ' = 'a'`,代表 line 17 所做的行為就是將大寫轉成小寫
* 再觀察 line 16,`(A ^ Z) ` 的結果要和 `PACKED_BYTE(VV4)` 做 `&` 操作且結果的值要再做 right shift 2位
* 考慮要將 'A' 轉成 'a', 'Z' 轉成 'z', 'M' 轉成 'm',不難發現大小寫差別在於左邊數來第三個位元,結合 line 16 需要做 right shift 2位,可以得知答案為 `(e) 0x80` = 0x$10000000$ , right shift 2 bit 後為 0x $00100000$ ,在交給 line 17做處理
| char | Binary expression |
| -------- | -------- |
| 'A' | 01**0**0 0001 |
| 'a' | 01**1**0 0001 |
| 'M' | 01**0**0 1101 |
| 'm' | 01**1**0 1101 |
| 'Z' | 01**0**1 1010 |
| 'z' | 01**1**1 1010 |
* 但 line 13 的 if 判斷式,大小寫 ASCII 有效字元都能為 true,所以可以推斷 line 14, 15 是用來區分輸入字元是否為大寫字元
==VV2==
* `(a)` `(-1)`
* `(b)` ***`0`***
* `(c)` `1`
* 由 line 16 判斷得知,`(A^Z)` 要跟 `0x80` 做 `&`運算,所以我們只會在乎最左邊的 bit 是否為 1
* `A` 的目的是為了要判斷 `*chunk` 內容是否會大於 'A',所以`PACKED_BYTE(128 - 'A' + VV2) = PACKED_BYTE(63 + VV2)` 的值為 `63 + VV2` 只要加上任何大於等於 65 的值會使最左邊的 bit 為 1,所以`VV2`不需要做任何調整,答案為 (b) 0
* `Z` 的目的是為了要判斷 `*chunk` 內容是否會大於 'Z',所以`PACKED_BYTE(128 - 'Z' + VV3) = PACKED_BYTE(38 + VV3)` 的值為`38 + VV3` 只要加上任何大於等於 90 的值會使最左邊的 bit 為 1,但是等於90時對應到 'Z' ,所以`VV3`應該要為 (a) -1,這樣才會讓任何大於 90的值都會使最左邊的 bit 為 1
==VV3==
* `(a)` ***`(-1)`***
* `(b)` `0`
* `(c)` `1`
:::warning
延伸問題://TODO
1. 解釋上述程式的原理;
2. 將前述測試程式 main 函式的 char str[] 更換為 char *str,會發生什麼事?請參閱 C 語言規格書,說明 string literal 的行為
:::
### 測驗 `6`
> LeetCode 137. 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 的題解:
```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;
}
```
* 已知 `^` 和 `&` 運算的順序有差,不可利用結合律
* 隨便舉個反例:假設 `A = 010110` , `B = 101011` ,`C = 100001` 則 `(A ^ B) & C = 100001`,而 `A ^ (B & C) = 110111`
* 已知利用 `A^B` 運算的結果再和 `A` 進行一次 `^` 運算會的到 `B`
* 意即 `(A^B)^B=A`,`(A^B)^A=B`
* 先思考幾個點:
* 為什麼需要有 `lower` 和 `higher` 兩個變數?
* 為什麼 `lower` 和 `higher` 的運算邏輯相同?
* 既然要求的數是僅出現一次,其餘都出現三次,那勢必相同三個數輸入程式後結果會為 `0`
* 假設程式僅執行3次迴圈 ,且將迴圈攤開來觀察
* 將 `num[3] = {010110, 010110, 010110}` 當作例子帶入
* 思考以下程式:
```cpp=
//first time
lower ^= nums[0];
lower &= KKK;
higher ^= nums[0];
higher &= JJJ;
//second times
lower ^= nums[1];
lower &= KKK;
higher ^= nums[1];
higher &= JJJ;
//third time
lower ^= nums[2];
lower &= KKK;
higher ^= nums[2];
higher &= JJJ;
...
```
老實說看不出什麼規則,但可以知道的是經過這一連串的運算後 `lower` 的值必為 0,幫助下面的想出下面的狀態機。
* 假設 `lower` 和 `higher` 會是兩個集合,我們知道任一數在 `lower` 經過兩次`^` 操作會得到 0,想像 `lower` 是一個 buffer 且具有以下特性
* 用來存放出現到目前為止只出現一次的數值集合
* 若有相同的第二個數字出現,經過 `^` 操作可以將數字從這個集合消除
* 那我們可推測 `higher` 為另外一個集合,目的是存放到目前為止恰出現兩次的數值集合。那在 `higher` 中再對同一個數字做一次 `^` 則可以將數字從 `higher` 這個群消除,這樣就可以處理數字洽出現三次的情形
* 經過上面的討論,我們還有一個問題:雖然我們得到了一點點蛛絲馬跡,但是如何保證加入 `higher` 這個數字不會影響 `lower` 集合?
* 這就是 `&` 操作所達到的功能,我們加入數字到 `lower` 集合後要確認它不存在於 `higher` 集合內(反之, `higher` 內也要確認該數不在 `lower` 內),所以在 `lower` 做完 `^` 運算後利用 `letter = letter & ~higher` 去排除已經存在於 `higher` 內的數值
* 所以 `lower` 和 `higher` 是兩個功能類似的集合,且一個數只能出現在其中一個集合內
| state num| state name | 說明 |狀態改變條件|
| -------- | -------- | -------- | -------- |
| 10 | higher | 存放輸入目前為止的洽出現兩次的數值集合| 若有一個數在 `higher` 集合內,且不在 `lower` 集合內,做完該輪運算後,該數會在 `higher` 集合被消除,並將該數移動到狀態 `11` |
| 01 | lower | 存放輸入到目前為止的僅出現一次的數值集合| 若有一個數在 `lower` 集合內,且不在 `higher` 集合內,做完該輪運算後,該數會在 `lower` 集合被消除,並將該數移動到狀態 `10` |
| 11 | initial | 數值未出現或恰好出現三次的數值集合| 當有新的數加入,判斷該數是否存在 `lower` 和 `higher`的集合,若都不存在則將該數移動到 `lower`,若存在則優先執行狀態 `10` 或 `01` |
```graphviz
digraph structs {
node [shape=record];
rankdir = LR;
A[label="lower"];
B[label="higher"];
C[label="initial"];
C->A->B->C
A->A[label="nothing"]
B->B[label="nothing"]
}
```
* 由以上說明解釋了 line 6 做的是「將數加入 `lower` 集合後,判斷 `higher` 中內是否已存在該值」,若存在則需要將 `lower` 內的該數消除掉
* line8 同理,僅是 `lower` 和 `higher` 角色對調
* 先前我們將 `higher` 想成一個集合,那`~higher` 的選項可以解釋成不在集合內的其他元素,若用 `~higher` 和 `lower` 做 `&` 運算的意義就是:判斷 `lower` 集合內和**非** `higher` 集合內的交集,這麼做自然可以將已存在 `higher` 內的數消除
* 反之 line 8 同理,僅是 `lower` 和 `higher` 角色對調
==KKK==
* `(a)` `higher`
* `(b)` `lower`
* ***`(c)` `~higher`***
* `(d)` `~lower`
* `(e)` `0xFFFFFFFF`
==JJJ==
* `(a)` `higher`
* `(b)` `lower`
* `(c)` `~higher`
* ***`(d)` `~lower`***
* `(e)` `0xFFFFFFFF`
:::warning
延伸問題://TODO
1. 解釋上述程式的原理;
2. 請撰寫不同上述的程式碼,並確保在 LeetCode 137. Single Number II 執行結果正確且不超時;
3. 延伸題意,將重複 3 次改為改為重複 4 次或 5 次,並找出可容易推廣到多次的程式碼;
:::