2020q3 Homework2 (quiz2)

--- tags: 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統 --- # 2020q3 Homework2 (quiz2) contributed by <`RusselCK` > ###### tags: `RusselCK` - ==[數值系統＆ Bitwise 練習題](https://hackmd.io/@sysprog/2020-quiz2)== - [作業繳交區](https://hackmd.io/@sysprog/2020-homework2) ## Q1.判斷指定的記憶體範圍內是否全是有效的 [ASCII](https://zh.wikipedia.org/wiki/ASCII) 字元 * 目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (ANSI) 制定的 ASCII 碼，被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended 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; } ``` 其中 `str` 是開頭的記憶體地址， `size` 則是要檢驗的範圍。 * 二進位表示 0~127 為 `0000 0000`~`0111 1111` ，也就是說只要第 8 個 bit 為 1 ，該欄位便不為有效的 ASCII 字元 * 因此，我們可以利用 bitwise 操作（ i.e. `if (str[i] & 0x80)` ），判別第 8 個 bit 是否為 0 > 1個 `char` 的大小 = 1 bytes = 8 bits > 0x80 = (1000 0000)~2~ #### 在 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) { // Check size if (size == 0) return false; int i = 0; while ((i + 8) <= size) { uint64_t payload; memcpy(&payload, str + i, 8); if (payload & MMM) // MMM = 0x8080808080808080 return false; i += 8; } while (i < size) { if (str[i] & 0x80) return false; i++; } return true; } ``` :::info * **`size_t`** * Unsigned integral type * **`uint64_t`** * **unsigned integer type** with width of exactly 64 * **`void * memcpy ( void * destination, const void * source, size_t num );`** * Copy block of memory * Copies the values of `num` bytes from the location pointed to by `source` directly to the memory block pointed to by `destination`. * Source : http://www.cplusplus.com/ ::: * 程式碼解析： ```c int i = 0; while ((i + 8) <= size) { uint64_t payload; memcpy(&payload, str + i, 8); if (payload & MMM) return false; i += 8; } ``` > 64 bits = 8 bytes * 每一次迴圈檢查 8 bytes ，`memcpy(&payload, str + i, 8);` 將起始位址 `str + i` 後的 8 個 bytes 複製到 `payload` ，再由 `if (payload & MMM)` 判斷這 8 個bytes 的每一個 bytes 是否都為有效 ASCII 字元 * 檢查一個 byte 可以用 `& 0x80` 來檢查，推理可得，要一次檢查 8 個 bytes ，可以用 `& 0x8080808080808080` 來檢查 * 因此， **MMM = `0x8080808080808080`** ```c while (i < size) { if (str[i] & 0x80) return false; i++; } ``` * 若 `size` 不為 8 的倍數，前面一個迴圈跳出來後，會剩餘 1~7 個 bytes 沒檢查到 * 這裡使用傳統方式，一次檢查 1 個 byte ## Q1. 進階題 #### 給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母 * 只要檢測到英文字母，便可`return true` ```c= #include <stdbool.h> #include <stddef.h> #include <stdint.h> #include <string.h> #include <ctype.h> #define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u) bool has_alpha(char *s, size_t size) { if (size == 0) return false; for (size_t j = 0; j < size; j++) { if ((s[j] >= 'A' && s[j] <= 'Z') || (s[j] >= 'a' && s[j] <= 'z')) return true; } return false; } bool has_alpha_vector(char *s, size_t size) { if (size == 0) return false; size_t i = 0; while ( (i + 8) <= size){ uint64_t *payload = (uint64_t *) s; if ((*payload & PACKED_BYTE(0x80)) == 0) { /* case1 : is ASCII */ // Upper mask uint64_t A = *payload + PACKED_BYTE(128 - 'A'); uint64_t Z = *payload + PACKED_BYTE(127 - 'Z'); uint64_t upper_mask = ((A ^ Z) & PACKED_BYTE(0x80)); // Lower mask uint64_t a = *payload + PACKED_BYTE(128 - 'a'); uint64_t z = *payload + PACKED_BYTE(127 - 'z'); uint64_t lower_mask = ((A ^ Z) & PACKED_BYTE(0x80)); if ( (upper_mask | lower_mask) & PACKED_BYTE(0x80) ) return true; }else{ /* case 2 */ if (has_alpha(s, 8)) return true; } i += 8; s += 8; } i = size % 8; if (i){ /* case 3 */ if (has_alpha(s, 8)) return true; } return false; } ``` * 此題的運用的技巧及分 case 的方式與 Q5. 類似 ```c #27 while ( (i + 8) <= size) ``` * 若最後一組不滿 8 個，則不可進入迴圈，要改使用 case 3 ```c #37 uint64_t upper_mask = ((A ^ Z) & PACKED_BYTE(0x80)); ``` * 這裡的 mask與 Q5. 不同，是因為不需要改變更動 bits，只須辨別是否為字母即可，因此不需要 `>>2` * 若該 byte 為字母，則相對應的 mask 的 byte 為 0x80 #### 承上，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對 >提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令，可加速字串比對，詳見: [Schema Validation with Intel® Streaming SIMD Extensions 4](https://software.intel.com/content/www/us/en/develop/articles/schema-validation-with-intel-streaming-simd-extensions-4-intel-sse4.html) ## Q2. 將十六進位表示的字串 (hexadecimal string) 轉為數值 #### 不需要分支 (branchless) 的實作: 已知 `in` 一定隸屬於 '0', '1', '2', …, '9' 及 'a', 'b', 'c', …, 'f' (小寫) 及 'A', 'B', 'C', …, 'F' (大寫) 這些字元。 ```c= uint8_t hexchar2val(uint8_t in) { const uint8_t letter = in & MASK; // MASK = 0x40 const uint8_t shift = (letter >> AAA) | (letter >> BBB); //AAA = 3 、 BBB = 6 return (in + shift) & 0xf; } ``` > 預期 hexchar2val('F') 和 hexchar2val('f') 回傳 15 = (1111)~2~ > 並且 hexchar2val('0') 回傳 0 = (0000)~2~ > 其他輸入都有對應的數值。 * 程式碼解析： 1. 考慮以下表格： | Character | Hexdecimal | Binary | |:---------:| ---------- | ------------- | | F | 0x46 | 0==1==00 0110 | | f | 0x66 | 0==1==10 0110 | | 0 | 0x30 | 0==0==11 0000 | * 我們可以發現，光==看第 7 個 bit ，就能夠區分 `in` 是字母或是數字== * 我們可以利用 `in & (0100 0000)` ( i.e. `in & 0x40` ) 來達到此效果 * 若 `in` 為數字，則 `letter` 為 0x00 = (0000 0000)~2~ * 若 `in` 為字母，則 `letter` 為 0x40 = (0100 0000)~2~ * 因此， **MASK = 0x40** 2. 考慮回傳值 `(in + shift) & 0xf` ： > 0xf = (0000 1111)~2~ * 若 `in` 為 F ， ( f 也可推得相同結果） * `(in + shift) & 0xf` = 15 * ( (0100 0110) + `shift` ) & (0000 1111) = (0000 1111) * ( (0100 0110) + `shift` ) = (**** 1111) * `shift` = (**** 1001) * 若 `in` 為 0 ， * `(in + shift) & 0xf` = 0 * ( (0011 0000) + `shift` ) & (0000 1111) = (0000 0000) * ( (0011 0000) + `shift` ) = (**** 0000) * `shift` = (**** 0000) 3. 考慮 `shift = (letter >> AAA) | (letter >> BBB)` : * 若 `in` 為字母，則 `letter` 為 (0100 0000) * 我們可以湊出 AAA = 3 、 BBB = 6 使得答案成立 ( i.e. `shift` = (**** 1001) ) * `(letter >> AAA)` = `(letter >> 3)` = (0000 1000) * `(letter >> BBB)` = `(letter >> 6)` = (0000 0001) * 若 `in` 為字母、AAA = 3 、 BBB = 6，則 `letter` 為 (0000 0000) * `(letter >> AAA)` = `(letter >> 3)` = (0000 0000) * `(letter >> BBB)` = `(letter >> 6)` = (0000 0000) * 可得 `shift` = (**** 0000) * 因此，**AAA = 3** 、 **BBB = 6** ## Q2. 進階題 #### 將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值 >[Hexspeak](https://en.wikipedia.org/wiki/Hexspeak) ```c= #include <ctype.h> #include <stddef.h> #include <stdint.h> #include <stdio.h> #include <string.h> #include <assert.h> #define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u) uint8_t hexchar2val(uint8_t in) { const uint8_t letter = in & 0x40; const uint8_t shift = (letter >> 3) | (letter >> 6); return (in + shift) & 0xf; } size_t hexspeak2val(char str[]){ int len = strlen(str); assert(len); if (len == 1) /* case 1 */ return hexchar2val(str[0]); assert(str[0] == '0' && (str[1] == 'x' || str[1] == 'X')); size_t total = 0; size_t i = 2; /* case 2 */ for (; (i + 8) <= len ; i += 8) { uint64_t payload; memcpy(&payload, str + i, 8); //printf("%lx\n", payload); const uint64_t letter = payload & PACKED_BYTE(0x40); const uint64_t shift = (letter >> 3) | (letter >> 6); const uint64_t value = (payload + shift) & PACKED_BYTE(0x0f); //printf("%lx\n", value); //total = total << 64 ; #if __BYTE_ORDER == __LITTLE_ENDIAN for (size_t j = 0; j < 64 ; j += 8) total += (( value << j ) >> 56) << (j >> 1); #else for (size_t j = 0; j < 64 ; j += 8) total += (( value << j ) >> 56) << ((56 - j) >> 3); #endif //printf("%lx\n",total); } //printf("%lx\n",total); for (; i < len ; i++) /* case 3 */ total = total << 4 | hexchar2val(str[i])); //printf("%lx\n",total); return total; } ``` :::warning * 當加總 `total` 超過 2^64 - 1 時，會造成 Overflow * 如果可以解決 Overflow ，加上 `#42 total = total << 64 ;` ，則可以在更長串的 hexspeak 上執行 * 目前正在尋找更有效率完成 `#44#45`、`#47#48` 之功能的程式碼 ::: * 若 `payload` 為 `'8BADF00D'` * 在 Little Endian ， `value` 為 `0x0d 00 00 0f 0d 0a 0b 08` * 在 Big Endian ， `value` 為 `0x08 0b 0a 0d 0f 00 00 0d` ## Q3. 除法運算的改進的策略 #### 將除法改為乘法運算 $$ \frac{n}{d} = \frac{n\times2^N}{d\times2^N} = n \times \frac{\frac{2^N}{d}}{2^N} $$ $$ = (n \times \frac{2^N}{d}) >> N $$ 其中，$2^N/d$ 可以先算好，節省時間 ```c= const uint32_t D = 3; #define M ((uint64_t)(UINT64_C(XXX) / (D) + 1)) // XXX = 0xFFFFFFFFFFFFFFFF /* 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; } ``` >當我們想將 5 除以 4 時，就相當於乘以 0.25，所以我們可將 $5/4$ 改為 5×0.25，我們得到整數的部分 (即 1)，和小數部分 (即 0.25)，後者乘以 4 就是 1 ，也就是餘數。 :::info * **`uint64_t`** * unsigned integer type with width of exactly 64 bits (provided only if the implementation directly supports the type) * **`UINT64_C`** * expands to an integer constant expression having the value specified by its argument and whose type is the promoted type of `uint_least64_t` * **`uint_least64_t`** * smallest unsigned integer type with width of at least 64 bits * **`__uint128_t`** * [GCC extension](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html)，用以表示 128 位元的無號數值 ::: * 程式碼解析： * 與數學式對比後，可以發現 N = 64 及 `M` 應該是擔任 $2^N/d$ 的角色，但仍須考量： * $2^N/d$ 可能不整除 * `uint64` 無法表示小數， * 應該可以用某些手法來避免上述困擾 * 因此，可以猜測 XXX 的值應該與 $2^N$ 差距不遠，故選 0xFFFFFFFFFFFFFFFF ( i.e. $2^N-1$ ) #### 證明正確性 $$ 0 \leq n - q \times D < D , $$ $$ where \space n,D \space \epsilon \space \mathbb{N} \space and \space q = \left\lfloor\frac{n\times(\left\lfloor\frac{2^N -1}{d}\right\rfloor +1)} {2^N} \right\rfloor , \space N \space \epsilon \space \mathbb{N} $$ * 若已知 n 、 D 為正整數，則存在唯一一組整數解 q 、 r 、且 $0\leq r<D$，使得 $n = q\times D+r$ * 因此，只要能完成上述證明，便能證明程式的正確性 ## Q4. 呈 Q3 ，判斷某個數值能否被指定的除數所整除 * `D` 和 `M` 都沿用 Q3 ```c= const uint32_t D = 3; #define M ((uint64_t)(UINT64_C(XXX) / (D) + 1)) bool divisible(uint32_t n) { return n * M <= YYY; // YYY = M-1 } ``` >divisible(7) 要得到 0 (即 7 無法被 3 整除) >divisible(87) 要得到 1 (即白痴是三的倍數) ## Q5. 將指定的字串 (或部分字串) 的英文字母全改為小寫 #### in-place 的實作: (一次比對一個字元) ```c #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]); } } ``` :::info * **`int tolower ( int c );`** * **Convert uppercase letter to lowercase (任何語系)** * Converts c to its lowercase equivalent if c is an uppercase letter and has a lowercase equivalent. If no such conversion is possible, the value returned is c unchanged. ::: #### 向量化 (vectorized) : (一次操作一整個 word ) 在 64 位元處理器架構 (以下針對 `x86_64`, little endian)，我們可引入向量化 (vectorized) 的手段，避免一次比對一個字元，而是直接操作一整個 word (對 `x86_64` 來說，就是 64 bits，或 8 個位元組)。 ```c= #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); } ``` * 程式碼解析： ```c #5 #define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u) ``` >0xff = ( 0000 ... 0000 1111 1111 )~2~ * 若 `b` 為 0x * ... * cd = ( **** ... **** 1011 1100 )~2~ ，則 `(uint64_t)(b) & (0xff)` 的結果為 ( 0000 ... 0000 1011 1100 ) = 0xcd，即 **取出 `b` 在 16 進制的最後兩位數** * `0xcd * 0x0101010101010101u` 結果為 0xcdcdcdcdcdcdcdcd ，即 **將前者複製 8 次** ```c #10 size_t k = n / 8; #11 for (size_t i = 0; i < k; i++, s += 8) { #12 uint64_t *chunk = (uint64_t *) s; ``` * 8 bytes 一組，共有 `k` 組需要比對 * 當然，還有剩餘不滿 8 bytes 的部份，由下一段程式碼處理 ##### case 1 : 8 個 bytes 皆為有效 ASCII 字元 ```c #13 if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */ ``` * 根據提示，`#13` 判斷 `*chunk` 是否為有效的 ASCII 字元 ( 請參考 Q1 ) * 一次檢查 8 bytes ，因此 `PACKED_BYTE(VV1)` 必須為 0x8080808080808080 * 若 `*chunk & PACKED_BYTE(VV1)` 為 0，則 `*chunck` 8 bytes 皆為有效的 ASCII 字元 * 故 **VV1 = 0x80** ```c #17 *chunk ^= mask; ``` * 根據 `#17` ，我們可以猜測，程式想用 `('A' ^ ' ') // 得到 'a'` 的原理，進行大小寫轉換 > `' '` = 0x20 = 0010 0000 * 接下來，們還需要辨別，哪些 bytes 裡頭存放著大寫，找出其在 `mask` 上的對應位置放上 0x20 反之則為小寫，在 `mask` 上的對應位置放上 0x00 ```c #16 uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2; ``` * 若只考慮 1 byte，且該 byte 存放著大寫字母，則 `mask = ((A ^ Z) & VV4 ) >>2` 應為 0x20 = ( 0010 0000 ) * `((A ^ Z) & VV4 )` 為 ( 1000 0000 ) = 0x80 * 若只考慮 1 byte，且該 byte 存放著小寫字母，則 `mask = ((A ^ Z) & VV4 ) >>2` 應為 0x00 = ( 0000 0000 ) * `((A ^ Z) & VV4 )` 為 ( 0000 0000 ) = 0x00 * 綜上所述，我們假設 **VV4= 0x80**，且 * 若存放著大寫字母，`(A ^ Z)` 應為 ( 1*** **** ) * `A` 應為 ( 1*** **** ) 、 `Z` 應為 ( 0*** **** ) * 若存放著小寫字母，`(A ^ Z)` 應為 ( 0*** **** ) * `A` 應為 ( 1*** **** ) 、 `Z` 應為 ( 1*** **** ) ```c #14 uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2); ``` * `#14` 應該要找出 ASCII 編碼 >= `'A'` ( i.e. ( 0100 0001 ) ) 的 bytes * `128 - 'A'` = ( 1000 0000 ) - ( 0100 0001 ) = ( 0011 1111 ) * 若只考慮 1 byte，且該 byte 存放著大寫字母，則 `*chunk + (128 - 'A' + VV2)` = ( 010* **** ) + ( 0011 1111 ) + VV2 * 因為 `*chunk` 是大寫字母，所以 * ( 010* **** ) + ( 0011 1111 ) >= `'A'` ( 0100 0001 ) + ( 0011 1111 ) = ( ==1==000 0000 ) * ( 010* **** ) + ( 0011 1111 ) <= `'Z'` ( 0101 1010 ) + ( 0011 1111 ) = ( ==1==001 1001 ) * 可達成我們假設的目標：`A` 應為 ( 1*** **** ) * 因此，假設 **VV2 = 0** * 同理，若存放的是小寫字母， VV2 = 0 也能成立 ```c #15 uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3); ``` * `#15` 應該要找出 ASCII 編碼 <= `'Z'` ( i.e. ( 0101 1010 ) ) 的 bytes * `128 - 'Z'` = ( 1000 0000 ) - ( 0101 1010 ) = ( 0010 0110 ) * 若只考慮 1 byte，且該 byte 存放著大寫字母，則 `*chunk + (128 - 'Z' + VV3)` = ( 010* **** ) + ( 0010 0110 ) + VV3 * 因為 `*chunk` 是大寫字母，所以 * ( 010* **** ) + ( 0010 0110 ) >= `'A'` ( 0100 0001 ) + ( 0010 0110 ) = ( ==0==110 0111 ) * ( 010* **** ) + ( 0010 0110 ) <= `'Z'` ( 0101 1010 ) + ( 0010 0110 ) = ( 1000 0000 ) * 除了 `'Z'` 以外，其他大寫字母都能達成假設的目標：`Z` 應為 ( 0*** **** ) * 若也要讓 `'Z'` 達成目標，可以假設 **VV3 = -1** * 同理，若存放的是小寫字母， VV3 = -1 也能成立 ##### case 2 : 8 個 bytes 中，至少有一個不為有效 ASCII 字元 ```c #18 else #19 strlower(s, 8); ``` * 若 `*chunk` 中有幾個 bytes 不為有效的 ASCII 字元，則無法一次轉換 8 bytes * 用傳統方式一次檢查一個 bytes ##### case 3 : 剩餘不滿 8 個 bytes 的部份 ```c #22 k = n % 8; #23 if (k) #24 strlower(s, k); ``` * 所有能 8 個 bytes 一組的轉換完之後，可能會有 1~7 個 bytes 尚未轉換 * 用傳統方式一次檢查一個 bytes ## Q5. 進階題 #### 將前述測試程式 `main` 函式的 char `str[]` 更換為 char `*str`，會發生什麼事？ * 會出現 ``` 程式記憶體區段錯誤 (核心已傾印) Segmentation fault ``` * [ISO/IEC 9899:1999](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) : :::success $§\space 6.4.5\space String \space\space literals\space$ ( p.62 ) * In translation phase 7, a byte or code of value zero is appended to each multibyte character sequence that results from a string literal or literals. ==The multibyte character sequence is then used to initialize **an array of static storage** duration and length just sufficient to contain the sequence.== For character string literals, the array elements have type `char`, and are initialized with the individual bytes of the multibyte character sequence; ... * ==It is **unspecified** whether these arrays are distinct provided their elements have the appropriate values.== ==If the program attempts to modify such an array, the behavior is **undefined**.== ::: :::success $§\space 6.7.8\space EXAMPLE \space\space 8\space$ ( p.130 ) 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**.== ::: ## q6. LeetCode [137. Single Number I](https://leetcode.com/problems/single-number/) Given a non-empty array of integers, every element appears twice except for one. Find that single one. >Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? ```c= int singleNumber(int* nums, int numsSize){ int note = 0; for (int i=0 ; i< numsSize ; i++) note ^= nums[i]; return note; } ``` * ==XOR 運算 = 看到 1 就反轉，看到 0 不變== * 從 bitwise 的角度出發，`note` 的每個 bit 分別紀錄以檢查的 `nums[i]` 各 bit 出現 1 的次數 * 若出現次數 mod 2 = 0 ，則 note~i~ 設為 0 * 若出現次數 mod 2 = 1 ，則 note~i~ 設為 1 * 狀態圖：( 圓圈中的值代表 note~i~ ) ```graphviz digraph { rankdir = LR 0 -> 1 [label = "input = 1"] 1 -> 0 [label = "input = 1"] 0 -> 0 [label = "input = 0"] 1 -> 1 [label = "input = 0"] } ``` * Truth table | A | B | C | | ------- | ------ |:----------- | | note~i~ | num~i~ | new note~i~ | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | * $C = 01 + 10$ $= A'B + AB'$ $= A \oplus B$ * 因此， **new note~i~ = note~i~ $\oplus$ num~i~** ## Q6. LeetCode [137. Single Number II](https://leetcode.com/problems/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? ```c= int singleNumber(int *nums, int numsSize) { int lower = 0, higher = 0; for (int i = 0; i < numsSize; i++) { lower ^= nums[i]; lower &= KKK; // KKK = ~higher higher ^= nums[i]; higher &= JJJ; // JJJ = ~lower } return lower; } ``` * 與 q6 相同概念，不同的是，數字可能出現 1~3 次，需要 `lower` ( 下方簡稱 L )及 `higher` ( 下方簡稱 H ) 兩個值來幫忙紀錄： * 若出現次數 mod 3 = 0 ，則 H~i~L~i~ 設為 0==0== * 若出現次數 mod 3 = 1 ，則 H~i~L~i~ 設為 0==1== * 若出現次數 mod 3 = 2 ，則 H~i~L~i~ 設為 1==0== * 狀態圖：( 圓圈中的值代表 H~i~L~i~ ) ```graphviz digraph { rankdir = LR 00 -> 01 [label = "input = 1"] 01 -> 10 [label = "input = 1"] 10 -> 00 [label = "input = 1"] 00 -> 00 [label = "input = 0"] 01 -> 01 [label = "input = 0"] 10 -> 10 [label = "input = 0"] } ``` * Truth table | A | B | C | D | E | |:---- | ---- | ------ | -------- |:-------- | | H~i~ | L~i~ | num~i~ | new H~i~ | new L~i~ | | 0 | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 0 | 1 | | 0 | 1 | 0 | 0 | 1 | | 0 | 1 | 1 | 1 | 0 | | 1 | 0 | 0 | 1 | 0 | | 1 | 0 | 1 | 0 | 0 | * $E = 001 + 010$ $= A'B'C + A'BC'$ $= A'(B'C + BC')$ $= A'(B \oplus C)$ * 因此，**new L~i~ = ~ H~i~ & ( L~i~ $\oplus$ num~i~ )** * $D = 001 + 100$ $= A'E'C + AE'C'$ $= E'(A'C + AC')$ $= E'(A \oplus C)$ * 因此，**new H~i~ = ~ (new L~i~) & ( H~i~ $\oplus$ num~i~ )** * 故，**KKK = ~higher** 、 **JJJ = ~lower** ## Q6. 進階題 #### 請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時 ##### 解法一 ```c= int singleNumber(int *nums, int numsSize) { int lower = 0, higher = 0; for (int i = 0; i < numsSize; i++) { int tmp = lower; lower ^= nums[i]; lower &= ~higher; higher = (~higher & tmp & nums[i]) | (higher & ~tmp & ~(nums[i])); } return lower; } ``` * Q6. 最後的數學推導中， new H~i~ 還有另一種寫法： * $D = 011 + 100$ $= A'BC + AB'C'$ * 因此， new H~i~ = ( ~ H~i~ & L~i~ & num~i~ ) | ( H~i~ & ~ L~i~ & ~ (num~i~) ) * [檢測結果](https://leetcode.com/submissions/detail/400937625/)： ![](https://i.imgur.com/lxrngA1.png) ##### 解法二： ( 參考 [RinHizakura 同學](https://hackmd.io/@RinHizakura/SJ5NuIANP#%E4%B8%8D%E5%90%8C%E7%9A%84%E8%A7%A3%E9%A1%8C%E6%80%9D%E8%B7%AF) ) * 數字只可能出現 1、3 次，可能只需要 `note` 一個值紀錄即可： * 若出現次數 mod 3 = 0 or 2 ，則 note~i~ 設為 0 * 若出現次數 mod 3 = 1 ，則 note~i~ 設為 1 #### 將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼 ##### 重複 4 次 ( 偶數次 ) * 重複 2的倍數次的情形，都可以使用 [q6](#q6-LeetCode-137-Single-Number-I) 的解法 * 同理，重複 3的倍數次的情形，也都可以使用 [Q6](#Q6-LeetCode-137-Single-Number-II) 解法 ##### 重複 5 次 ( 5的倍數次 ) ```c= int singleNumber(int *nums, int numsSize) { int left = 0, middle = 0, right = 0; for (int i = 0; i < numsSize; i++) { right = ~left & (nums[i] ^ right); middle = ~left & ((~right & (middle ^ nums[i])) | (middle & right)); left = ~middle & ~right & (left ^ nums[i]); } return right; } ``` * 數字可能出現 1~5 次，需要 `left`( 下方簡稱 L )、`middle`( 下方簡稱 M )、`right`( 下方簡稱 R ) 三個值來幫忙紀錄： * 若出現次數 mod 5 = 0 ，則 L~i~M~i~R~i~ 設為 0==00== * 若出現次數 mod 5 = 1 ，則 L~i~M~i~R~i~ 設為 0==01== * 若出現次數 mod 5 = 2 ，則 L~i~M~i~R~i~ 設為 0==10== * 若出現次數 mod 5 = 3 ，則 L~i~M~i~R~i~ 設為 0==11== * 若出現次數 mod 5 = 4 ，則 L~i~M~i~R~i~ 設為 1==00== * 狀態圖：( 圓圈中的值代表 L~i~M~i~R~i~ ) ```graphviz digraph { rankdir = LR 000 -> 001 [label = "input = 1"] 001 -> 010 [label = "input = 1"] 010 -> 011 [label = "input = 1"] 011 -> 100 [label = "input = 1"] 100 -> 000 [label = "input = 1"] 000 -> 000 [label = "input = 0"] 001 -> 001 [label = "input = 0"] 010 -> 010 [label = "input = 0"] 011 -> 011 [label = "input = 0"] 100 -> 100 [label = "input = 0"] } ``` * Truth table: | A | B | C | D | E | F | G | | ---- | ---- |:---- | ------ | -------- | -------- |:-------- | | L~i~ | M~i~ | R~i~ | num~i~ | new L~i~ | new M~i~ | new R~i~ | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 0 | 0 | 0 | 1 | 0 | 0 | 1 | | 0 | 0 | 1 | 0 | 0 | 0 | 1 | | 0 | 0 | 1 | 1 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 1 | 0 | 1 | 1 | | 0 | 1 | 1 | 0 | 0 | 1 | 1 | | 0 | 1 | 1 | 1 | 1 | 0 | 0 | | 1 | 0 | 0 | 0 | 1 | 0 | 0 | | 1 | 0 | 0 | 1 | 0 | 0 | 0 | ![](https://i.imgur.com/7vBeHtN.jpg) * 由上圖的推導，我選擇下列這組解： * new R~i~ = ~ L~i~ & ( R~i~ $\oplus$ num~i~ ) * new M~i~ = ~ L~i~ & ( ( ~ (new R~i~) & ( M~i~ $\oplus$ num~i~ ) ) | ( M~i~ & new R~i~ ) ) * new L~i~ = ~ (new M~i~) & ~ (new R~i~) & ( L~i~ $\oplus$ num~i~ )

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.