# 2020q3 Homework2 (quiz2)
contributed by < `ptzling310` >
## 事前作業
- [ ] 何為 ASCII？
- [ ] 數值系統
- [ ] bitwise 操作
- [ ] C99 ： array object, string literal
## ASCII (American Standard Code for Information Interchange) table
- 字元集及其編碼。
- ASCII 碼有7位碼和8位碼兩種形式。
- ASCII 表格
| 範圍 | 代表 |
| -------- | -------- | -------- |
| 第0～32號及第127號(共34個) | 控制字元或通訊專用字元 |
| 第33～126號(共94個) | 字元(含標點符號) |
| 第48～57號 | 字元：0～9 |
| 第65～90號|字元：26個大寫英文字母|
| 第97～122號|字元：26個小寫英文字母
- Extended Character Set ： 第 128～255 號為擴展字元
## 測驗 `1`：判斷指定的記憶體範圍內是否全是有效的 ASCII 字元
### 版本一：一次比較一字元
- ASCII 碼的取值範圍是 ==0~127==
```c=
#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;
}
```
- 參數
1. `const char str[]`：第一個參數為==開頭的記憶體地址==，前面加上 `const` 表示該參數不可再變動。
> 我的問題：
> str[ ] 長怎樣？他是一個儲存 char 的 array。
> 所以 str[ ] = {"c" , " " , "*", "w" }
> str[0] = "c", str[1] = " " ...... 而一個 `char` 大小 = 8 bits 。
:::danger
翻閱 C99 規格書，理解上述 array object, string literal 和有效的生命週期等議題，不要臆測
:notes: jserv
:::
::: warning
TODO： study C99 (°ཀ°) ！
:::
2. `size_t size` ：記憶體範圍
- 程式
1. `str[i]` 所儲存的會是一個 `char` 的字，又每個字可以轉成一個對應的數字，故可以用來和`0x80`做運算。
2. `0x80` 的含義？
`0x80` 是(`80`)~16~ 指 (`1000 0000`)~2~，所以將`str[i]` 與 (`1000 0000`)~2~ 做 `AND` 的計算。所以要 `str[i]` **的二進制**的最左 bit為 1 才會 `if` 成立。 又(`1000 0000`)~2~ = (128)~10~。 都轉為十進制來看，可理解成 `(unsigned) str[i] >= 128`。
> 假設比對 "A" 是否屬於 ASCII，則我們要先知道 "A" 轉為數字對應到 (`0x41`)~16~ = (`1000001`)~2~。 再來做 **(`1000 0000`)~2~ AND (`0100 0001`)~2~**
> 0x80 ： 1000 0000
> 0x41 ： 0100 0001
> AND結果：0000 0000
> 所以 return true， "A" 為 ASCII
3. 由於這個版本是一個字元逐一比對，故效率較低，為了改善這個問題，所以有了第二個版本去嘗試一次比對 64 位元的資料。
> bit：位元
> byte：位元組 = 8 bits
> word：字組 = 2 bytes = 16 bits
### 版本二：一次比對 64 位元( bits )
```c=1
#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 & 0x8080808080808080 )
return false;
i += 8;
}
while (i < size) {
if (str[i] & 0x80)
return false;
i++;
}
return true;
}
```
```c=11
while ((i + 8) <= size)
```
一次要比較 8 個 char，用 `while` 來控制。
```c=12
uint64_t payload;
memcpy(&payload, str + i, 8);
```
新增一個`uint64_t` 的變數 `payload`，將 `str` 中的8個 char 複製到 payload 所在的記憶體位址。 所以`payload` 所存的會是複製過來的 char。
```c=14
if (payload & 0x8080808080808080 )
return false;
```
將 `payload` 與 `0x8080808080808080` 做 `AND` 運算，為何是`0x8080808080808080`呢？從版本一可以知道一次比對1個字元需要使用一個 `80` ，比對8個字元則要使用 8 個 `80`。
- `uint64_t` 為何？
不只有 `uint64_t` ，亦有`uint32_t`, `uint16_t`, `uint8_t`。後面的 `_t` 代表他們是透過 `typedef` 定義出來的。
[cstdint.hpp](https://github.com/boostorg/config/blob/master/include/boost/cstdint.hpp)
```c
typedef unsigned long uint64_t;
```
所以 `uint64_t` 的範圍：0 ~ $2 ^ {64}$ - 1 (0x0000 0000 0000 0000~0xFFFF FFFF FFFF FFFF)~16~，轉乘二進制後會有 64 個 bits 。
#### ==問題一==：為何使用memcpy()？
- 先理解 `memcpy()` 的功能
The memcpy() function **copies** n bytes **from memory area** src to memory
area dest. **The memory areas should not overlap**. Use memmove(3) if the
memory areas do overlap.
```c
#include <string.h>
void *memcpy(void *str1, const void *str2, size_t n)
```
`void *str1`：destination
`const void *str2`：source
`size_t n`：要複製的字元數
範例：
```c=
#include <stdio.h>
#include <string.h> //要使用 memcpy()
int main ()
{
const char src[50] = "http://www.gitbook.net/html";
char dest[50];
printf("Before memcpy dest = %s", dest);
//"+1"是要複製'/0'
memcpy(dest, src, strlen(src)+1);
printf("After memcpy dest = %s", dest);
return(0);
}
```
```c
Before memcpy dest =
After memcpy dest = http://www.gitbook.net/html
```
- 再了解**data alignment**
- 定義：data 的 address 可以公平的被 1, 2, 4, 8,這些數字整除。
- `memcpy()` 與 aligement 的關係： `memcpy()` 在複製資料前會先檢查是否 **word aligned** ，有利於 Single Instruction Multiple Data (SIMD, 一個指令可同時處理多筆資料)。但在 `memcpy()` 使用上必須注意在不同處理器上未必皆可正確執行，例如： ARM 。
- 參考：
1. [PCMan](https://www.facebook.com/pcman.im/posts/1623916640981340/)
2. [ARMCC: problems with memcpy (alignment exceptions)](https://stackoverflow.com/questions/24883410/armcc-problems-with-memcpy-alignment-exceptions)
3. [我是軟體那些處理器教我的事](https://coscup.org/2008/files/trap-in-processors.pdf)
#### ==問題二==：將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
[github_quiz2_test1](https://github.com/ptzling310/quiz2/blob/master/test1.c)
```c=
#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)
bool is_alpha(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' + 0 );
uint64_t Z = payload + PACKED_BYTE(128 - 'Z' + (-1));
uint64_t a = payload + PACKED_BYTE(128 - 'a' + 0);
uint64_t z = payload + PACKED_BYTE(128 - 'z' + (-1));
uint64_t mask_up = ((A ^ Z) & PACKED_BYTE(0x80));
uint64_t mask_low = ((a ^ z) & PACKED_BYTE(0x80));
if(mask_up == PACKED_BYTE(0x00) && mask_low== PACKED_BYTE(0x00))
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;
}
```
```
a [] = {testING} #will return true
b[]= {"@@deF"}; #will return false
```
利用 測驗 `5` 判斷字母是否屬於 '`A`'~'`Z`' 之間來完成此題。
若該 char 為大寫英文，則 `mask_up` 會為 `0x80`、 `mask_low` 會為 `0x00`。
若該 char 為小寫英文，則 `mask_low` 會為 `0x80`、 `mask_up` 會為 `0x00`。
若該 char 非英文字母，則 `mask_low` == `mask_up` == `0x00`。
#### ==問題三==：承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對
---------------------------
## 測驗 `2`： 十六進制轉十進制
```c=
uint8_t hexchar2val(uint8_t in)
{
const uint8_t letter = in & 0x40; //挑出0~9
const uint8_t shift = (letter >> 3) | (letter >> 6);
return (in + shift) & 0xf;
}
```
`0xf` = (0000 1111)~2~ ，再取 `&` 表示保留最後 4 個 bits。
::: spoiler ASCII 表
| input char|ASCII - 10進制 |ASCII - 16進制 | b~7~ |b~6~ |b~5~ |b~4~ |b~3~ |b~2~ |b~1~ |b~0~ | output |
|--------| -------- | -------- |-------- |-------- |-------- |-------- |-------- |-------- | -------- |-------- |-------- |
|'`0`' | 48 | 0x30 |0 |0|1|1|0|0|0|0|0
|'`1`' | 49 | 0x31 |0 |0|1|1|0|0|0|1|1
|'`2`' | 50 | 0x32 |0 |0|1|1|0|0|1|0|2
|'`3`' | 51 | 0x33 |0 |0|1|1|0|0|1|1|3
|'`9`' | 57 | 0x3A |0 |0|1|1|1|0|0|1|4
|... | ... | ... |... |...|...|...|...|...|...|...|
|'`A`' | 65 | 0x41 |0 |1|0|0|0|0|0|1|10
|'`B`' | 66 | 0x42 |0 |1|0|0|0|0|1|0|11
|'`F`' | 70 | 0x46 |0 |1|0|0|0|1|1|0|15
|... | ... | ... |... |...|...|...|...|...|...|...|
|'`a`' | 97 | 0x61 |0 |1|1|0|0|0|0|1|10
|'`b`' | 98 | 0x62 |0 |1|1|0|0|0|1|0|11
|'`f`' | 102 | 0x66 |0 |1|1|0|0|1|1|0|15
:::
- 觀察 '`0`' ~ '`9`'
- 值就是最左四個 bits
- 和大寫英文、小寫英文的區別在於 b~6~ 這個bit
- 觀察 '`A`' ~ '`F`' 以及 '`a`' ~ '`f`'
- 相同字母之 b~3~ b~2~ b~1~ b~0~ 相同
- 大小寫字母差別在 b~5~
- 再觀察最後 4 個 bits (b~3~ b~2~ b~1~ b~0~)，會發現最後與真正要 return 的值差 9！所以如果是屬於英文字母，則將最後 4 個 bits 取出再加上 9 = (1001)~2~。
| char | b~3~ b~2~ b~1~ b~0~ | b~3~ b~2~ b~1~ b~0~之十進制值 | 想轉換成的值 | 差值|
| -------- | -------- | -------- |-------- |-------- |
| A or a | 0001 | 1 |10 |9|
| B or b | 0010 | 2 |11 |9|
| ... | ... | ... |... |...|
| F or f | 0110 | 6 |15 |9|
```
in = (0011 0001) = 1
letter = in & 0x40
= (0011 0001) & (0100 0000)
= (0000 0000)
由 0x40 可以過濾出 b6 這個 bit，如果是 0 代表是數字，是 1 代表是英文字母。
shift = ( letter>>3 ) | (letter >> 6)
= (0000 0000) | (0000 0000)
= (0000 0000)
in + shift = (0011 0001) + (0000 0000)
= (0011 0001)
(in + shift) & 0xf = (0011 0001) & (0000 1111)
= (0000 0001)
= 1
```
- 流程
1. 先區分數字以及英文字母。
2. 是英文字母的，要再加上 9 = (1001)~2~ 。
3. 保留最後四個 bit ，其值即為所求。
#### ==問題一==：解釋上述程式的運作原理
```c
typedef unsigned char uint8_t;
```
所以 `uint8_t` 是一個 `8 bits` 的 `char`。
```c=3
const uint8_t letter = in & 0x40;
```
利用 `0x40` = (0100 0000)~2~ 抓出 b~6~
```c=4
const uint8_t shift = (letter >> 3) | (letter >> 6);
```
`shift` 用來做到加上 9 = (1001)~2~ 這件事，如果 letter 非 0 ，就可以利用 letter 位移組合出 (0000 1001)~2~ ； 若 letter 則此值會為 (0000 0000)~2~ 。
```c=5
return (in + shift) & 0xf;
```
`in + shift` 就是在補 9 ，因為只保留最後 4 個 bits ，所以再和 `0xf` = (0000 1111)~2~ 取 `&` 運算，則前面的 4 個 bits 一定會被清成 (0000)~2~。
#### ==問題二==：將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值
[Github_quiz2_test2](https://github.com/ptzling310/quiz2/blob/master/test2.c)
i 從 2 開始是為了要跳過 "0x" 的部分。
這裡是一個 byte 轉換，因為 1 byte = 4 bits，所以要 `<<4` 。
```c=
uint64_t hexchar2val(const char str[])
{
uint64_t result = 0 ;
int i=0;
for(int i = 2 ; i < strlen(str) ; i++){
const uint8_t letter = str[i]& 0x40;
const uint8_t shift = (letter >> 3 ) | (letter >> 6);
result = (result << 4) | ( (str[i]+shift)&0xf);
}
return result;
}
```
---------------------------
## 測驗 `3`： 快速除法，回傳 `n mod 3`
```c=
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;
}
```
:::info
為何要 __uint128_t
因為在 intel 處理器上，會使用到 128 位元。
:::
`uint32_t D = 3`，D 是一個 32 bits 的 unsigned integer，給定為3。
`uint64_t M`，M 是一個 64 bits 的 unsigned integer。
`uint32_t n` ，傳入參數是一個 32 bits 的 unsigned integer，為 n 。
`uint64_t quotient`，商數是 64 buts 的 unsigned integer。
- UINTN_C(value) 把無符號整型值 value 擴展以適應數據類型 uint_leastN_t。
#### ==問題一==：解釋上述程式的運作原理
- 先以答題的方向來來看：
從 `return n - quotient * D` 推， quotient 即為 $\dfrac{n}{d}$ 的整數部分 $= n \times \dfrac{ \dfrac{2^N}{d} }{2^N}$，再依照程式中 `quotient` 的算法，$\dfrac{n}{d} = n \times \dfrac{ \dfrac{2^N}{d} }{2^N} = M \times n \times \dfrac{1}{2^{64}}$。
對應來看：
$N = 64$ 以及 $M=\dfrac{2^{64}}{d}$。
回到在 line 2 我們如何定義 M：
`#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1))`也就是$M =\dfrac{xxx}{d}+1 = \dfrac{xxx+d}{d}$，所以$xxx+1 ≈2^{64}$，最終我們會選擇`0xFFFFFFFFFFFFFFFF`。
- 再來從數學的角度來看：
:::warning
TODO 數學部分
:::
#### ==問題二==：閱讀[div.h](https://github.com/jemalloc/jemalloc/blob/dev/include/jemalloc/internal/div.h) 及 [div.c](https://github.com/jemalloc/jemalloc/blob/dev/src/div.c) 並且抽離快速除法部分為獨立程式，比較透過處理器的整數除法指令及本技巧的效能差距以及理解。
假設：$n=q\times d$ (可整除)
\begin{split}
\lfloor \lceil \dfrac{2^k}{d} \rceil \times \dfrac{n}{2^k} \rfloor
&= \lfloor \dfrac{2^k+r}{d} \times \dfrac{n}{2^k} \rfloor …(1)\\
&= \lfloor \dfrac{2^k}{d} \times \dfrac{n}{2^k} + \dfrac{r}{d} \times \dfrac{n}{2^k} \rfloor …(2)\\
&= \lfloor \dfrac{n}{d} + \dfrac{r}{d} \times \dfrac{n}{2^k} \rfloor …(3)\\
&= \dfrac{n}{d} + \lfloor \dfrac{r}{d} \times \dfrac{n}{2^k} \rfloor …(4)
\end{split}
$(1)$ $r = {(-2)^k} \quad mod \quad d$
$(2)$ 將 $\dfrac{n}{2^k}$ 乘入 $\dfrac{2^k+r}{d}$
$(3)$ 提 $\dfrac{n}{d}$
$(4)$ 因為 $\dfrac{n}{d}$ 為整數，小數部分為 $0$
當 $r < d$ ，則 $\dfrac{r}{d} < 1$，再假設 $\dfrac{n}{2^k}< 1$
則$\dfrac{r}{d}\times\dfrac{n}{2^k}<1$，最後 $\dfrac{n}{d} + \lfloor \dfrac{r}{d} \times \dfrac{n}{2^k} \rfloor = \dfrac{n}{d}$
如何使 $\dfrac{n}{2^k}< 1$ 成立呢，這邊做法是只要 $k$ 夠大即可，所以取 $k=32$ 來只這個條件成立。
---------------------------
## 測驗 `4`： 判斷某個數值能否被指定的除數所整除
```c=
bool divisible(uint32_t n)
{
return n * M <= M - 1;
}
```
已知：
1. `D = 3`
2. `M = 0x5555555555555556`
n 可分類為三種可能： n % 3 = 0； n % 3 = 1 ； n % 3 = 2。
可以記錄為 n = {3k , 3k+1 , 3k+2 } ，k 為 $\ge0$ 之正整數。
##### case 1： n = 3k
`n * M` = 3k * M = 3k * (0x5...5 + 1) = k * ( 0xf...f + 3) = 2k
##### case 2： n = 3k + 1
`n * M` = (3k+1) * M = 3km + M = 2k + M
##### case 3： n = 3k + 2
`n * M` = (3k+2) * M = 3km + 2M = 2k + 2M
觀察 3 個 case ，會發現只有 case 1 中 沒有 `M` ，
所以 n * M < M 成立，則可被整除。又因為程式碼內使用的是 `<=` 所以才選擇 `M-1`。
---------------------------
## 測驗 `5`： 將字串的的英文字母全改為小寫
[ASCII Code - The extended ASCII table](https://www.ascii-code.com/)
### 版本一：一次比較一字元
```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]);
}
}
```
- tolower()：將字串轉乘小寫
```c
#include <ctype.h>
int tolower(int c);
```
```c=7
if (s[j] >= 'A' && s[j] <= 'Z')
s[j] ^= 1 << 5;
```
此段處理 `'A'` ~ `'Z'` 之間的字母，將其移到 `'a'` ~ `'z'` 的部分就好。
我們回頭看 測驗`2` 中的 ASCII 表：
| input char|ASCII - 10進制 |ASCII - 16進制 | b~7~ |b~6~ |b~5~ |b~4~ |b~3~ |b~2~ |b~1~ |b~0~ |
|--------| -------- | -------- |-------- |-------- |-------- |-------- |-------- |-------- | -------- |-------- |
|'`A`' | 65 | 0x41 |0 |1|0|0|0|0|0|1|
|'`a`' | 97 | 0x61 |0 |1|1|0|0|0|0|1|
所以 `'A'` → `'a'` 只要在 b~5~ 補上 bit `1`。
```c=9
else if ((unsigned) s[j] >= '\x7f') /* extended ASCII */
s[j] = tolower(s[j]);
```
`'\x7f'` 是對應到 ASCII 中的 127 這個，所以就是 >127 (超出 ASCII 編碼範圍)，則使用 `tolower()` 來轉為小寫。
### 版本二：一次比對 64 位元( bits )
```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(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) & (0xff)` 是 b 與 (0...0 1111 1111)~2~ 做 `AND` 運算，也就是只保留最後 8 個 bits。 在呈上 `0x0101010101010101u` 就會把剛剛所算之結果複製 8 次。
> b = (1111...1111 1010 1111)
> b and (0xff) = (0000...0000 1010 1111)
> ( b and (0xff) ) * (0x0101010101010101u) = (1010 1111 1010 1111 .... 1010 1111)
#### ==問題一==：解釋上述程式的原理
```c=10
size_t k = n / 8;
```
用 k 來紀錄要比較字串的次數，因為每次都 8 bytes 比，所以 `/8`。
```c=11
for (size_t i = 0; i < k; i++, s += 8)
```
只要我還沒做到所需之比較次數，就會執行 for 迴圈以內的事。
```c=13
if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */
```
去觀察 ASCII 表，我們將所有的值都轉成二進制來看，那麼從共同特點就是，b~7~ (最左 bit) 皆為 `0`。 所以這行要用來篩選是不是 ASCII 就是用 (`1000 0000`)~2~ = `0x80` 來將 b~7~ 單獨抓出來看， 如果 b~7~ 是 1 ，則必不屬 ASCII 。
同版本一，我們也分成為`'A'`~`'Z'` 的部分以及其他。
```c=16
uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2;
*chunk ^= mask;
```
先做 `%` 後 `>>`。
回推：
1. Line 17 是為了轉換為小寫，所以要將 b~6~ 設為 1 ，所以 mask 應為 (`0010 0000 ... 0010 0000`)~2~。
2. `(0010 0000 ... 0010 0000)`~2~ 為 line 16 之結果，先將位移還原(也就是做 `<<2`)得：
`(A ^ Z) & PACKED_BYTE(VV4))` = `(1000 0000 ... 1000 0000)`~2~。
3. 為了達到上述結果，`PACKED_BYTE(VV4)` 應是用來修正 `(A ^ Z)` 的結果， 所以 `PACKED_BYTE(VV4)` 應為 (`1000 0000 ... 1000 0000`)~2~ = `0x80...80`。 VV4 為 `0x80` 。
4. `(A ^ Z)` 之結果也必為(`1xxx xxxx .... 1xxx xxxx`)~2~(否則`&PACKED_BYTE(0x80)`後，b~7~ 無法為 1 )，為了使 `(A ^ Z)` 的b~7~ 為 1，`A` 與 `Z` 的 b~7~ 必為相反，如此做完 `XOR` 後， b~7~ 才會為 1。
```c=14
uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2);
uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3);
```
假設一個 char 他是落在 '`A`'~'`Z`' 之間，則該 char - '`A`' + 128 + VV2 應該 `>=128` ； 以及該 char - '`Z`' + 128 + VV3 應該 `< 128`
:::warning
為何 char - ‘Z’ + 128 + VV3 不能 <= 128 呢？
假設今天將 char 取 'Z' 好了，那麼：
char - '`A`' + 128 = 95-65+128 = 158 >= 128
則 A 會為 (1001 1110)~2~
char - '`Z`' + 128 = 128
則 Z 會為 ( 1000 0000 )~2~
再將 `(A^Z)` = (0001 1110 )~2~ ，那麼就不為第 4 點所要求的(1xxx xxxx)~2~ ，所以我必須要確認 Z 值不能為 128
:::
根據上述 VV2 = 0 ； VV3 = (-1) 。
#### ==問題二==：main 函式的 char str[] 更換為 char *str，會發生什麼事？
>Segmentation fault (core dumped)
`char str[]` 會回傳陣列；而`char *str` 是一個指標。
>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.==
---------------------------
## 測驗 `6`： LeetCode 137. Single Number II: 找出只出現 1 次的 element
```c=
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;
}
```
- 複習一下 `XOR` 的概念
```
1. 和自己 XOR 是 0
a ^ a = 0
2. 和 0 XOR 是 自己
a ^ 0 = 0
3. 交換律
a ^ b = b ^ a
4. 結合律
(a ^ b) ^ c = a ^ (b ^ c) = a ^ (c ^ b) = a ^ c ^ b
```
- LeetCode 136. Single Number
Every element appears **two** times except for one.
```c=
int singleNumber(int *nums, int numsSize)
{
int count = 0;
for(int i=0;i<numsSize;i++){
count ^= nums[i];
}
return count;
}
```
解釋
```
假設一個 int array = [1 , 2 , 3 , 4 , 1 ,2 ,3]
則 count 即為：
1 ^ 2 ^ 3 ^ 4 ^ 1 ^ 2 ^ 3
再依照交換律
1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 3 ^ 4
再依照結合律
(1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 3) ^ 4
又因為 a ^ a = 0 ，故
0 ^ 0 ^ 0 ^ 4 = 4
所以 count = 4，代表 4 因為沒執行兩次的 XOR 所以沒有被消除。
```
#### ==問題一==：解釋上述程式的原理
- 回到 LeetCode 137. Single Number
Every element appears **three** times except for one.
承 LeetCode 136. Single Number 概念，想要創造一組計算，使得 a ? a ? a = 0 ，這樣子未做到 3 次的 number 會留下。欲產生 `00 → 01 → 10 → 00` 的這個運算。
```graphviz
digraph graphname{
rankdir="LR";
00 [label="00",shape = circle]
01 [label="01",shape = circle]
10 [label="10",shape = circle]
10 [label="10",shape = circle]
Init[label="Initial",shape=plaintext]
00->01[label="1"]
00->00[label="0"]
01->10[label="1"]
01->01[label="0"]
10->00[label="1"]
10->10[label="0"]
Init->00
}
```
為了變更這兩個值，我們利用 heigher 以及 low 設定。
當某數第一次出現時，會被加在 lower 中，若出現第二次時，lower 中會扣除，並且加在 heigher 中。當第三次出現時，就會從 heigher 中刪除。
當 b~n~ 出現一次時， b~n~ 在 lower 中會設為 1 ； 當 b~n~ 出現第二次時， b~n~ 在 lower 會設為 0 且在 higher 中設為 1 ； 當 b~n~ 出現第三次時， b~n~ 在 higher 會設為 0。
#### ==問題二==：請撰寫不同上述的程式碼
#### ==問題三==：將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼
## 時間表
- [x] 2020/9/21 測驗 `1` 程式理解
- [x] 2020/9/22 測驗 `2` 程式理解
- [x] 2020/9/23 測驗 `3` 程式理解、影片
- [x] 2020/9/24 測驗 `5` 程式理解
- [x] 2020/9/26 測驗 `6` 、`4` 程式理解、影片
- [x] 2020/9/27 測驗 `1` 延伸問題二 、 測驗 `2` 延伸問題 (到作業截止時間)
- [ ] 2020/9
###### tags: `sysprog2020`
Sign in with Wallet
Connect another wallet