# 2020q3 Homework2 (quiz2)
contributed by < `haoyu0970624763` >
## 1. ASCII 編碼判斷
```cpp
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.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 & 0x8080808080808080)
return false;
i += 8;
}
while (i < size) {
if (str[i] & 0x80)
return false;
i++;
}
return true;
}
```
***程式解說***
對於單個字元 1 byte = 8 bits , ASCII碼為0-126
若此字元 和 0x80 做 ＆ 不等於0 則表示他從左邊數過來第二個bit != 0 也就不為ASCII碼
同樣的邏輯推廣到 8 個字元即是答案
:::info
memcpy 的使用不但是用來得到 64 bits 的 payload，memcpy會去檢查記憶體位址是否有
alignment ，可以避免因為對記憶體的 unaligned memory access 產生錯誤。
:::
### 延伸問題二
```cpp=
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)
bool is_alphabet(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 lowerMask = (a ^ z) & PACKED_BYTE(0x80);
uint64_t upperMask = (A ^ Z) & PACKED_BYTE(0x80);
if (( lowerMask | upperMask ) ^ PACKED_BYTE(0x80)){
return false;
}
i += 8;
}
while (i < size) {
if ( (str[i] < 65 || (str[i] > 90 && str[i] < 97) || str[i] > 122))
return false;
i++;
}
return true;
}
```
***程式解說***
一開始想不到要怎麼寫 參考了別人一下也發現看不太懂
:::danger
看不懂就說看不懂，不要說模糊地「不太懂」。如果你認定其他同學的共筆寫不好，那就留訊息指出其不足之處。
再者，你的標點符號呢？
:notes: jserv
:::
但是把全部測驗都解釋整理一次之後 就是把測驗 5 的思考迴路跟解法搬過來這邊解
## 2. 16進位字元轉換
```cpp=
uint8_t hexchar2val(uint8_t in)
{
const uint8_t letter = in & 0x40;
const uint8_t shift = (letter >> 3) | (letter >> 6);
return (in + shift) & 0xf;
}
```
***程式解說***
我們可以觀察回傳值 `(in + shift) & 0xf` 僅要後面四碼而已
而字元`'0'`到`'9'` 的僅取其後四個bit轉換過來即為答案
至於字元`'a'`到`'f'` 的其後四個bit轉換過來為 1-7 只要都再+9 即為對應之答案
我們先用 mask=0x40 如果你是字母（大小寫都可）letter都會等於 0x40 如果是 數字 letter=0x00
而shift則表示 如果你是字母 shift=0x09 數字的話則為0
接著就可求到答案了
## 3.快速除法
```cpp=
const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (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\mod D = n - (n/D) \times D$
也就是說 `n - quotient * D` 的 `quotient` 就是 `n / D` 的整數部份。
從題目裡的提示
$$
\dfrac{n}{d} = n \times (\dfrac{2^N / d}{2^N})
$$
`quotient = ((__uint128_t) M * n) >> 64` 右移 64 bits 即為 $\dfrac{1}{2^N}$，所以 N = 64。
但是 $M＝{(2^{64}/D)}$ 跟 ${(2^{64} - 1) / D} + 1$ 略為不同 參考`Rsysz` 發現兩者算出來的答案是一樣的 所以 `M=0xFFFFFFFFFFFFFFFF`
## 4.倍數判斷
```cpp=
bool divisible(uint32_t n)
{
return n * M <= M-1;
}
```
### 程式原理
延伸上一題的觀念
因為D=3 令 `n=3k,3k+1,3k+2` (k為非負整數)
其中 `3M=0x10000000000000002` 已經overflow 所以會把 3M視為`3M=0x0000000000000002`
所以 case1: $n * M = 3kM = 2k$
case2 : $n * M = 3kM +M = 2k +M$
case3 : $n * M = 3kM +2M = 2k +2M$
所以答案 C,D皆符合
:::info
疑問：有點像是用答案硬推理 不知道為什麼當初會這樣構想程式
:::
:::danger
工程人員說話要精準，避免說「有點像是」，後者是文組^TM^用語
:notes: jserv
:::
## 5. 字串大寫轉換小寫
```cpp
#include <ctype.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)
void strlower(char *s, size_t n);
/* vectorized implementation for in-place strlower */
void strlower_vector(char *s, size_t n);
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);
}
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]);
}
}
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(0x80)) == 0) { /* is ASCII? */
uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + 0);
uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + (-1));
uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80)) >> 2;
*chunk ^= mask;
} else
strlower(s, 8);
}
k = n % 8;
if (k)
strlower(s, k);
}
```
### 程式原理
`PACKED_BYTE(b)` 的作用是取出 `b` 的後 8 個位元(假設是 0x12)，並且變成 0x1212121212121212
接著檢查這個字元是不是 ASCII 編碼 （運用到題一）
如果 `*chunk + PACKED_BYTE(128 - 'A' + 0) >= 128` 表示 chunk的ASCII 編碼大於等於`'A'`
如果 *chunk + PACKED_BYTE(128 - 'Z' -1) < 128表示 chunk的ASCII 編碼小於等於`'Z'`
把 A 跟 Z 做 Xor 如果等於 `10000000` 表示 chunk是介於 `'A'` 到 `'Z'` 之間
則 mask=`00100000`=`' '`
若大寫字母跟`' '` Xor 則會跑出小寫字母
如果chunk不介於`'A'`到 `'Z'` 之間 同時小於128 或是同時大於128
則 mask=`00000000`
任何東西跟`0` Xor 都等於自己
## 6. 單次數尋找
```cpp
int singleNumber(int *nums, int numsSize)
{
int lower = 0, higher = 0;
for (int i = 0; i < numsSize; i++) {
lower ^= nums[i];
lower &= ~higher;
higher ^= nums[i];
higher &= ~lower;
}
return lower;
}
```
### 程式原理
`lower` 是紀錄哪個位置的bit出現數為奇數次 出現奇數次的=1
`higher` 是紀錄哪個位置的bit出現數為偶數次 出現偶數次的=1
**實做邏輯**
lower ^= nums[i] 會先把num[i]的bit 出現奇數次的bit紀錄住
lower &= ~higher 會把已經出現過偶數次的bit扣掉
（當有一個bit出現第三次 lower會紀錄住 但是這個其實是不需要的 會透過上一個迴圈的higher把第三次出現的的消掉 因為我們只要出現一次的bit）
higher ^= nums[i] 會先把num[i]的bit 奇數次的bit的紀錄住
higher &= ~lower 會把已經出現過奇數次的bit扣掉
(當只出現一次 lower會記住 higher也會記住 但會被扣掉 而出現第二次時 lower會消掉
higher會記住 但不會被扣掉 也就是說higher會紀錄出現偶數次的bit)
:::danger
注意筆記書寫規範，中英文字元用一個空白區隔，從小處做起
:notes: jserv
:::
## 新增: 第2題 16進位字串轉換
```c=1
uint64_t HexToDigit(char* in) {
char *tmp_ptr=in;
char *reverse;
uint64_t payload = 0, value = 0;
if (in[0] == '0' && in[1] == 'x')
tmp_ptr=&in[2];
#if __BYTE_ORDER == __BIG_ENDIAN
reverse=tmp_ptr;
#else
memset(reverse,'\0',strlen(tmp_ptr)+1);
for (int i = 0; i < strlen(tmp_ptr); i++)
{
reverse[i]=tmp_ptr[strlen(tmp_ptr)-1-i];
}
#endif
memcpy(&payload, reverse , sizeof(char)*strlen(tmp_ptr));
uint64_t letter = payload & 0x4040404040404040;
uint64_t shift = (letter >> 3) | (letter >> 6);
uint64_t tmp=(payload + shift) & 0x0F0F0F0F0F0F0F0F;
int i=strlen(tmp_ptr);
for( int i=strlen(tmp_ptr); i!=0 ; i--){
value= value << 4;
value |= ((tmp >> (i-1)*8) & 0x0F);
}
return value;
}
```
根據電腦的endian架構去決定input的字串要不要反過來
把 input 的字串反過來是因為 電腦架構還有 uint64_t 的 endian 是不一樣的，會發現這個
是因為我在測試 `0x12` 的時候，答案一直都不是我預期的，反而是 `0x21` 的答案，所以就上
stackoverflow 尋找才發現是 endian 的問題
邏輯:
`strlen(tmp_ptr)` 表示需要轉換的長度
用 `tmp` 存著所有轉換完的 input ，每 8bits 表示一個數字
從轉換完的輸入最左邊 8bits 開始依序到最右邊 8bits ，將 8bits 右移到最右邊8 個 bits 並且跟 value 做 AND 接著再把 value 左移4個bits(因為是16進位)
把第8-15bits 右移到最右邊8 個 bits 並且跟 value 做 AND ....依此類推
`tmp >> (i-1)*8` 控制是哪一組 8bits 右移到最右邊
` ＆ 0x0F` 只需要最右邊 4bits
## 新增: 第3題 快速除法（jemelloc原理）
$n$ 為**被除數**, $q$ 為**商**, $d$ 為**除數**
數學式子從`Rsysz`參考，但是他的 $r=(-2)^k mod \space d$ 應為筆誤或是錯誤
r 表示 $2^k mod \space d$ (也就是餘數)
假設$n = q \times d$，已知 n , d 求 q
$q = n / d$ $=\left \lfloor \left \lceil \dfrac{2^k}{d} \right \rceil \times \dfrac{n}{2^k} \right \rfloor = \left \lfloor \dfrac{2^k + r}{d} \times \dfrac{n}{2^k} \right \rfloor，k為任意整數，而r = -(2)^k mod \space d$
$將\left \lfloor \dfrac{2^k + r}{d} \times \dfrac{n}{2^k} \right \rfloor展開為\left \lfloor \dfrac{2^k}{d} \times \dfrac{n}{2^k} + \dfrac{r}{d} \times \dfrac{n}{2^k}\right \rfloor = \left \lfloor \dfrac{n}{d} + \dfrac{r}{d} \times \dfrac{n}{2^k} \right \rfloor$
$因假設n /d為整除，所以n/d的小數部分為0，因此式子可以化簡為\dfrac{n}{d} + \left \lfloor \dfrac{r}{d} \times \dfrac{n}{2^k} \right \rfloor$
也就是當$\dfrac{r}{d} \times \dfrac{n}{2^k} < 1$，$n/d = \left \lfloor \left \lceil \dfrac{2^k}{d} \right \rceil \times \dfrac{n}{2^k} \right \rfloor$就會成立
因 $r$ 是 $\dfrac{2^k}{d}$ 的餘數，因此 r < d 且 $r/d<1$總是成立，所以只需滿足$\dfrac{n}{2^k} < 1$
又 $n$ 為32bits的數，最大值為 $2^{32}-1$，因此可以令 k = 32(k之最大值)來確保$\dfrac{n}{2^k} < 1$，而這也是為什麼jemalloc bound 數值範圍在 $2^{32}$ 之間。
[code 連結](https://github.com/haoyu0970624763/sysprog21-quiz2/blob/master/quickDiv.c)
div_info->magic = $\left \lceil \dfrac{2^k}{d} \right \rceil$
為何要取上高斯??
用例子說明 ： $12 \times \dfrac{2^3}{6} >> 3$
若是 $\dfrac{2^3}{6}$ 四捨五入或取下高斯 ， 答案皆為1，取上高斯答案則為 6（所以要取上高斯）
理論上最優的算法當然是 $12 \times 2^3 /6 >> 3$ 但程式語言無法做到這件事。
取下高斯或是捨去會有部份值被捨去，會造成相乘出來的結果變小，進而影響結果。
取上高斯或是進位，會造成相乘出來的結果變大，進而影響結果，但後來有右移所以把答案調回來。
## 新增: 快速除法跟一般除法之間的效能比較:
**最一開始的實驗:** 將快速除法跟除法分成兩個執行檔，除數為亂數設定，被除數也是亂數設定。
兩個檔案的亂數種子是設定為一樣的，所以兩個檔案的除數跟被除數都是一樣的，皆進行一億次運算
想像中的結果，quickdiv 應該快於 div 的運算，然而結果卻不一樣。
[div code 連結](https://github.com/haoyu0970624763/sysprog21-quiz2/blob/master/div_test.c)
[quickdiv code 連結](https://github.com/haoyu0970624763/sysprog21-quiz2/blob/master/quickdiv_test.c)
**從上圖可以發現，一般的除法會略快於快速除法**
**為什麼會導致這樣的結果呢?**
* **1. 實驗設計錯誤**
* **2. 在實做上 quickdiv真的慢於div**
* **3. 實驗測資導致的結果**
### 針對實驗設計錯誤的問題，我仿照`RinHizakura`的實驗方式進行實驗
底下的 code 為 `RinHizakura` 的實驗基礎設計
```cpp
static uint64_t MAX = ((uint64_t)(1) << 32) - 1;
int main()
{
struct timespec tt1, tt2;
clock_gettime(CLOCK_MONOTONIC, &tt1);
for (uint64_t i = 2; i < 5000; i++) {
div_info_t DIV;
div_init(&DIV, i);
uint64_t num = rand() % MAX;
clock_gettime(CLOCK_MONOTONIC, &tt1);
size_t ans1 = div_compute(&DIV, num);
clock_gettime(CLOCK_MONOTONIC, &tt2);
long long time1 = (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
(long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);
clock_gettime(CLOCK_MONOTONIC, &tt1);
size_t ans2 = num / i;
clock_gettime(CLOCK_MONOTONIC, &tt2);
long long time2 = (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
(long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);
printf("%ld, %lld, %lld\n", i, time1, time2);
}
}
```
## 改良的第一版測試，測試 多個被除數 除以 單一除數
[test1 code 連結](https://github.com/haoyu0970624763/sysprog21-quiz2/blob/master/TestDiv/test1.c)
下圖為測試結果
可以發現在編譯器沒優化的情況下， quickdiv 明顯快於 div
而經過優化之後發現兩者速度皆減低不少，而根據 `RinHizakura`的實驗發現這是因為編譯器發現
除法的結果是不需要用到的，所以自動把它略過了。
## 改良的第二版測試，測試 多個被除數 除以 多個除數
[test2 code 連結](https://github.com/haoyu0970624763/sysprog21-quiz2/blob/master/TestDiv/test2.c)
因為知道存在編譯器的優化，所以在程式過程中我們把編譯器的優化關掉。
同時為了避免測資的偏頗，設置數個不同的 divisor ，並分別計算兩種不同的除法的時間並取平均值，
quickDiv 暫時不包含 div_init 的執行時間（也就是僅計算除法的部份）。
由上圖可發現 quickdiv 明顯快於 div
## 改良的第三版測試，測試2的小變形
[test3 code 連結](https://github.com/haoyu0970624763/sysprog21-quiz2/blob/master/TestDiv/test3.c)
test2的變形，因為在程式執行過程中，其實不能忽略 div_init 的執行時間
因為他也算在 quickDiv 的部份環節，若是以 test2 為基準，每一層 loop 都找一個新的divisor
也就是每一個quickDiv都包含 div init的時間。
由上圖就可以發現， quickdiv 的時間明顯慢於 div
關於 `RinHizakura` 的實驗筆記的這部份修正，我覺得是不必要的。
```cpp
int main()
{
struct timespec tt1, tt2;
clock_gettime(CLOCK_MONOTONIC, &tt1);
for (uint64_t i = 2; i < 5000; i++) {
div_info_t DIV;
div_init(&DIV, i);
uint64_t num = rand() % 10000;
num *= i;
clock_gettime(CLOCK_MONOTONIC, &tt1);
size_t ans1 = div_compute(&DIV, num);
clock_gettime(CLOCK_MONOTONIC, &tt2);
long long time1 = (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
(long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);
clock_gettime(CLOCK_MONOTONIC, &tt1);
size_t ans2 = num / i;
clock_gettime(CLOCK_MONOTONIC, &tt2);
long long time2 = (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
(long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);
printf("%ld, %lld, %lld, %ld, %ld\n", i, time1, time2, ans1, ans2);
}
}
```
為了符合 div 的假設，因此需讓被除數 n 可以整除 d，才可以得到正確的計算結果
**因為 jemalloc 其實也可以處理非整除的問題，只是要將 debug的那一行註解掉，而且我覺得 div_init 的時間是需要被考慮進去的，所以我在自己的測驗code3有加入 init ， 還有一個地方是他的 divisor 是從 2 加到 4999 ，我覺得要用亂數才比較能符合真實狀況，所以有進行修改。**
:::info
小結論:我們從改良的實驗code可以發現，當遇到一個新的除數，因為要包含div_init的時間，在這個時候，quickdiv會較慢，在除同一個除數的時候 quickdiv 會較快，但這個結論跟我的最開始的實驗有產生矛盾。
:::
### 矛盾解法1.
仔細看 `RinHizakura` 跟我最開始設計的實驗有一個**巨大的差異**，就是他的變數宣告都是
`uint64_t` 而我的是 `int` ，但此題的除法實做應該只須用到 `int` ， quickdiv 是用乘法跟右移 取代掉 32bit除法 ，在過程中的確需要 64bit ，但卻不是全部都需要。
[test4 code 連結](https://github.com/haoyu0970624763/sysprog21-quiz2/blob/master/TestDiv/test4.c)
將test2進行微調，並把變數宣告成int 並且不包含 div_init
可以發現，用 int 型別的確略快於 uint64_t ， 然而卻不足以超越 quickdiv的時間
比對最初的資料跟 test1 ， 1E 筆資料 int 型別大概要0.9秒 而 uint64_t 要1.5秒
### 矛盾解法2.
**重新 review 自己最開始的測試結果，我發現我測試的是整段 code ，而 code 當中還包含rand（）
而 rand() 次數高達一億次，也因為包含這個非除法的部份，會導致自己偵測的時間變得不只包含除法，所以不準確。**
### hint
**在測驗過程中應盡量避免極端值得出現，EX：數字太小 ， 數字太小在 fastdiv 測試 會有異常高的測驗時間值，但我因為測試的資料量較大，所以我認為平均下來應該還好，然而最好還是要撇去極端值存在才能更好得比較效能**
## 新增: 第5題 延伸問題 char str[] 更換為 char *str
結果: `Segmentation fault`
> 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.
string literal 是靜態配置的，也就是 const char *str 嘗試去更動其內容是 undefined behavior
## 新增 4.倍數判斷 解說
```cpp=
bool divisible(uint32_t n)
{
return n * M <= M-1;
}
```
延伸自上一題的觀念
若以 D=3 此題為例子來看:
其中 `3*M=0x10000000000000002` 會產生overflow ，也就是所以大於 3 的數字乘上 M 都會發生overflow ， 3*M 在這裡被視為 `0x0000000000000002` ， 4*M 則代表 2+M...依此類推
而 6*M 則視為 4 ，也就是說 當 3的倍數乘上 M ， 最後的數值 會小於或小於 M （不確定是哪個） 。
但有一點很重要的是， M 是 $\left \lceil \dfrac{2^k}{d} \right \rceil$ （上高斯值），舉個例子說明
EX： 當我們取 k=4 (bit數為4的意思) 而 d=4 ， 則 M = 4 = (0xF/4)+1
取 n=4 ， n*M = 16 （overflow ,修正為 0 < M）
取 n=5 ， n*M = 20 （overflow ,修正為 4 = M）
取 n=6 ， n*M = 24 （overflow ,修正為 8 > M ）
取 n=7 ， n*M = 28 （overflow ,修正為 C > M ）
取 n=8 ， n*M = 32 （overflow ,修正為 0 < M ）
(0xF/4） 實際上只有 3.x 的值 ， 但取上高斯則為 4 ，會導致一個情況是 n * M 造成的overflow 進行修正後的值 = 取上高斯的值，導致 n*M=M ，但是這情況是不整除的。
所以要 -1 修正，把上高斯的值去掉。
## 新增： 6.改寫 singleNumber
這題舉例子說明的話
例1： 1,1,1,3
bit 0 =1 出現 4 次 ， 而 bit1=1 出現 1 次 ， 其餘 bit X=1 出現 0次 ，最後要回一個數字 bit 0,1 = 1
例2 : 1,1,1,3,5,5,5
bit 0 =1 出現 7 次 ， 而 bit1=1 出現 1 次 ， bit2=1 出現 3 次其餘 bit X=1 出現 0次 ，最後要回一個數字 bit 0,1 = 1
從這裡我們可以發現，要去紀錄 bit X 出現 3k+1 次的時候 ( k >= 0 ) ， 出現 3 次的則是不重要
因此我們可以做簡化，紀錄出現 3k+1次的，紀錄出現 3k+2 次的，出現 3k+3 次的
```c=
int singleNumber(int *nums, int numsSize)
{
int apprear1 = 0, apprear2 = 0, apprear3 = 0;
int tmp1=0,tmp2=0,tmp3=0;
for(int i=0;i<numsSize;i++) {
apprear1 = (~(tmp2 | tmp1) & nums[i]) | tmp1 & ~nums[i] | tmp3 & nums[i];
apprear2 = tmp1 & nums[i] | tmp2 & ~nums[i];
apprear3 = tmp2 & nums[i] | apprear3 & ~nums[i];
tmp1 = apprear1;
tmp2 = apprear2;
tmp3 =apprear3;
}
return apprear1;
}
```
apprear 1 紀錄出現 3k+1 次的 ， apprear2 紀錄出現 3k+2 次的 ， apprear 1 紀錄出現 3k+1 次的。
apprea1 要紀錄的有
* 1.沒有出現在 3K+1 次 也沒有出現在 3K+2 次 但是 nums[i] 有的 （因為這些應該被紀錄在 apprear2 跟 apprear3 裡面）
* 2.出現 3K+1次 但在 nums[i] 沒出現的，
* 3.出現在 3K+3 次也有出現在 nums[i]裡面的(因為 3k+4 = 3(k+1) +1 )
apprea2 要紀錄的有
* 2.出現 3K+1次 在 nums[i] 也有出現的，
* 3.出現 3K+2 次 但在 nums[i] 沒出現的
apprea3 要紀錄的有
* 2.出現 3K+2次 在 nums[i] 也有出現的，
* 3.出現 3K+3 次 但在 nums[i] 沒出現的
最後回傳 出現 3K+1 次的即可。
[改寫版 code 連結](https://github.com/haoyu0970624763/sysprog21-quiz2/blob/master/singleNumber.c)
[改寫擴充版 code 連結](https://github.com/haoyu0970624763/sysprog21-quiz2/blob/master/singleNumber_expansion.c)
Sign in with Wallet
Connect another wallet