---
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/)：
##### 解法二： ( 參考 [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 |
* 由上圖的推導，我選擇下列這組解：
* 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~ )
Sign in with Wallet
Connect another wallet