# 2020q3 Homework2 (quiz2)
contributed by < `zzzxxx00019` >
## 測驗 1
### 題目：
目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (ANSI) 制定的 ASCII 碼，被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。如果我們明確界定 7 位元編碼的字元隸屬於 ASCII，可透過以下函式來判斷指定的記憶體範圍內是否全是有效的 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 則是要檢驗的範圍。逐一字元比對的效率低，在 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)
{
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;
}
```
請補完程式碼。
### 原理：
透過 `uint64_t payload` 一次擷取8個陣列字元進行比對，而ASCII是透過7位元進行編碼的編碼技術，且 `char` 一般被配置大小為8bit，因此一個透過ASCII編碼的字元與 `0x80` 進行and運算需得到的理論結果為 `0x00` ，從下表 `binary` 的部分可以很清楚觀察到 `0x7F & 0x80` 後的運算結果；因此如果想對存有8個字元的字串直接進行比較，則需將8個字元都對 `0x80` 做 `&` 運算。
| | Binary | Hexadecimal |
| --- | --- | --- |
| 7bit | 0111 1111 | 0x7F |
| 8bit | 1000 0000 | 0x80 |
### 延伸問題：
* 解釋上述程式的運作原理，特別是為何用到 memcpy 呢？提示: 與 data alignment 有關。
:::info
透過memcpy，會先檢查 memory 是否為 data alignment ，如果不是的話會先針對 memory 做對齊的動作，即先 copy 幾個 byte 使 memory 狀態為 data alignment ，再以 word 為單位進行複製。
:::
* 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
* 參考`測驗 5` 的 mask 方法，透過將字元 `+128-'A'` 與 `+127-'Z'` 後，兩者做 `xor` 計算後再對 `0x80` 做 `and` 計算，如果存在著 A~Z 的字元，計算後的結果會為 `0x80` 。
* 最後因剩餘的字串長度不足 8 bytes ，因此透過逐一檢查的方式進行。
```cpp=
#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)
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);
uint64_t A = payload + PACKED_BYTE(128 - 'A') ;
uint64_t Z = payload + PACKED_BYTE(128 - 'Z' - 1) ;
uint64_t a = payload + PACKED_BYTE(128 - 'a') ;
uint64_t z = payload + PACKED_BYTE(128 - 'z' - 1) ;
if( (A^Z) & PACKED_BYTE(0x80) || (a^z) & PACKED_BYTE(0x80))
return true ;
i += 8;
}
while (i < size) {
char tmp_c = str[i] ;
if(tmp_c > 'Z') tmp_c^=' ';
if(tmp_c >= 'A' && tmp_c <= 'Z')
return true;
i++;
}
return false;
}
```
## 測驗 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;
}
```
已知 in 一定隸屬於 '0', '1', '2', …, '9' 及 'a', 'b', 'c', …, 'f' (小寫) 及 'A', 'B', 'C', …, 'F' (大寫) 這些字元。預期 hexchar2val('F') 和 hexchar2val('f') 回傳 15，且 hexchar2val('0') 回傳 0，其他輸入都有對應的數值。
以下摘自 ASCII 表格
* '0', '1', '2', …, '9' 對應到 0x30, 0x31, 0x32, … 0x39
* 'a', 'b', 'c', …, 'f' (小寫) 對應到 0x61, 0x62, 0x63, …, 0x66
* 'A', 'B', 'C', …, 'F' 對應到 0x41, 0x42, 0x43, …, 0x46
請補完程式碼。
### 原理：
首先先觀察程式碼最後的部分為 `return (in + shift) & 0xf` ，意思是前面的運算主要是為了達到 `(in + shift)` 範圍為 `0x0f ~ 0xff` 的目的。透過將 `f(0x66)` 與 `F(0x66)` 轉換為二進制，可以更加直覺觀察。
| | Binary |
| --- | --- |
| f | 0110 0110 |
| F | 0100 0110 |
為了將不必要的字元過濾掉，透過上表可以發現將 MASK 設為 `0x40` 是留下 `'f'` 與 `'F'` 共通點的最佳數值。而這兩字元經過與 MASK 進行 `&` 運算後，可以得到` 0x40` 這個結果。
而為了符合最後 `return` 的結果，最後 shift 結果需為 `'xxxx 1001'` ，因此可以很直觀的推測出 ==0x40 >> 3 | 0x40 >> 6== 輸出結果會符合預期目標。
### 延伸問題：
* 將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值。
* 透過修改原本的方法，將字串逐一比對並將結果加入 `uint_64 result` 此變數
* 因每個字元算出來的結果為 `4 bit` 的值，因此當有新的值要加入 result 時，對 result 當前數值左移 4 位。
```cpp=
uint64_t hexchar2val(char in[])
{
int i=0, in_len = strlen(in) ;
uint64_t result=0 ;
if(in_len>2 && in[0]=='0' && in[1]=='x') i = 2 ;
for( ; i < in_len ; i++)
{
const uint8_t letter = in[i] & 0x40;
const uint8_t shift = (letter >> 3) | (letter >> 6);
result = (result << 4) | ((in[i] + shift) & 0xf);
}
return result ;
}
```
## 測驗 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;
}
```
其中 `__uint128_t` 是 GCC extension，用以表示 128 位元的無號數值
預期 quickmod(5) 會得到 2, quickmod(55) 得到 1, quickmod(555) 得到 0 (555 是 3 的倍數)。
請補完程式碼。
### 原理：
根據快速除法的思維，將透過等式 $\dfrac{n}{d}=n\times\dfrac{\dfrac{2^n}{d}}{2^n}$ 進行運算。
* `#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1))` 部分以數學式來表達可寫為： $M=\dfrac{x}{d}+1$
* `uint64_t quotient = ((__uint128_t) M * n) >> 64` 這段程式碼中 `>>64` 即為除 $2^{64}$；而將整段解析以數學方式表達則為 $n\times\dfrac{M}{2^{64}}$ ，因此可推得 M 為接近 $2^{64}$ 的值 `0xFFFFFFFFFFFFFFFF`。
* 因預設處理器為 64 位元的電腦，$M$ 如果代入 $2^{64}$ 會導致溢位問題，因此將代入 $M=2^{64}-1$
:::info
證明 $\dfrac{n}{d}=((\dfrac{2^k-1}{d}+1)\times\dfrac{n}{2^k})$
$((\dfrac{2^k-1}{d}+1)\times\dfrac{n}{2^k})=(\dfrac{2^k-1+d}{d})\times\dfrac{n}{2^k}=(\dfrac{2^k}{d}-\dfrac{1}{d}+1)\times\dfrac{n}{2^k}=\dfrac{n}{d}+\dfrac{n(d-1)}{2^k\times d}$
等式結果必須符合 $\dfrac{n(d-1)}{2^k\times d}=0$，根據計算機無條件捨去特性，必須符合 $\dfrac{n(d-1)}{2^k\times d}<1$
稍微整理一下可得到不等式 $n(1-\dfrac{1}{d})<2^k$ ，因為 $n$ 為 `uint32_t` 的資料型態，因此 $n<2^{32}$
又因為 $d$ 為正整數，因此 $(1-\dfrac{1}{d})<1$ ，且 $k=64$ ，故不等式 $n(1-\dfrac{1}{d})<2^k$ 結果成立
得證 $\dfrac{n}{d}=((\dfrac{2^k-1}{d}+1)\times\dfrac{n}{2^k})$
:::
### 延伸問題：
由 Facebook 公司所維護的 [jemalloc](https://github.com/jemalloc/jemalloc) 是個高效能的記憶體配置器 (memory allocator)，特別在多核多執行緒的環境有優異表現，在其原始程式碼 [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) 也運用類似的技巧，請閱讀原始程式碼，並抽離快速除法實作為獨立的程式碼，說明運作原理，也該撰寫測試程式，比較透過處理器的整數除法指令及本技巧的效能差距
:::info
$\dfrac{2^k}{d}\times\dfrac{n}{2^k}=\dfrac{2^k+r}{d}\times\dfrac{n}{2^k}$ ， $r=-2^k mod$ $d$
$\dfrac{2^k}{d}\times\dfrac{n}{2^k}+\dfrac{r}{d}\times\dfrac{n}{2^k}=\dfrac{n}{d}+(\dfrac{r}{d}\times\dfrac{n}{2^k})$ ，因此只要證明 $\dfrac{r}{d}\times\dfrac{n}{2^k}<1$ ，就可以用上述方法得到 $\dfrac{n}{d}$ 的值。
已知 $r=-2^k mod$ $d$ 且 $k=32$ ，因此$r<d$
又因為 n 為 uint32_t 型態，最大值為 $2^{32}-1$，故 $n<2^{32}$
得證 $\dfrac{r}{d}\times\dfrac{n}{2^k}<1$
:::
## 測驗 4
### 題目：
```cpp
#define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (D) + 1))
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
以 D = 3 來說，divisible(7) 要得到 0 (即 7 無法被 3 整除)，divisible(87) 要得到 1 (即87是三的倍數)
請補完程式碼。
### 原理：
因為實在摸不清這段程式的邏輯，因此參考< `quantabase13` >的代數方法去解釋。
* 根據已知參數 $M=\dfrac{0xFF...F}{3}+1$ ，可先算出 $M=0x5555555555555556$
* 已知 $D=3$ ，因此可以令 $n=3k$、$3k+1$、$3k+2$
* $if(n=3k)$：$n\times{M}=3k\times{0x555...6}$，經過處理可得$k\times{0x55...5}+k+2k$，基於 64 位元處理器下限制下，$k\times{0x55...5}+k$ 會發生溢位操作而歸 0 ，因此結果為$2k$。
* $if(n=3k+1)$：如同上述計算可得結果為 $0x55..5+2k+1$，即 $2k+M$ 。
* $if(n=3k+2)$：如同上述計算可得結果為 $0xAA..A+2k+2$，即$2k+2M$。
* 在 $k$ 為非負整數的狀態下，只有 $M-1$ 符合要求結果。
## 測驗 5
### 題目：
在 64 位元處理器架構 (以下針對 x86_64, little endian)，我們可引入向量化 (vectorized) 的手段，避免一次比對一個字元，而是直接操作一整個 word (對 x86_64 來說，就是 64 bits，或 8 個位元組)。沿用上述的 strlower 函式，我們用這樣的思路實作向量化的 strlower，程式碼列表如下:
```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);
}
```
對應的測試程式碼如下:
```cpp
#include <stdio.h>
#include <string.h>
int main()
{
/* quote from https://www.gutenberg.org/files/74/74-h/74-h.htm */
char str[] =
"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);
}
```
參考執行輸出:
>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
請補完程式碼。
### 原理：
* `PACKED_BYTE(b)` 用途是將一個 16-bit 的數值擴張為 64-bit ，且以 16-bit 為一個單位。如 `PACKED_BYTE(0x80)` 結果就會為 `0x8080808080808080` 。
* 因 ASCII Code 為 7-bit 編碼，因此最大值只會來到 `'0x7F'` ，對 `'0x80'` 進行 `&` 運算結果必定為 0 ，因此推測 `VV1=0x80` 。
* 根據課堂講義 [C 語言: 數值系統 - 運用 bit-wise operator](https://hackmd.io/@sysprog/c-numerics#%E9%81%8B%E7%94%A8-bit-wise-operator) 所提到內容「大小寫互轉: 避免使用分支」，推測 `*chunk ^= mask` 用意即是為了做這個動作。
```
('a' ^ ' ') // 得到 'A'
('A' ^ ' ') // 得到 'a'
```
* mask 的用意在於，將對應為大寫的部分以 `0x20(' ')` 填入，其他部分以 `0x00` 填入，如此大寫字元將會被降為小寫，而其他字元則維持原貌。
* 為了達到上述目的， `(A ^ Z) & PACKED_BYTE(VV4)` 所對應的大寫字元部分結果應為 `0x80` ，如此透過 `>>2` 的步驟，才能得到預期的結果 `0x20` ，因此知 `VV4=0x80` 。
* 為了得到 `0x20` 這個結果，對應的字元必須滿足 `(A ^ Z)` 的第 8 個 bit 為 1 ，即必須滿足以下兩式，根據代入 'A' 與 'Z' 計算，`VV2=0` 且` VV3=(-1)` 可以滿足需求。
```
input + 128 - 'A' + VV2 >= 128
input + 128 - 'Z' + VV3 < 128
```
### 延伸問題：
* 將前述測試程式 main 函式的 char str[] 更換為 char *str，會發生什麼事？
參考自 < `RinHizakura` > 所擷取的 C 語言規格書內容片段：
>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
:::info
* `str[]` 是在 memory 上，透過靜態配置產生 string literal ，去儲存字串內容，而 `*str` 則是一個指標型態，指向字串儲存的記憶體位置。因此兩者最明顯的差異在於 `str[]` 是一個陣列型態，依據需求去進行記憶體的配置，而 `*str` 則是一個指標型態，指向 array of char。
* 根據 C 語言規格書所記載，透過指標 "pointer to char" ，去對 string literal 進行修改，此動作是 undefined 的。
:::
因此產生錯誤訊息：
```
[1] 22494 segmentation fault (core dumped) ./a.o
```
## 測驗 6
### 題目：
>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
```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` 運算特性：
* `XOR` 在 `bit` 世界中，即是對相對應的 `bit` 做相加的動作，且不做進位的動作，根據此特性可以得到 `a ^ a = 0` 的特性。
* 在 `XOR` 運算式中，符合交換率的規則，即 `a ^ b ^ c = a ^ c ^ b` 。
* 綜合以上兩點，可以歸納出 `a ^ b ^ a = b` 的小結論，意即透過 `XOR` 運算的方法，可以求出出現 `1` 次的數值。
* 將觀念延伸到此題，透過 lower 、 higher 與初始化去紀錄每個數值出現的狀況，如果以兩個 bit 去記錄各種不同的狀態，簡單表示下即為 `(00 -> 01 -> 10 ->00)`：
|higher|lower|input|higher'|lower'|
|- | -| -| -|- |
|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 |
根據邏輯設計課程所學，將增值表以邏輯運算表示：
$lower = higher' \cdot lower' \cdot input + higher' \cdot lower \cdot input'=higher' \cdot (lower' \cdot input + lower \cdot input') = higher' \cdot (lower\oplus input)$
此外根據程式撰寫流程， higher 在更新時，所採用的是已更新過的 lower ，得到邏輯運算式：
$higher = higher \cdot lower \cdot input + higher \cdot lower' \cdot input' = lower' \cdot (higher' \cdot input + higher \cdot input') = lower' \cdot (higher \oplus input)$
因此推斷 `KKK=~higher` 、 `JJJ=~lower` 。
### 延伸問題：
* 請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時
* 透過原題的邏輯運算，可將程式碼縮短為更簡短且更直觀的寫法
* 在設計 `higher` 那部分，也可直接透過邏輯運算，不採用更動後的 `lower` ，只是這樣會使程式碼變得更加冗長，增加計算負擔
```cpp=
int singleNumber(int *nums, int numsSize)
{
int lower = 0, higher = 0 ;
for(int i = 0 ; i < numsSize ; i++)
{
lower = (~higher)&(lower^nums[i]) ;
higher = (~lower)&(higher^nums[i]) ;
}
return lower ;
}
```
* 延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼
* 設計題目為陣列中，所有字都會出現 4 次，只有一個字會出現 1 次
* 依照想法， low 必須保留給只出現一次的字，因此還需要額外兩個變數紀錄出現兩次與三次的狀況 (第四次會歸 0 )，故為 000 -> 001 -> 010 -> 100 ，因為最右邊的 bit 要保留給 low
|high 2|high 1|low|input|high2'|high1'|low'|
|-| -| -| -| -| -| -|
|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| 1| 0| 0|
|1| 0| 0| 0| 1| 0| 0|
|1| 0| 0| 1| 0| 0| 0|
依照增值表可設計出以下的邏輯運算規則 (尚未化簡)：
$outputlow = high2'\cdot high1'\cdot low'\cdot input + high2'\cdot high1'\cdot low \cdot input'$
$outputhigh1 = high2'\cdot high1' \cdot low \cdot input + high2'\cdot high1\cdot low'\cdot input'$
$outputhigh2 = high2'\cdot high1\cdot low'\cdot input + high2\cdot high1'\cdot low'\cdot input'$
而運算式中的 $high2$ 、 $high1$ 、 $low$ 皆為前面運算的結果，因此依照 C 依序執行的概念，需將上次的運算結果儲存在一個變數中，才不會導致結果錯誤。
```cpp=
#include <stdio.h>
#include <stdlib.h>
int singleNumber(int *nums, int numsSize)
{
int low = 0, high1 = 0, high2 = 0 ;
for(int i = 0 ; i < numsSize ; i++)
{
int h1 = high1, h2 = high2, lo = low ;
low = ( ~h2 & ~h1 & ~lo & nums[i] )|( ~h2 & ~h1 & lo & ~nums[i] ) ;
high1 = (~h2 & ~h1 & lo & nums[i] )|( ~h2 & h1 & ~lo & ~nums[i] ) ;
high2 = (~h2 & h1 & ~lo & nums[i] )|(h2 & ~h1 & ~lo & ~nums[i] ) ;
}
return low ;
}
int main()
{
int nums[] = {2, 2, 4, 2, 3, 2, 4, 4, 4} ;
printf("result = %d\n", singleNumber(nums, 9)) ;
return 0 ;
}
```
```
result = 3
```
依照此邏輯去設計可以推展出 4 次、 5 次、 6 次等演算法，只要記得將最右邊的 bit 留給 lower 使用即可，如 5 次可設計為 000 -> 001 -> 010 -> 100 -> 110 -> 000 以此類推。
Sign in with Wallet
Connect another wallet