# 2020q3 Homework2 (quiz2)
## [題目](https://hackmd.io/@sysprog/2020-quiz2)
## 1. is_ascii
### 目的: 改善效率
```c
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>
#define MMM 0x8080808080808080
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;
}
int main(int argc, char **argv) {
int i;
for(i = 1; i < argc; i++)
printf("%s: %s\n", argv[i], is_ascii(argv[i], strlen(argv[i])) ? "True" : "False");
return 0;
}
```
執行結果: 
美國資訊交換標準代碼:
**A**merican **S**tandard **C**ode for **I**nformation **I**nterchange
定義了128個字元，它主要用於顯示現代英語。
原版的is_ascii()是逐個char做比對，一個char只有8bit很慢。
所以 `uint64_t payload;` 這行的用意是，指定一個64bit的空間作暫存。
再來透過==memcpy==把字串讀進這個空間。
再來就是整個程式的核心
`payload & MMM`
判斷字串是否在ASCII的範圍裡，最直觀的做法就是，每個byte要小於128(即0~127)。
在二進位的世界裡:
$$127_{10} = 0111\ 1111_2$$
也就是最左邊的位元(**Most Significant Bit**)必須是零，因此只要這的bit是1，這個字元必定不符合ASCII的基本規範。
最簡單的判斷方法就是直接用==AND==來過濾。
```XXXX XXXX``` ==AND== ```1000 0000``` 得到 ```X000 0000```
再用if判斷有無，馬上就會知道條件是否符合。
而二進位```1000 0000```用十六進位表達就會是 ==0x80== (8bit)
又payload有64bit那麼大，(64bit) / (8bit) = (8組0x80)
故這題答案是8組0x80，即 **0x8080808080808080**
### 延伸問題 memcpy
:::success
延伸問題:
為何用到 `memcpy`？
:::
memcpy語法:
`memcpy(target_address, source_address, size_in_bytes)`
其功能是把指定區域的內容複寫到目標空間。
```graphviz
digraph structs {
node[shape=record]
source [label="source|<0>0|<1>1|<2>0|<3>...|<4>0|<5>1|<6>0"];
target [label="target|<0>0|<1>1|<2>0|<3>...|<4>0|<5>1|<6>0"];
source:0 -> target:0;
source:1 -> target:1;
source:2 -> target:2;
source:3 -> target:3;
source:4 -> target:4;
source:5 -> target:5;
source:6 -> target:6;
}
```
雖會因架構而異，但 CPU 一般不會一次只處理 1 byte 的資料。
==Block size==指每次執行的所抓取的資料塊大小，memcpy有多個版本，==byte-by-byte==, ==word-by-word==...所以編譯器會選一個適合尺寸，在資料對齊後，讓CPU可以更有效率去複寫，減少cycle數。
若是不用memcpy而改用strcpy或是其他函數，則難以預料其後果，很可能會變慢或有預想外的行為。
比如說用**強轉**，在**ARM**上有可能會造成[Unaligned Data Access](https://www.keil.com/support/man/docs/armcc/armcc_chr1359124229461.htm)
`uint64_t *payload = (uint64_t *) str`
**效能差異**: 我丟了一個NGS實驗的DNA序列檔，避開讀檔時間，針對個別函數去計時，觀察到6倍以上的速度差距。
```c
int main(int argc, char **argv) {
char * buffer = 0;
unsigned long long length;
FILE *f;
if (argv[1])
f = fopen(argv[1], "rb");
else return 1;
if(f) {
fseek (f, 0, SEEK_END);
length = ftell (f);
fseek (f, 0, SEEK_SET);
buffer = malloc (length);
if(buffer)
fread (buffer, 1, length, f);
fclose(f);
} else return 1;
double time_spent = 0.0;
clock_t begin = clock();
bool b = ori_is_ascii(buffer, length);
clock_t end = clock();
time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf("Time elpased for original is_ascii is %f seconds\n", time_spent);
begin = clock();
b = opt_is_ascii(buffer, length);
end = clock();
time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf("Time elpased for optimized is_ascii is %f seconds\n", time_spent);
return 0;
}
```
```
$ ./run ~/Analysis/25ctrl24_L4_1.fq
Time elpased for original is_ascii is 3.680090 seconds
Time elpased for optimized is_ascii is 0.590715 seconds
```
---
## 2. hexchar2val
### 目的: 將十六進位的字元轉換成值
```c
#include <stdint.h>
#include <stdio.h>
#define MASK 0x40
#define AAA 3
#define BBB 6
uint8_t hexchar2val(uint8_t in)
{
const uint8_t letter = in & MASK;
const uint8_t shift = (letter >> AAA) | (letter >> BBB);
return (in + shift) & 0xf;
}
int main(int argc, char **argv) {
int i;
for(i = 1; i < argc; i++)
printf("%s = %d\n", argv[i], hexchar2val(*(argv[i])));
return 0;
}
```
執行結果:
首先我們先觀察一下字元的編碼 [0-9],[A-F],[a-f]
數字組```0x30```, ```0x31```, ```0x32```, … ```0x39```
字母大寫 ```0x41```, ```0x42```, … ```0x46```
字母小寫 ```0x61```, ```0x62```, … ```0x66```
取字元'0'改用二進位表達，即```0x30```
```0011 0000```
取字元'A'改用二進位表達，即```0x41```
```0100 0001```
取字元'0'改用二進位表達，即```0x61```
```0110 0001```
我們可以看到數字的值剛好等於十六進位的個位數。
而字母的值剛好等於十六進位的個位數再```+9```。
同時，在這裡可以發現，用```0100 0000```當MASK可以很簡單地把數字跟字母分開。
MASK完後，後續的shift只要選好適當的AAA, BBB值，就可以使shift變數保持恆為0。
```in + 0``` 還是```in```，```in```再跟```0xf```==AND==一次就只剩後面4個bit，這4個bit就是十六進位的個位數值。
到這裡，數字的轉換解決了。
字母的部分，只要想辦法讓```in```可以```+9```，就可以得到它的值。
在這裡，```letter```的值就是```0100 0000```。
再來就是湊數字了，想辦法讓shift變數恆等於9:
往右位移 3, 6次，分別得到```0000 1000```跟```0000 0001```
這兩個再==OR==起來就是9了，即```0000 1001```
這時```(in + shift) & 0xf```就會是我們要的東西了。
### 延伸問題 Hexspeak
:::success
延伸問題: Hexspeak
擴充`hexchar2val`，並輸出對應的十進位數值
:::
```c
#include <stdint.h>
#include <stdio.h>
#include <string.h>
uint8_t hexchar2val(uint8_t in)
{
const uint8_t letter = in & 0x40;
const uint8_t shift = (letter >> 3) | (letter >> 6);
return (in + shift) & 0xf;
}
int hexspeak(const char *in) {
const char *str;
str = in + 2;
int r = 0;
while (*str) {
r = r << 4; // r * 16
r += hexchar2val(*str);
str++;
}
return r;
}
int main(int argc, char const *argv[]) {
for (size_t i = 1; i < argc; i++) {
printf("%s = %d\n", argv[i], hexspeak(argv[i]));
}
return 0;
}
```
輸入的字串格式上都以"0x"做開頭，因此可以直接跳過前兩個字元(`str = in + 2`)，剩下的部分再加總起來，因為是16進位，所以每個位數要作加法前都要乘以16，可以用位移簡化。
執行結果: 
---
## 3. quickmod
### 目的: 當除數已知，快速求餘數
```c
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
const uint32_t D = 3;
#if defined (__aarch64__) | defined(__amd64__) | defined(__x86_64__)
#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;
// {[(2^N - 1) / D] + 1} * [ n / (2^N)]
return n - quotient * D;
}
#else
#define M ((uint32_t)(UINT32_C(0xFFFFFFFF) / (D) + 1))
/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n) {
uint32_t quotient = ((__uint64_t) M * n) >> 32;
// {[(2^N - 1) / D] + 1} * [ n / (2^N)]
return n - quotient * D;
}
#endif
int main(int argc, char **argv) {
uint32_t i = quickmod(5);
printf("%d\n", i);
i = quickmod(55);
printf("%d\n", i);
i = quickmod(555);
printf("%d\n", i);
return 0;
}
```
計算$n/d$有個特別的方法，由於分子分母同乘任意值，其值不變。所以只要把會用到的最大值事先除以已知的分母$d$ (denominator)，之後再乘回去變數$n$，這樣做的理由是，對電腦而言，除法計算所需要的操作遠比乘法來的複雜，用乘法取代除法，就可以節省運算所需的時間。
在電腦上，$N$位元的組合可以表達 $(2^N)$ 個數字。 故
$$\dfrac{n}{d}=\dfrac{n(2^N)}{d(2^N)}=n\times(\dfrac{2^N}{d})\div(2^N)$$
從上式可知，除法可拆成三個部分
1. 變數 $n$
2. $\dfrac{2^N}{d}$ --> $\dfrac{2^N-1}{d}+1$
3. $2^N$
(1)由函數的參數提供；(3)除以二的N次方可用位移N次簡化；剩下的就是(2)，又$d$已知，只要將計算所得作為常數儲存，即可迅速帶入公式求解。
但因為受限於電腦編碼的特性，數字組合包括零，所以最大值其實是 $(2^N-1)$ ，我們只能用 $2^N - 1$ 作為近似值計算。 $2^N - 1$ 就是全部填滿，即0xFFF.....直到填滿空間。而為了補足使用近似值所造成的誤差，可再將計算結果加一。 以 $(\dfrac{2^N-1}{d}+1)$ 取代 $\dfrac{2^N}{d}$
舉個簡單的例子: 設$N=4$ (即只用4bit簡化計算)，求$n/3$；在此假設下，最大值為$2^4-1=15_{10}$，可表示成$1111_2$。當$d$已知(d=3)，可得$n/d=[n\times(\frac{15}{3}+1)] >> 4$。設$n=7$，帶入算式得$42_2>>4$ 位移後得 ==0010 ~~0011~~==，即商為$2$。欲計算餘數，則 $n-dq=7 - 3 \cdot 2 = 1$
以相同原理可推廣到更高的位元 (8-bit,16-bit,32-bit,64-bit...)
:::info
**程式的改良:**
受限於硬體限制，有些機器沒有 ==__uint128_t== 可用，所以我稍微改寫了一下原始碼，讓它可以在編譯時，選擇比較適當的大小作運算。
多數編譯器可利用以下巨集簡單分辨是否為64位元處理器
#if defined (__aarch64__) | defined(__amd64__) | defined(__x86_64__)
#define code for 64-bit
#else
#define code for 32-bit
#endif
:::
參考資料: [Faster remainders when the divisor is a constant: beating compilers and libdivide](https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/?fbclid=IwAR2yz_T_siwv77DCOuFo8tZoPrSpxDaQ1zbh6OCbBat_Qs3CgbHN3Y_NPYY)
---
## 4. divisible
### 目的: 當除數已知，判斷是否整除
```c
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
const uint32_t D = 3;
#if defined (__aarch64__) | defined(__amd64__) | defined(__x86_64__)
#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;
// {[(2^N - 1) / D] + 1} * [ n / (2^N)]
return n - quotient * D;
}
#else
#define M ((uint32_t)(UINT32_C(0xFFFFFFFF) / (D) + 1))
/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n) {
uint32_t quotient = ((__uint64_t) M * n) >> 32;
// {[(2^N - 1) / D] + 1} * [ n / (2^N)]
return n - quotient * D;
}
#endif
typedef unsigned char bool;
#define YYY (M - 1)
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
int main(int argc, char **argv) {
uint32_t i = 5;
printf("MOD = %d, %s\n", quickmod(i), divisible(i) ? "divisible" : "undivisible");
i = 55;
printf("MOD = %d, %s\n", quickmod(i), divisible(i) ? "divisible" : "undivisible");
i = 555;
printf("MOD = %d, %s\n", quickmod(i), divisible(i) ? "divisible" : "undivisible");
return 0;
}
```
除法部分，原理與上題quickmod相同。
回顧一下除法原理: 被除數 $\div$ 除數 = 商 + 餘(小數點以後的部分)
$$\dfrac{n}{d}=q + r\space;\space q \in Z\space;\space 0 \leq r < 1$$
假設我們的機器是64位元，當兩個64位元數字相乘會得到128位元的數字。參考到上一題的解法，會發現 $q$ (商)就是$n \times M$的前64位元，$r$ (餘)就是剩下來的64位元。
在驗證的地方運用到overflow的特性，剛剛說到商就是$n \times M$的前64位元，因為這裡沒有做位移的操作，所以單純的$n \times M$必定overflow，留下來的是後面的64位元。
換句話說，現在留下來的值是 $r$ (小數點以後的部分)
$$r = \dfrac{n}{d} - q\space;\space r \in \{0/d, 1/d, 2/d,...,i/d\}\space;\space i \in \{0, 1, 2, ..., q-1\}$$
欲判斷是否整除，$i$必須為$0$，由於會有誤差，可以改為判斷$r < 1/d$。
知道這些後，用程式碼表達就是`return n * M < M`
因為題目要求`return n * M <= YYY`，考慮到等號造成的誤差，==M-1==才會是適合這題的答案。
---
## 5. strlower_vector
### 目的: 轉換字元編碼成小寫
```c
#include <ctype.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#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]);
}
}
#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)
#define VV1 0x80
#define VV2 0
#define VV3 -1
#define VV4 0x80
/* 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);
}
int main()
{
/* quote from https://www.gutenberg.org/files/74/74-h/74-h.htm */
char str[] = // why not __char *str__, if so, str can not be modified
"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);
return 0;
}
```
比較字元編碼: [A-Z],[a-z]
字母大寫 ```0x41```, ```0x42```, … ```0x5A```
二進位 `0100 0001`, `0100 0002`, … `0101 1010`
字母小寫 ```0x61```, ```0x62```, … ```0x7A```
二進位 `0110 0001`, `0110 0002`, … `0111 1010`
巨集PACKED_BYTE的用意跟第1題(is_ascii)的變數==payload==相近，把小單位的變數拓展成較大的尺寸，達成一口氣比對更多位元的效果。
`if ((*chunk & PACKED_BYTE(VV1)) == 0)`
欲判斷一個字元是否符合ASCII，直接比對8-bit變數裡的**Most Significant Bit**。
$1000\ 0000_2 = 80_{16}$
所以==VV1==是`0x80`
指標==chunk==型態為(uint64_t *)，寬度達64-bit。
PACKED_BYTE用乘法把`0x80`展開，以符合==chunk==的大小，即`0x8080808080808080`。
==VV2== 跟 ==VV3== 一起看，要圈出字母A~Z的範圍，直觀上分別判斷每個byte是否介於兩者之間($A \leq byte \leq Z$)。
換個角度想，就是要判斷`(byte - 'A' >= 0 && byte - 'Z' <= 0)`，只是光這樣仍無法簡單用bitwise操作處理。
於是再加一些變化，等式兩邊同加`0x80`，得到`(byte + 128 - 'A' >= 128 && byte + 128 - 'Z' <= 128)`。
考慮一下溢位，修改一些參數，融合bitwise的精神，整理後得`(byte + 128 - 'A' & 0x80)`跟`byte + 128 - 'Z' - 1 & 0x80)`這兩個條件。
由此可知題目的==VV2== = 0；==VV3== = -1。
變數`A`跟`Z`利用==XOR==的特性，做為mask以判斷`*chunk`是否同時符合條件(介於兩者之間)。
:::info
**轉換小寫的另一個方法:**
只要每個byte都跟$0010\space0000_{2}$==OR==一下
大寫會轉小寫，小寫依然是小寫。
==XOR==則比較適合大小寫的轉換。
:::
==XOR==做完之後，如果是範圍內的數，**Most Significant Bit**必會是1，上面藍框內提到轉換小寫會用到這個$0010\space0000_{2}$，它跟MSB差了兩個shift，所以mask最後還需要向右位移兩次。
### 延伸問題 `str[]` `*str`
:::success
延伸問題:
如果把`char str[]`更換為`char *str`，會發生什麼事？
:::
一般這麼做會收到==Segmentation fault==的訊息，通常指動到不該動的記憶體位址。
`*str`是唯讀的，屬於靜態配置的string literal，如果你去改它就會觸發undefined behavior。
而`str[]`則會在初始化時，於記憶體裡的stack中建立可修改的副本，不會觸發UB。
6.4.5 String literals
> 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.
參考資料: [C語言規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)
---
## 6. singleNumber
### 目的: 已知array所有元素必存在三個copies，僅一個元素沒有，求該元素
```c
#define KKK ~higher
#define JJJ ~lower
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;
}
int main() {
int data[] = {2,2,3,2};
return singleNumber(data, 4);
}
```
**原理:** 這題的解法很不直觀，先來看看另一種做法的解題思路。
**Counting Set Bit** - 通過計算位元總數來求解。
以```data[] = {2,2,3,2}```為例可得下表: ($2_{10} = 10_2$；$3_{10} = 11_2$)
|$\downarrow$|$\downarrow$|
|:-:|:-:|
|1|0|
|1|0|
|1|1|
|1|0|
將所有數字的各個位元分別加總起來，在左邊這行(column)總合是4，右邊這行是1。分別對3取餘數，各會得到1。兩邊併在一起用二進位表達就是$11_2 = 3_{10}$。
這樣做可以很直觀的找到我們要找的single number，但問題是一個int不小，通常有32位元，這意味著有32個bit要數，實作上很可能比先排序再搜尋還要慢。
這裡就要用上一個特別的邏輯操作XOR，XOR有個特性，取任意一個數字，對另一個數字==XOR==兩次，其值不變，即**自反性**。
$$p \oplus q \oplus q = p \oplus 0 = p$$
真值表如下:
|$p$|$q$|$p \oplus q$|
|:-:|:-:|:----------:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
利用這個會自己回歸的特性，可以用來記錄狀態。如果題目的設定是所有數字兩兩成對，僅一個數單獨存在，那把整個數列(array)從頭XOR到底，就可以很快地得到答案。但由於題目是三個重複，所以還要加一點修改讓變數可以載運行三次後回歸為零。
**換句話說，這題的本質就是利用bitwise操作達成三進位的計算。**
這題利用兩個變數lower, higher來記錄位元的變化，暫時先用True/False簡化以理解其原理。這裡先畫出我們想要的規律。
|出現次數|lower|higher|
|:----:|:----:|:----:|
|1|True|False|
|2|False|True|
|3|False|False|
再來答案湊一湊就知道這樣寫可以滿足上面這張表所要的效果。
```c
for (int i = 0; i < numsSize; i++) {
lower ^= nums[i];
lower &= ~higher;
higher ^= nums[i];
higher &= ~lower;
}
```
實際去一步一步展開就會是以下結果:
| i | nums[i] | action | lower | higher |
|:-:|:-------:| :-------------: |:-----:|:------:|
| 0 | 2 | - | 0 | 0 |
| 0 | 2 |lower ^= nums[i] | 2 | 0 |
| 0 | 2 |lower &= ~higher | 2 | 0 |
| 0 | 2 |higher ^= nums[i]| 2 | 2 |
| 0 | 2 |higher &= ~lower | 2 | 0 |
| 1 | 2 |lower ^= nums[i] | 0 | 0 |
| 1 | 2 |lower &= ~higher | 0 | 0 |
| 1 | 2 |higher ^= nums[i]| 0 | 2 |
| 1 | 2 |higher &= ~lower | 0 | 2 |
| 2 | 3 |lower ^= nums[i] | 3 | 2 |
| 2 | 3 |lower &= ~higher | 1 | 2 |
| 2 | 3 |higher ^= nums[i]| 1 | 1 |
| 2 | 3 |higher &= ~lower | 1 | 0 |
| 3 | 2 |lower ^= nums[i] | 3 | 0 |
| 3 | 2 |lower &= ~higher | 3 | 0 |
| 3 | 2 |higher ^= nums[i]| 3 | 2 |
| 3 | 2 |higher &= ~lower | 3 | 0 |
最終回傳==lower=3==。
### 延伸問題 LeetCode
:::success
延伸問題:
請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時
:::
```c
int singleNumber(int* nums, int numsSize){
if (numsSize == 1) {
return nums[0];
}
int once = 0, twice = 0, thrice = 0;
for (size_t i = 0; i < numsSize; i++) {
twice |= once & nums[i];
once ^= nums[i];
thrice = once & twice;
once &= ~thrice;
twice &= ~thrice;
}
return once;
}
```
利用三個變數搭配邏輯操作，達成三次一循環的效果。
==once==, ==twice== 分別表示出現的次數。
==thrice==則在第三次出現時，作為MASK使用，修正==once==跟==twice==的狀態。
```c
twice |= once & nums[i];
```
==twice==必須比==once==先執行，確保值的正確性。
如果在```once```跟```nums[i]```同時有值，代表這個bit已經是第二次出現了，透過```AND```即可過濾出來。
```c
once ^= nums[i];
```
==once==與輸入值==nums==利用自反性，加入第一次出現的值，同時削去第二次出現的值。
```c
thrice = once & twice;
once &= ~thrice;
twice &= ~thrice;
```
這三個操作是為了找出出現三次的bit，並記錄在==thrice==變數，再利用==thrice==變數反轉作為MASK去除==once==跟==twice==的狀態。
LeetCode執行結果:
### 延伸問題 重複多次
:::success
延伸問題:
將重複 3 次改為改為重複 4 次或 5 次
:::
**重複 4 次**
```c
int singleNumber(int* nums, int numsSize){
int r = 0;
for (int i = 0; i < numsSize; i++) {
r ^= nums[i];
}
return r;
}
```
作法很單純，任何偶數次的都可以這樣處理。
只要一路```XOR```到底，利用自反性把位元消除，剩下的就會是多出來的那個數字的位元組態。
**重複 5 次**
```c
#include<stdio.h>
int singleNumber(int* nums, int numsSize){
if (numsSize == 1) {
return nums[0];
}
int once = 0, twice = 0, thrice = 0, quarce = 0, quince = 0;
for (size_t i = 0; i < numsSize; i++) {
quarce |= thrice & nums[i];
thrice |= twice & nums[i];
twice |= once & nums[i];
once ^= nums[i];
quince = once & twice & thrice & quarce;
once &= ~quince;
twice &= ~quince;
thrice &= ~quince;
quarce &=~quince;
}
return once;
}
int main() {
int data[] = {0,2,1,2,0,1,0,2,2,1,9,0,1,2,0,1};
printf("Ans: %d\n", singleNumber(data, sizeof(data)/sizeof(int)));
return 0;
}
```
一樣的道理，後面的變數先跟前一個處理(有點像進位)，最後處理==once==。
```c
quarce |= thrice & nums[i];
thrice |= twice & nums[i];
twice |= once & nums[i];
once ^= nums[i];
```
生成出現五次的MASK。
```c
quince = once & twice & thrice & quarce;
```
最後再消除前面各變數的狀態。
```c
once &= ~quince;
twice &= ~quince;
thrice &= ~quince;
quarce &= ~quince;
```
執行結果: 
Sign in with Wallet
Connect another wallet