2020q3 Homework2 (quiz2)

# 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) ![](https://i.imgur.com/7PvxtuN.png) **從上圖可以發現，一般的除法會略快於快速除法** **為什麼會導致這樣的結果呢?** * **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) 下圖為測試結果 ![](https://i.imgur.com/pZLWvGB.png) 可以發現在編譯器沒優化的情況下， quickdiv 明顯快於 div 而經過優化之後發現兩者速度皆減低不少，而根據 `RinHizakura`的實驗發現這是因為編譯器發現除法的結果是不需要用到的，所以自動把它略過了。 ## 改良的第二版測試，測試多個被除數除以多個除數 [test2 code 連結](https://github.com/haoyu0970624763/sysprog21-quiz2/blob/master/TestDiv/test2.c) 因為知道存在編譯器的優化，所以在程式過程中我們把編譯器的優化關掉。同時為了避免測資的偏頗，設置數個不同的 divisor ，並分別計算兩種不同的除法的時間並取平均值， quickDiv 暫時不包含 div_init 的執行時間（也就是僅計算除法的部份）。 ![](https://i.imgur.com/ah7pZjC.png) 由上圖可發現 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的時間。 ![](https://i.imgur.com/57dZeZQ.png) 由上圖就可以發現， 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 ![](https://i.imgur.com/9gj0J5U.png) 可以發現，用 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)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.