2020q3 Homework2 (quiz2)
===
contribute by `Liao712148`
* 1.從新回答[第2周測驗題](https://hackmd.io/@sysprog/2020-quiz2)
###### tags: `進階電腦系統理論與實作`
### 測驗1
```cpp=
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.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 & MMM)
return false;
i += 8;
}
while (i < size) {
if (str[i] & 0x80)
return false;
i++;
}
return true;
}
```
由於128~255是擴展字元所以他們的編碼會是`10000000~11111111` 由觀察可以發現一定會是`1*******`的形式所以如果有一編碼與`0x80`(10000000)作 & 後為==True== 則可以確定他一定屬於擴展字元。
此題要求一次比較64 bits 由上述可知比對一個字元要一個`0x80`,所以只要透過與`0x8080808080808080`作&就可以知道這個字串是否有擴展字元
### 延伸問題
* 解釋為何會用到`memcpy()`
如果要一個一個byte與`0x80`檢查的話，效率會很低，所以把字串存入較大的type（uint64_t）中就可以一次檢查較多的字元。
* 討論：如果是透過`cast`直接將`char *`轉換成`uint64_t *`，將低為寬型別轉換成高位寬型別的指標，如下所示，會有什麽問題嘛？
```cpp=
uint64_t temp; /*using a bigger type to store char of str,rather than declare an array*/
memcpy(&temp,str[i],8);
```
換成
```cpp=
uint64_t *temp = (uint64_t *) str;
```
如果放在 intel x86的系統下因為硬體可以支援==unalign==的記憶體操作，我們可能就會誤認程式的正確性。但是在ARM等不支援＝＝unaligned memory access＝＝的架構上，這樣不合法的操作可能直接導致程式無法執行或產生非預期的結果。
我們可以打開`Address Sanitizer`來檢查是否有**unaligned memory access**:
```
gcc -fsanitize=alignment *.c
```
然後透過類似以下的呼叫來測試`memcpy`的版本和使用`casting`的版本。
```cpp=
char a[] = "ABCDEFGHIFKL";
is_ascii(a+1,strlen(a)-1);
```
在`casting`的版本中會得到，以下的資訊
```
runtime error: load of misaligned address 0x7ffd174c0fac for type 'uint64_t', which requires 8 byte alignment
0x7ffd174c0fac: note: pointer points here
a0 e0 b8 41 42 43 44 45 46 47 48 49 4a 4b 4c 00 00 33 89 23 50 4b 53 9c 00 00 00 00 00 00 00 00
```
使用`memcpy`版本不會遇到此問題，根據[memcpy.c](https://github.com/lattera/glibc/blob/master/string/memcpy.c)
`memcpy`可以從一個記憶體區塊拷貝資料到另一個記憶區塊，但兩個記憶體區塊不能overlap，否則是未定義行為。
當要copy的bytes數量較少（len < OP_T_THERES)會直接以byte為單位進行copy，其中（OP_T_THERES = 8 or 16），當copy 的bytes數量大時（len > OP_T_THERES）會先以byte為單位進行copy，使得**目標的記憶體區塊對齊**這樣就可能可以直接copy整個page來加速copy。
部分CPU硬體不支援對齊訪問，在非對齊的資料訪問可以使用`memcpy`，`memcpy`不存在對齊的問題，但對於device型別(Linux核心中分配記憶體時指定)的記憶體，部分架構下(如ARE64)不能使用`memcpy`的方式訪問，否則也會出現aligment fault。
==指標轉換==可能導致**alignment fault**
將低位寬型別的指標轉換為高位寬型別的指標，如：將`char *` 轉為`int *`，或將`void *`轉為結構體指標。這類操作是導致alignment fault的最主要的來源，在分析定位問題時，需要特別關注。對於出現異常卻又必須這樣使用的場景，對這類轉換後的指標進行訪問時，如果不能確認其對應的地址是對齊的，則應該使用==memcpy==訪問(memcpy方式不存在對齊問題)。另外，建議轉換後立即使用，不要將其傳遞到其他函式和模組，防止擴充套件，帶來潛在的問題。
* 思考`bool is_ascii(const char str[], size_t size)`如果size被輸入一個負數值
則size 會被轉換成一個很大的正值，會造成不當的記憶體存取。
[參考RinHizakura](https://hackmd.io/@RinHizakura/SJ5NuIANP)
[參考資料](https://www.itread01.com/content/1544492598.html)
* 將上述技巧應用於 給予一個已知長度的字串，檢測裡頭是否包含有效的英文字大小寫字母
利用測驗5的技巧就可以一次大量的分辨字串是否為英文子元大小寫。如果字母介在a~z之間的字母則`mask = 0x80`而如果字母介在A~Z之間的字母則`MASK = 0x80`
如果字串都是由大小寫英文字母組成的話,由第`16`行`mask | MASK`會得到`0x8080808080808080`
```cpp=
bool is_alpha(const char *s, size_t size)
{
if (size == 0)
return false;
size_t k = size / 8;
int i;
for(i = 0; i < k; i++) {
uint64_t chunk;
memcpy(&chunk, s + i * 8, 8);
uint64_t a = chunk + PACKED_BYTE(128 - 'a' + 0);
uint64_t A = chunk + PACKED_BYTE(128 - 'A' + 0);
uint64_t z = chunk + PACKED_BYTE(128 - 'z' - 1);
uint64_t Z = chunk + PACKED_BYTE(128 - 'Z' - 1);
uint64_t mask = (a ^ z) & PACKED_BYTE(0x80);//判斷是不是介在a～z的字母
uint64_t MASK = (A ^ Z) & PACKED_BYTE(0x80);//判斷是不是介在A～Z的字母
if((mask | MASK) == PACKED_BYTE(0x80))
return false;
}
int temp = k * 8;
while (temp < size) {
if (s[temp] < 'a' || (s[temp] > 'z' && s[temp] < 'A') || s[temp] > 'Z')
return false;
temp++;
}
return true;
}
```
* 考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集
==尚未完成==
---
### 測驗2
```cpp=
uint8_t hexchar2val(uint8_t in)
{
const uint8_t letter = in & MASK;
const uint8_t shift = (letter >> AAA) | (letter >> BBB);
return (in + shift) & 0xf;
}
```
此題的輸入可以大致分成:
1.0~9
`0x30`,`0x31`,`0x32`,...,`0x39`
0b0011==0000==,... , 0b0011==1001==
2.
a,b,c,...f,
`0x61`,`0x62`,`0x63`,...,`0x66`
0b0110==0001==,...,0b0110==0110==
3.
A,B,C,...F
`0x41`,`0x42`,`0x43`,...,`0x46`
0b0100==0001==,...,0b0100==0110==
***MASK***:
由於大小寫英文視為相同且數字不需額外處理，所以透過`& 0x40`可以將大小寫英文相同的部分取出(01000000)
***AAA，BBB***
由觀察可以發現字母的後四位元，再加上`9`即為16進位中所代表的數字，以a,A為例，對應到的16進位轉2進位是10，而`0x61`,`0x41`最後的4個bit為0001，所以只要再加上9(1001)就能得到10，故利用第4行將shift設為9(1001)
第5行透過`&0xf`可取出最後4個bit
### 延伸問題
將`hexchar2val`擴充為允許"0xFF","0xCAFEBABE","0x8BADFD"等字串輸入，且輸出對應的十進位值
```cpp=
uint64_t hexstring2val(const char str[])
{
int len = strlen(str);
uint64_t result = 0;
assert(str[0] == '0' && (str[1] == 'x' || str[1] == 'X'));
for (int i = 2;i < len; i++) {
uint64_t letter = str[i] & 0x40;
uint64_t shift = (letter >> 3) | (letter >> 6);
result = result << 4 | ((str[i] + shift) & 0xf);
}
return result;
}
```
透過了指標的走訪來實現將一個字串轉成對應的16進位的數值，要注意的是`0xCAFEBABE`其中的`0x`是此字串是要以16進位表示，所以再轉換上應該從`0x`後的字元開始轉。再利用一個64位元的空間來存放答案。
之所以可以直接按照排列順序直接存入，是因為用的是`little endian`的架構，倘若是用`big endian`的架構的話這樣直接存入會得到不同的答案。
所以應該做以下的改善
```cpp=
uint64_t hexstring2val(const char str[])
{
int len = strlen(str);
uint64_t result = 0;
assert(str[0] == '0' && (str[1] == 'x' || str[1] == 'X'));
int i = 1;
char *c = (char *) & i;
if (*c) {
for (int i = 2;i < len; i++) {
uint64_t letter = str[i] & 0x40;
uint64_t shift = (letter >> 3) | (letter >> 6);
result = result << 4 | ((str[i] + shift) & 0xf);
}
} else {
for (int i = 2;i < len; i++) {
uint64_t letter = str[i] & 0x40;
uint64_t shift = (letter >> 3) | (letter >> 6);
result = result | ((str[i] + shift) & 0xf) << (4 * (i - 2));
}
}
return result;
}
```
利用`6`,`7`來做`littel/big endian`的判斷，因為如果是`big endian`的話，`i`會以以下的方式儲存：
| address | content |
|:---------- |:--------|
| 0x0000 | 0x00 |
| 0x0001 | 0x00 |
| 0x0002 | 0x00 |
| 0x0003 | 0x01 |
`int`變量佔了4個`byte`，而`char`只佔了一個`byte`，所以執行第`7`行時，會發生只能讀取到`0x0000`的內容`（0x00）`，所以`*c`為`0`。
而如果是用`little endian`儲存的話，
| address | content |
|:---------- |:--------|
| 0x0000 | 0x01 |
| 0x0001 | 0x00 |
| 0x0002 | 0x00 |
| 0x0003 | 0x00 |
`little endian`可以藉由相同的記憶體位址`0x0000`來取得`0x01`的值，所以`*c`為`1`。
---
### 測驗3
```cpp=
const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(XXX) / (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;
}
```
此題會return一個餘數，所以可以知道quotient為除式的商，根據題目可以知道可將除是寫成
$q= \dfrac{n}{d}$ $=n\times\dfrac{\dfrac{2^N}{d}}{2^N}$...(1)
對照第6行可以知道 $N=64$ 帶回(1)可得$M$應該為$\dfrac{2^{64}}{d}$，但與第2行的定義的$M=\dfrac{2^{64}-1}{d}+1$不一樣，所以列下來要證明$M=\dfrac{2^{64}}{d}$，$M=\dfrac{2^{64}-1}{d}+1$帶入(1)後具有一樣的商式。
$q=n\times\dfrac{(\dfrac{2^{64}-1}{d}+1)}{2^{64}}$$=n\times(\dfrac{2^{64}-1}{d\times2^{64}}+\dfrac{1}{2^{64}})$$=n\times\dfrac{(2^{64}-1)}{d\times2^{64}}+\dfrac{n}{2^{64}}$
由於$n\times\dfrac{(2^{64}-1)}{d\times2^{64}}+\dfrac{n}{2^{64}}$$<n\times\dfrac{2^{64}}{d\times2^{64}}+\dfrac{n}{2^{64}}$$=\dfrac{n}{d}+\dfrac{n}{2^{64}}$
所以現在只要證明$\dfrac{n}{d}+\dfrac{n}{2^{64}}$整數部分與$\dfrac{n}{d}$的整數相同即可，==因為n,d皆是32位元的無號數所以最大值為$2^{32}-1$==
所以在餘數很接近除數時$\dfrac{2^{32}-2}{2^{32}-1}$即使再加上$\dfrac{2^{32}-1}{2^{64}}$也不會造成$\dfrac{n}{d}$的商式會增加，所以依舊是$q$。
因此$M=\dfrac{2^{64}}{d}$，$M=\dfrac{2^{64}-1}{d}+1$帶入(1)後具有一樣的商式。
答案選`0xFFFFFFFFFFFFFFFF`
#### 討論
* Q: 為什麼`N`要設成`64`?
Ans:因為我們基於運算成本的考量,而不使用浮點數的型態來儲存$\dfrac{2^{N}}{d}$ 的結，但用整數型態來儲存，會造成小數點後的數值遺失，而造成誤差變大。所以如何減少小數點後的數值遺失，是我們要著重注意的。舉以下的例子:
$9\times\dfrac{1}{7}=1.285714$(使用浮點數運算)
(使用整數來儲存)
$=9\times\dfrac{1}{7}$=$=9\times 0$=$\ 0$，$\dfrac{1}{7}=0.142857$小數點後的值會被省略，所以得到$0$
$=\dfrac{9\times\dfrac{10}{7}}{10}$$=\dfrac{9\times 1}{10}$=$\ 0.9$，$\dfrac{10}{7}=1.42857$小數點後的值會被省略，所以得到$1$
$=\dfrac{9\times\dfrac{100}{7}}{100}$$=\dfrac{9\times 14}{100}$=$\ 1.26$，$\dfrac{100}{7}=14.2857$小數點後的值會被省略，所以得到$14$
$=\dfrac{9\times\dfrac{1000}{7}}{1000}$$=\dfrac{9\times 142}{1000}$=$\ 1.278$，$\dfrac{1000}{7}=142.857$小數點後的值會被省略，所以得到$142$
可以觀察到不斷的$\times10$，可以使之前==被省略的小數變成整數==，進一步改善我們的精準度。而${2^{N}}$亦為此效果，因此`N`要大。
### 延伸問題
由 Facebook 公司所維護的 [jemalloc](https://github.com/jemalloc/jemalloc) 是個高效能的記憶體配置器 (memory allocator，即 malloc 和 free 函式對應的實作)，特別在多核多執行緒的環境有優異表現，在其原始程式碼 [include/jemalloc/internal/div.h](https://github.com/jemalloc/jemalloc/blob/dev/include/jemalloc/internal/div.h) 和 [src/div.c](https://github.com/jemalloc/jemalloc/blob/dev/src/div.c) 也運用類似的技巧，請閱讀原始程式碼，並抽離快速除法實作為獨立的程式碼，說明運作原理，也該撰寫測試程式，比較透過處理器的整數除法指令及本技巧的效能差距;
透過[src/div.c](https://github.com/jemalloc/jemalloc/blob/dev/src/div.c)的數學推導:
* 所求為$q=\dfrac{n}{d}$，其中`n,d,q`皆為整數
* 可以描述成$q=\dfrac{n}{d}$$=\dfrac{n}{d}+\left\lfloor{ \frac{r}{d} \times \frac{n}{2^k}} \right\rfloor$，其中 $r=-({2}^k)\ mod\ d$且$\left\lfloor{ \frac{r}{d} \times \frac{n}{2^k}} \right\rfloor=0$，因為$r$是$d$的餘數，所以$\dfrac{r}{d}<1$成立，而n的範圍是在$0\leq n\leq 2^{32}-1$，所以$\dfrac{n}{2^{k}}\leq1$成立，因此$\frac{r}{d} \times \frac{n}{2^k}<1$，故$\left\lfloor{ \frac{r}{d} \times \frac{n}{2^k}} \right\rfloor=0$成立
* 由於$\dfrac{n}{d}$為整除，所以$\dfrac{n}{d}+\left\lfloor{ \frac{r}{d} \times \frac{n}{2^k}} \right\rfloor$$=$$\left\lfloor{\dfrac{n}{d}+ \frac{r}{d} \times \frac{n}{2^k}} \right\rfloor$，得到$q=\dfrac{n}{d}=$$\left\lfloor{\dfrac{n}{d}+ \frac{r}{d} \times \frac{n}{2^k}} \right\rfloor$
* 整理可得$q=\dfrac{n}{d}=$$\left\lfloor{\dfrac{2^{k}}{d}\times\dfrac{n}{2^{k}}+ \frac{r}{d} \times \frac{n}{2^k}} \right\rfloor$$=$$\left\lfloor{(\dfrac{2^{k}+r}{d}) \times \frac{n}{2^k}} \right\rfloor$，由於$r$是$d$的餘數所以可以推得$\left\lfloor{(\dfrac{2^{k}+r}{d}) \times \frac{n}{2^k}} \right\rfloor$$=$ $\left\lfloor{\left\lceil\frac{2^k}{d}\right\rceil \times \frac{n}{2^k}} \right\rfloor$
* $q=\dfrac{n}{d}=$ $\left\lfloor{\left\lceil\frac{2^k}{d}\right\rceil \times \frac{n}{2^k}} \right\rfloor$
`div_init`
```cpp=
void
div_init(div_info_t *div_info, size_t d) {
/* Nonsensical. */
assert(d != 0);
/*
* This would make the value of magic too high to fit into a uint32_t
* (we would want magic = 2^32 exactly). This would mess with code gen
* on 32-bit machines.
*/
assert(d != 1);
uint64_t two_to_k = ((uint64_t)1 << 32);
uint32_t magic = (uint32_t)(two_to_k / d);
/*
* We want magic = ceil(2^k / d), but C gives us floor. We have to
* increment it unless the result was exact (i.e. unless d is a power of
* two).
*/
if (two_to_k % d != 0) {
magic++;
}
div_info->magic = magic;
#ifdef JEMALLOC_DEBUG
div_info->d = d;
#endif
}
```
依照上面的推導加上註解可以了解
第`4,10`行:判斷除數是否為`0`或`1`，否則$\dfrac{r}{d}<1$不成立。
第`12`行:產生$2^{32}$
第`13,20`行:產生$\lceil \frac{2^{32}}{d} \rceil$
`div_compute`
```cpp=
static inline size_t
div_compute(div_info_t *div_info, size_t n) {
assert(n <= (uint32_t)-1);
/*
* This generates, e.g. mov; imul; shr on x86-64. On a 32-bit machine,
* the compilers I tried were all smart enough to turn this into the
* appropriate "get the high 32 bits of the result of a multiply" (e.g.
* mul; mov edx eax; on x86, umull on arm, etc.).
*/
size_t i = ((uint64_t)n * (uint64_t)div_info->magic) >> 32;
#ifdef JEMALLOC_DEBUG
assert(i * div_info->d == n);
#endif
return i;
}
```
第`3`行:`n`不能超過$2^{32}-1$
第`10`行:計算$\dfrac{n\times\lceil \frac{2^{32}}{d} \rceil}{2^{32}}$
因為是用`int`型態儲存，所以小數會被捨棄，因此整體可以理解為$\left\lfloor{\left\lceil\frac{2^k}{d}\right\rceil \times \frac{n}{2^k}} \right\rfloor$
### 測驗4
```cpp=
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
此題參考<`quantabase13`>
因為$D=3$所以如果式被除數可以$D$整除的話，則$n=3k$反之則式$n=3k+1$ or $n=3k+2$
，其中$k$為非負整數。並且已知$M=0x5555555555555556$，而$M-1=0x5555555555555555$
所以$3\times(M-1)=0xFFFFFFFFFFFFFFFF$，即將溢位。而溢位後會`wraparound`。所以$3\times(M-1)+1=0x0000000000000000$，利用這點可以進行化簡。
$n=3k:\ n\times M=3kM=$==$3k\times(M-1)+k$==$+2k=$==$0$==$+2k$
$n=3k+1:\ n\times M=3kM+M=$==$3k\times(M-1)+k$==$+2k+M=$==$0$==$+2k+M$
$n=3k+2:\ n\times M=3kM+2M=$==$3k\times(M-1)+k$==$+2k+2M=$==$0$==$+2k+2M$
將$k=0$代入上述3個情況可以得到
$n=3k:$ $n\times M$最小值為$0$
$n=3k+1:$ $n\times M$最小值為$M$==(不能整除)==
$n=3k+2:$ $n\times M$最小值為$2M$==(不能整除)==
回到題目:$n\times M<=YYY$代表整除，反之$n\times M>YYY$則不能整除
由上推得$2M ,M>YYY$，所以$YYY$要選擇$M-1$
##### 整理之後的概念
$\frac{2^{64}-1}{d}=qMAX+\frac{rMAX}{d}$ ，$M =qMAX+1$且 $1\leq d\leq 2^{32}-1$，設$\frac{n}{d}=q+\frac{r}{d}...(1)$
$n\times M$ 代入(1)式
$=(q+\frac{r}{d})\times M$
$=q\times d\times M+r\times M$
將$d\times M=d\times qMAX+d=2^{64}-1-rMAX+d$代入上式
$=q\times (d-1-rMAX)+r\times M...(2)$，因為$\frac{n}{d}$要是整除，所以$r$要是$0$
因此若要整除，則$n\times M$會比$r=1$代入(2)式中來的小，意味著$r=0$
$n\times M<q\times (d-1-rMAX)+1\times M$
其中$0\leq q\times (d-1-rMAX)\leq (2^{32}-1)\times (2^{32}-1)$
故$n\times M\leq M-1$
### 測驗5
```cpp=
#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);
}
```
此題的目的是要將一個string中的大寫字母轉換成小寫，根據題目一可以知道，我們會利用`0x8080808080808080`來一次檢測64個bit中有沒有擴充字元，此題依據此一想法選擇**VV1**
因該為`0x80`，並透過&(0xff)，取出最後2個byte，然後用`*0x0101010101010101u`將`0x80`擴充成我們要的`0x8080808080808080`。
==藉由`('a'^'')`可得'A'，和`('A'^'')`可得'a'==
我們知道可以透過把字元和' '作XOR得到小寫字元，所以推測mask應該會是一個`space`，而我們可以透過`0x80>>2`得到' '，所以`(A ^ Z) & PACKED_BYTE(VV4)`應該要是`0x80`故**VV4**要是`0x80`，因為中間有一個`&`所以`(A^Z)`要是128以上的數才行否則`mask`為0。
由`A^Z`回推得到(128-'A'+VV2+*chunk)^(128-'Z'+VV3+*chunk)這左右兩邊的運算子應該要是一邊>128，一邊<128。否則`(A^Z)`不會>=128，再加上 *chunk是A~Z 的字元所以大小界在65~90
。因此會是(128-'A'+VV2+*chunk)>=128而且(128-'Z'+VV3+*chunk)<128。
故**VV2**=0,**VV3**=-1。
### 延伸問題
將前述測試程式 main 函式的 char str[] 更換為 char *str，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為
根據[C語言規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
>EXAMPLE 8 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.
`char str[]`是透過copy `string literal` 來對一個char array object來作初始化
`char *str`則是將一個`pointer to char`指向`array of char`其中的元素是`string iteral`，所以透過str去更改array的內容是==未定義==的
根據[C語言規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
>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.66) 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
所以`string literal`是一個static的記憶體配置，如果要去更改是==未定義==的行為
---
### 測驗6
```cpp=
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;
}
```
***需要先理解XOR的特性:***
* 具有交換性
`A^B==B^A`
* 與0作XOR會得到自己
`A^0==A`
* 與自己作XOR會得到0
`A^A==0`
此題的原理參照[link text](https://blog.csdn.net/karen0310/article/details/78226261)概念是用bit來記錄出現的次數，透過將數字轉換成2進位制後，利用lower來存放在各個bit上出現1次**1**的位置，倘若同個bit出現2次的**1**，就將出現兩次的bit位置用higher存放起來。
以下透過例子來說明:
[2,2,3,2]
L:000,H:0000
L=0000^0010=0010//右二bit出現1次**1**
L=0010&1111=0010 //確保在higher中沒有存放相通位置的**1**如果已經存放過的話代表這個位置的**1**之前已經出現過2次了，則應該要把這個位置上的1消除，因為已經出現2+1並非是我們要的答案
H=0000^0010=0010//檢查此數字是不是之前出現過
H=0010&1101=0000//紀錄是不是已經出現了2次
以此類推
### 延伸問題
請撰寫不同上述的程式碼，並確保在 [LeetCode 137. Single Number II](https://leetcode.com/problems/single-number-ii/")執行結果正確且不超時
紀錄每個數字各個`bit`出現的次數，因為出現3次的數一定可以被3整除。所以沒被整除的數字即為我們所由。
```cpp=
int singleNumber(int* nums, int numsSize){
int single = 0;
for (int i=0; i < 32; i++) {
int temp = 0;
for (int j = 0; j < numsSize; j++) {
temp += (nums[j] >> i & 1);
}
if (temp % 3)
single += (unsigned int) 1 << i;
}
return single;
}
```
Sign in with Wallet
Connect another wallet