# 2020q3 Homework2 (quiz2)
contributed by < `shauming1020` >
###### tags: `homework`
## 測驗1
```c=
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;
}
```
### 1. 解釋上述程式的運作原理，特別是為何用到 memcpy 呢？
- 一個 ASCII 字元開頭的 bit 為 0，可利用 mask 0x80 (0b10000000) 直接與一個字元做比較，原第一段程式碼 ```if (str[i] & 0x80) /* i.e. (unsigned) str[i] >= 128 */``` 逐一**比較 1 個字元 （8-bits）**
- 上述程式碼改採用一次**比較 8 個字元 （64-bits）** 來判斷，因此可以很直觀的得到 **mask MMM 為 0x8080808080808080***
- 優化的 memcpy 算法會 data alignment，加速 cpu 運算
https://www.embedded.com/optimizing-memcpy-improves-speed/
i = 0, str + i:
| Address | 1 byte | Char |
| -------- | -------- | -------- |
| 0x56440dc9e9a0 | 0100 0001 | A |
| 0x56440dc9e9a1 | 0100 0010 | B |
| ...| ...| ...|
| 0x56440dc9e9a7 | 0100 1000 | H |
i = 8, str + i:
| Address | 1 byte | Char |
| -------- | -------- | -------- |
| 0x56440dc9e9a8 | 0100 0001 | A |
| 0x56440dc9e9a9 | 0100 0010 | B |
| ...| ...| ...|
| 0x56440dc9e9af | 0100 1000 | H |
payload
| 0100 1000 0100 0111 ... 0100 0010 0100 0001 |
| --- |
Mask (MMM)
| 1000 0000 1000 0000 ... 1000 1000 1000 1000 |
| --- |
### 2.將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
- 逐一字節的判斷
```c=
bool is_alpha(const char str[], size_t size)
{
if (size == 0)
return false;
for (int i = 0; i < size; i++) {
int diff_A = str[i] - 'A', diff_a = str[i] - 'a';
if ((0 <= diff_A && diff_A < 26) ||
(0 <= diff_a && diff_a < 26))
return true;
}
return false;
}
```
### 3. 承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對
---
## 測驗2
### 1.解釋上述程式的運作原理
```c=
uint8_t hexchar2val(uint8_t in)
{
const uint8_t letter = in & MASK;
const uint8_t shift = (letter >> AAA) | (letter >> BBB);
return (in + shift) & 0xf;
}
```
已知 in 一定隸屬於 '0', '1', '2', …, '9' 及 'a', 'b', 'c', …, 'f' (小寫) 及 'A', 'B', 'C', …, 'F' (大寫) 這些字元。預期 hexchar2val('F') 和 hexchar2val('f') 回傳 15，且 hexchar2val('0') 回傳 0，其他輸入都有對應的數值。
``` #3 const uint8_t letter = in & MASK; ```
- 觀察字母 'A', 'a' 的 ASCII，可以發現兩者皆**大於 0x0100_0000 (0x40)**，因此可以用 Mask 0x40 來**偵測該 in 是否為字母**，如果是字母的話則 letter 就會被設成 0x40
```#4 const uint8_t shift = (letter >> AAA) | (letter >> BBB);```
- 觀察字母 'A', ..., 'F' 及 'a', ..., 'f' 的後 4 個 bits，為 '0001', ..., '0110'
- 而要將 'A', 'a' 輸出成 10 (0b1010) 且 'F', 'f' 輸出成 15 (0b1111)
- 根據最後一行提示 ```#4 return (in + shift) & 0xf;```
- **&0xf 保留後 4 個 bits**
- in + shift 要恰為 (0b1010), ..., (0b1111)
- 因此 shift **得為 0b00001001**
- 可利用 letter >> **3** | letter >> **6** 得到
- **MASK = 0x40，AAA = 3，BBB = 6**
### 2.將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值
```c=
#include <stdbool.h>
#include <stddef.h>
#include <stdint.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;
}
uint64_t hexspeak(char str[])
{
int len = strlen(str);
if (len > 18)
return NULL;
if (str[0] != '0' || (str[1] != 'x' && str[1] != 'X'))
return NULL;
uint64_t res = 0, x = 0;
for (int i = len-1, n = 0; i >= 2; i--, n+=4) {
x = hexchar2val(str[i]) << n;
res += x;
}
return res;
}
main () {
uint64_t x = hexspeak("0x0B00B135"); // 184594741
printf("%i" , x);
}
```
---
## 測驗3
```c=
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;
}
```
### 1.解釋上述程式的原理
乘法和位移操作 $\dfrac{n}{d}$ = ${n}*{\dfrac{\dfrac{2^N}{d}}{2^N}}$
```#6 uint64_t quotient = ((__uint128_t) M * n) >> 64;```
- 右移 64 bits 相當於除 $2^{64}$
- 用 __uint128_t 來 catch ${M} * {n}$ 的高位 bit，擴大乘法後可表示的數值範圍
- 將程式碼整理成數學式 ${\dfrac{({M}*{n})}{2^{64}}}$
```#2 #define M ((uint64_t)(UINT64_C(XXX) / (D) + 1))```，其中 ${M}={\dfrac{2^{64}}{d}}$ $=$ ${\lfloor}{\dfrac{{{XXX}}}{d}{\rfloor} +1}$
- ${\dfrac{2^{64}}{d}}$ 無法總是用整數來表達，利用可表示數值範圍的最大值來估算除 d 的結果，再將差值補回去
- 64-bits 的**最大值 XXX = 0xFFFFFFFFFFFFFFFF** 與 $2^{64}$ 恰為 1，而除 d 後最壞情形是如 ${\lfloor}1.999..{\rfloor} = 1$，捨去了小數點後非常接近 1 的值，因此一概將取完 floor 的值補上修正值 1
### 2. jemalloc
---
## 測驗4
延伸測驗 3，我們想判斷某個數值能否被指定的除數所整除，在 D 和 M 都沿用的狀況下，程式碼如下:
```c=
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
- ${\lfloor} \dfrac{n}{d} {\rfloor} = (n * M) >> 64$
- M 為估算 ${\dfrac{2^{64}}{d}}$ 的結果，$n * M$ 為 $\dfrac{n}{d}$ 乘上 $2^{64}$，即 $\dfrac{n}{d}$ 小數的部份
- ${M} - 1 =$ ${\lfloor}{\dfrac{{{0xFF..FF}}}{d}{\rfloor}}$ 為 $\dfrac{1}{d}$ 乘上 $2^{64}-1$，即 $\dfrac{1}{d}$ 小數的部份
- 如果 n 要可被 d 整除，表 $\dfrac{n}{d}$ 小數的部份 < $\dfrac{1}{d}$ 小數的部份
- **YYY = M - 1**
---
## 測驗5
```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);
}
```
### 1.解釋上述程式的原理
- 從 ```#13 if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */ ``` 給的提示可以知道此行程式碼在檢測 *chunk 是否為 ASCII
- ``` #5 #define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u) ```
- ((uint64_t)(b) & (0xff)) 保留所有 (b) 的 bits
- 與 0x0101010101010101u 相乘相當於將 (b) 每隔兩個 bit 在放值
- 假設 (b) = 0xb0 ，得 0xb0b0b0b0b0b0b0b0，因此 **PACKED_BYTE(b) 將輸入做相同值的 padding**
- 根據測驗一的結果，**VV1 為 0x80**
- 改成 ```#define PACKED_BYTE(b) ((uint64_t)(b) * 0x0101010101010101u)```
- 從 strlower 函式觀察，```#7 if (s[j] >= 'A' && s[j] <= 'Z')``` then ```s[j] ^= 1 << 5;```
- 得知可透過 **mask 0x20 (1 << 5)** 與大寫字母做 XOR 轉成小寫字母
- ```#17 *chunk ^= mask;``` ，*chunk 與 mask 做 XOR
- 因此當字母為大寫時，mask 得為 0x20
- 字母為小寫時，讓 **mask 為 0x00** 則可保留原 bit，保持小寫字母
- 觀察 ```A = *chunk + PACKED_BYTE(128 - 'A') ``` 和 ```Z = *chunk + PACKED_BYTE(128 - 'Z') ```
| char | char + (128 - 'A') | char + (128 - 'Z') |
| -------- | -------- | -------- |
| 'A'(65) | 128 | 103 |
| 'Z'(90) | 153 | 128 |
| 'a'(97) | 160 | 135 |
| 'z'(122) | 185 | 160 |
- 當字母為 'a' ~ 'z' 時，其最高位的 bit 皆為 1 (>= 128)
- 而在字母為 'Z' 時，char + (128 - ‘Z’) 的結果也 >= 128
- 因此若想要透過 ```#16 uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2;``` 來做出 **0x00 或是 0x20 的 mask**
- 可以先將 char + (128 - ‘Z’) **減1**，**使其最高位 bit 在大小寫字母不同時可以區別**
| char | char + (128 - 'A') | char + (128 - 'Z') - 1|
| -------- | -------- | -------- |
| 'A'(65) | 128 | 102 |
| 'Z'(90) | 153 | 127 |
| 'a'(97) | 160 | 134 |
| 'z'(122) | 185 | 159 |
- char 在大寫時，(A ^ Z) **最高位為 1，小寫時為 0**
- 再與 0x80 做 & **保留最高位 bit 後，進行右移 2 bit**
- 因此當 char 大寫，0x80 >> 2 得 0x20，同理小寫 0x00 >> 2 得 0x00
### 2. 將前述測試程式 main 函式的 char str[] 更換為 char *str，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為
- char str[] 更換為 char *str，會 Segmentation fault
- 規格書 6.4.5 String literals 提到
> 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.
靜態配置足夠大的陣列空間存放每個字元
> 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**.
但是修改其內容是未定義的行為
- char *str 是指向 string literal 的指標，如果對該指標變數操作則會直接更改到原 string literal 的內容，為未定義行為
- 而 char str[] 則配置新的字元陣列來存放與 string literal 相同的值，因此對其操作不會更改到原 string literal 的內容
> [What is the type of string literals in C and C++?](https://stackoverflow.com/questions/2245664/what-is-the-type-of-string-literals-in-c-and-c)
---
## 測驗6
LeetCode 137. 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?
>
> Example 1:
Input: [2,2,3,2]
Output: 3
>
>Example 2:
Input: [0,1,0,1,0,1,99]
Output: 99
```c=
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;
}
```
### 1. 解釋上述程式的原理
- 將整數看成數個獨立 bit，如 2 = 0b0010、3 = 0b0011
- 當一個數最多出現 2 次時，可以只用 1 bit 來描述，而當一個數最多出現 3 次時，則需要用 2 bit 來描述
- 00 表一個數未出現、01 表出現一次、10 表出現兩次
- 當出現三次時應為 11，但將其重置為 00 來表示該數已達上限，即該數不是要找的**恰出現一次**的數，因此給定一個數，其出現次數的規律為 00 -> 01 -> 10 -> 00
- 真值表如下，其中 high 表計數過程中的高位，low 表對應的低位，input 表下一個輸入， **high' 和 low' 表對應的高低位輸出**
| high| low |input| high'| low'|
| --- | --- |-----| ---- | ----|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
- 最後一行當 high/low 狀態為 10 時，輸入 1 後輸出為 00 而非 11
- 高低位的邏輯表達式
- ${low} = {low} \cdot {\overline {high}} \cdot {\overline {input}} + {\overline {low}} \cdot {\overline {high}} \cdot {input}$
$= {\overline {high}} \cdot ({low} \cdot {\overline {input}} + {\overline {low}} \cdot {input)}$
$= {\overline {high}} \cdot ({low} \oplus {input})$
- ${high} = {high} \cdot {\overline {low}} \cdot {\overline {input}} + {\overline {high}} \cdot {low} \cdot {input}$
- low' 即表示出現一次的整數，因為 0、2、3次對應的 low' 皆為 0，這也解釋為何要將 11重置為 00，**避免兩種情形的 low' 為 1**
- 利用上述式子計算 low' 和 high' 時，皆是沿用舊的 low 值，需要先暫存起來以待計算，嘗試修改真值表，避免用舊值計算
- 將先前真值表的 low' 輸出取代掉 low，即 low 的輸出重新作為輸入
| high|**low**|input| high'|
| --- | --- |-----| ---- |
| 0 |**0**| 0 | 0 |
| 0 |**1**| 0 | 0 |
| 1 |**0**| 0 | 1 |
| 0 |**1**| 1 | 0 |
| 0 |**0**| 1 | 1 |
| 1 |**0**| 1 | 0 |
- 重新計算高位表達式
${high} = {high} \cdot {\overline {low}} \cdot {\overline {input}} + {\overline {high}} \cdot {\overline {low}} \cdot {input}$
$= {\overline {low}} \cdot ({high} \cdot {\overline {input}} + {\overline{high}} \cdot {input})$
$= {\overline{low}} \cdot ({high} \oplus {input})$
- 從上述得 KKK = ~higher，JJJ = ~lower
> [參考] https://blog.csdn.net/yutianzuijin/article/details/50597413
### 2. 請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時
- 撰寫沿用舊 low 值的版本，額外宣告 tmp 變數暫存舊 low 值來計算 higher、lower
```c=
int singleNumber(int *nums, int numsSize)
{
int lower = 0, higher = 0, tmp = 0;
for (int i = 0; i < numsSize; i++) {
tmp = lower;
lower = ~higher & (lower ^ nums[i]);
higher = (higher & ~tmp & ~nums[i]) | (~higher & tmp & nums[i]);
}
return lower;
}
```
### 3. 延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼
- 重複 4 次，用 3 個 bit 描述，000 -> 001 -> 010 -> 100 -> 000
- 重複 5 次，用 4 個 bit 描述，0000 -> 0001 -> 0010 -> 0100 -> 1000 -> 0000
- 重複 n 次，用 n-1 個 bit 描述
- 建真值表後計算邏輯表達式，撰寫程式碼
Sign in with Wallet
Connect another wallet