# 2020q3 Homework2 (quiz2)
contributed by < `justapig9020` >
###### tags: `sysprog2020`
## outline
[TOC]
## link
[作業區](https://hackmd.io/@sysprog/2020-homework2)
[題目](https://hackmd.io/@sysprog/2020-quiz2)
[github](https://github.com/justapig9020/sysprog2020-quiz2)
## 測驗 `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 & 0x8080808080808080)
return false;
i += 8;
}
while (i < size) {
if (str[i] & 0x80)
return false;
i++;
}
return true;
}
```
- [x] 解釋上述程式的運作原理，特別是為何用到 memcpy 呢？提示: 與 data alignment 有關，詳閱 [C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)
- [x] 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
- [ ] 承上，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對
:::info
提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令，可加速字串比對，詳見: Schema Validation with Intel® Streaming SIMD Extensions 4
:::
---
### 議題 `1`
:::info
解釋上述程式的運作原理，特別是為何用到 memcpy 呢？提示: 與 data alignment 有關，詳閱 [C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)
:::
首先檢視 glibc 中 [memcpy](https://code.woboq.org/userspace/glibc/string/memcpy.c.html) 的 source code .
```cpp=
#include <string.h>
#include <memcopy.h>
#undef memcpy
void *memcpy (void *dstpp, const void *srcpp, size_t len)
{
unsigned long int dstp = (long int) dstpp;
unsigned long int srcp = (long int) srcpp;
/* Copy from the beginning to the end. */
/* If there not too few bytes to copy, use word copy. */
if (len >= OP_T_THRES)
{
/* Copy just a few bytes to make DSTP aligned. */
len -= (-dstp) % OPSIZ;
BYTE_COPY_FWD (dstp, srcp, (-dstp) % OPSIZ);
/* Copy whole pages from SRCP to DSTP by virtual address manipulation,
as much as possible. */
PAGE_COPY_FWD_MAYBE (dstp, srcp, len, len);
/* Copy from SRCP to DSTP taking advantage of the known alignment of
DSTP. Number of bytes remaining is put in the third argument,
i.e. in LEN. This number may vary from machine to machine. */
WORD_COPY_FWD (dstp, srcp, len, len);
/* Fall out and copy the tail. */
}
/* There are just a few bytes to copy. Use byte memory operations. */
BYTE_COPY_FWD (dstp, srcp, len);
return dstpp;
}
```
其中 `MACRO` 所定義的數值如下，來自於 [memcopy.h](https://code.woboq.org/userspace/glibc/sysdeps/generic/memcopy.h.html) 。
主要用於定義 `word` 的大小，然而並沒有看到對於不同平台的判斷。
```cpp
#define OP_T_THRES 16
#define op_t unsigned long int
#define OPSIZ (sizeof (op_t))
```
先講結論， `memcpy` 首先透過 `MACRO` `BYTE_COPY_FWD` 將 `dstp` 整理至 `OPSIZE` 對齊。
接著依序按照 `page` 、 `word` 長度來複製資料，最後再次以 `byte` 為單位搬移剩餘資料。
接下來來看看上述 `MACRO` 的 [source code](https://code.woboq.org/userspace/glibc/sysdeps/generic/memcopy.h.html)
```cpp=
#define BYTE_COPY_FWD(dst_bp, src_bp, nbytes) \
do \
{ \
size_t __nbytes = (nbytes); \
while (__nbytes > 0) \
{ \
byte __x = ((byte *) src_bp)[0]; \
src_bp += 1; \
__nbytes -= 1; \
((byte *) dst_bp)[0] = __x; \
dst_bp += 1; \
} \
} while (0)
```
首先 `BYTE_COPY_FWD` 就是單純的自 `src_bp` 搬移 `nbytes` 到 `dst_bp`。
```cpp=
#define WORD_COPY_FWD(dst_bp, src_bp, nbytes_left, nbytes) \
do \
{ \
if (src_bp % OPSIZ == 0) \
_wordcopy_fwd_aligned (dst_bp, src_bp, (nbytes) / OPSIZ); \
else \
_wordcopy_fwd_dest_aligned (dst_bp, src_bp, (nbytes) / OPSIZ); \
src_bp += (nbytes) & -OPSIZ; \
dst_bp += (nbytes) & -OPSIZ; \
(nbytes_left) = (nbytes) % OPSIZ; \
} while (0)
```
接著 `WORD_CPOY_FWD` 是透過 `_wordcopy_fwd_aligned`
```cpp=
# define PAGE_COPY_FWD_MAYBE(dstp, srcp, nbytes_left, nbytes) \
do \
{ \
if ((nbytes) >= PAGE_COPY_THRESHOLD \
&& PAGE_OFFSET ((dstp) - (srcp)) == 0) \
{ \
/* The amount to copy is past the threshold for copying \
pages virtually with kernel VM operations, and the \
source and destination addresses have the same alignment. */ \
size_t nbytes_before = PAGE_OFFSET (-(dstp)); \
if (nbytes_before != 0) \
{ \
/* First copy the words before the first page boundary. */ \
WORD_COPY_FWD (dstp, srcp, nbytes_left, nbytes_before); \
assert (nbytes_left == 0); \
nbytes -= nbytes_before; \
} \
PAGE_COPY_FWD (dstp, srcp, nbytes_left, nbytes); \
} \
} while (0)
```
#### 記憶體對齊
設計簡單實驗驗證記憶體對齊對
```cpp
#include <stdio.h>
#include <time.h>
#include <stdint.h>
#include <stdbool.h>
time_t access_test(int arr[], size_t sz) {
time_t start, end;
start = clock();
for (int i=0; i<10000; i++)
for(int j=0; j<sz; j++)
arr[j] = i*j;
end = clock();
return end - start;
}
time_t test() {
int a[101];
time_t rst1;
time_t rst2;
for (int i=0; i<101; i++) a[i] = 0;
rst1 = access_test(a, 100);
rst2 = access_test((int*)((char*)a + 1), 100);
return rst2 - rst1;
}
int main(void) {
time_t total = 0;
size_t times = 0;
for (int i=0; i<1000; i++) {
time_t rst = test();
printf("%d %ld\n", i, rst);
if (rst > 0)
times++;
total += rst;
}
printf("# rate %f\n", times/1000.0);
printf("# avg %f\n", total/1000.0);
return 0;
}
```
透過重複讀取對齊與非對齊的記憶體並比較所花費時間。
`圖 1`
- positive rate: 72.4%
- AVG 84.81 ticks
---
`圖 2`
- positive rate: 93.8%
- AVG 334.905 ticks
---
`圖 3`
- positive rate: 20.1%
- AVG -3.59 ticks
透過實驗可以觀察到大致上存取非對齊記憶體的成本是會大於對齊記憶體的。但是有時情況會反轉，甚至會發生如圖 `3` 中平均值為負的情況。
:::warning
無法解釋為何會產生不符合預期結果。
:::
### 議題 `2`
:::info
將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
:::
借鑑測驗 `5` 的概念，改寫程式為
```cpp=
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#define ALIGN(ptr) (((ptr) + sizeof(uint64_t) - 1) & ~(sizeof(uint64_t) - 1))
const uint64_t MASK = 0x0101010101010101;
char BUF[100];
bool isalph_char(char c) {
c |= 0x20;
char lz = c + (0x80 - 'z' - 1);
char ga = c + (0x80 - 'a');
return ((lz ^ ga) & 0x80) == 0x80;
}
bool isalph_word(uint64_t w) {
w |= 0x20 * MASK;
uint64_t lz = w + (0x80 - 'z' - 1) * MASK;
uint64_t ga = w + (0x80 - 'a') * MASK;
return ((lz ^ ga) & (0x80 * MASK)) == (0x80 * MASK);
}
bool isalph_str(char str[], size_t size) {
bool alph = true;
char *aligned = (char *)ALIGN((uint64_t)(str));
printf("size: %zu\n", size);
printf("string: %p\n", str);
printf("Aligned: %p\n", aligned);
while (size && alph && str < aligned) {
alph = isalph_char(*str);
str++;
size--;
}
printf("Pre-matched: %p\n", str);
while (alph && size >= 8) {
alph = isalph_word(*(uint64_t *)str);
str += sizeof(uint64_t);
size -= 8;
}
printf("Matched word: %p\n", str);
while (alph && size) {
alph = isalph_char(*str);
str++;
size--;
}
return alph;
}
```
完整實作放在 [github](https://github.com/justapig9020/sysprog2020-quiz2/tree/master/question1/topic2)
主要函數 `isalph_word` 透過 `MASK` 將 `bitwise` 操作擴展成一個 word 各 byte 同時操作。
另外嘗試透過前處理使進行 `isalph_word` 運算時， word 皆處於記憶體對齊。
### 議題 `3`
:::info
承上，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對
:::
## 測驗 `2`
```cpp
uint8_t hexchar2val(uint8_t in)
{
const uint8_t letter = in & 0x40;
const uint8_t shift = (letter >> 3) | (letter >> 6);
return (in + shift) & 0xf;
}
```
- [x] 解釋上述程式的運作原理;
- [x] 將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值
---
### 議題 `1`
:::info
解釋上述程式的運作原理
:::
首先觀察 return 的值為輸入值 + `shift` 並取低四位元。
透過觀察 `ascii` 表可以得知：
1. `'0'` ~ `'9'` 的低四位元實際上就為對應的二進制數值 (`0b0000` ~ `0b1001`)。由此可見 `shift` 在輸入為 `'0'` ~ `'9'` 時需為 `0`。
3. `'a'` ~ `'f'` 及 `'A'` ~ `'F'` 的低四位元實際上對應二進制數值 (`0b0001` ~ `0b0110`)。由此可見 `shift` 在輸入為 `a` ~ `f` 時需為 `9` ($10-1$)。
目前的問題為要如何在 `'0' ~ '9'` 與 `'a' ~ 'f' , 'A' ~ 'F'` 時組合出不同的 `shift` 。
首先我們知道英文大小寫相差 `0x20` 。來觀察看看 `ascii` 的高四位元，是否也有類似的機制可以利用。
透過觀察我們可以發現
|bin|ascii|
|-|-|
|0b0011 0000|0|
|0b0100 0001|A|
|0b0110 0001|a|
`'a'` 與 `'A'` 都有 0x40 這個位元，而 `'0'` 則沒有。因此 `0x40` 便是 0~9 跟 a~f 的差異位元。
觀察一下 `shift` 的生成過程。
```cpp
const uint8_t letter = in & 0x40;
const uint8_t shift = (letter >> 3) | (letter >> 6);
```
透過與 0x40 進行 and 運算， letter 在輸入值為 `'0'~'9'` 時為零。 而 `'a' ~ 'f'` 則會為 0x40 。
接下來就是透過 0x40 來組成 `shift` 9。
9 的二進制為 `0x1001` ， `0x40` 可以分別透過右移 3 與 6 變成 `0x1000` 與 `0x0001` ，再藉由 `or` 運算變可獲得 9 。
總結來說，透過分析兩組數值的差異以及位移，再藉由萃取差異部份組成位移來達成無分支度運算。
### 議題 `2`
::: info
將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值
:::
再次借鑒測驗 `5` 的概念，透過擴展 `bit wise` 操作同時處理複數 `byte` 。
完整實作放置於 [gitthub](https://github.com/justapig9020/sysprog2020-quiz2/tree/master/question2/topic2)
```cpp
#define MASK 0x0101010101010101
uint32_t hexchar2val(uint64_t in) {
const uint64_t letter = in & (0x40 * MASK);
const uint64_t shift = (letter >> 3) | (letter >> 6);
in = (in + shift) & (0xf * MASK);
uint64_t sh_msk = 0xf * (MASK - 1);
for (size_t i = 0; i < 7; i++) {
uint64_t shift = in & sh_msk;
in &= ~sh_msk;
shift >>= 4;
in |= shift;
sh_msk <<= 4;
}
return in & 0xffffffff;
}
```
首先 `MACRO` `MASK` 可以透過乘法在編譯時期將 `bit mask` 擴展成同時處理 8 byte 。
依照議題 `1` 的分析，以下程式碼可以將每個 byte 的值運算成對應的二進制數值。
```cpp
const uint64_t letter = in & (0x40 * MASK);
const uint64_t shift = (letter >> 3) | (letter >> 6);
in = (in + shift) & (0xf * MASK);
```
但是透過這樣過後，數值會以 byte 為單位分散。例如 `"deadbeef"` 再經過運算後會變成 `0x0d_0e_0a_0d_0b_0e_0e_0f` ，這明顯不是我們所逾期的答案。
透過觀察可以發現，只要將由右數來的第 `n` 個 `byte` 右移 `4 * n` 位，即可將數值移動至正確位置。
遵循此想法建構以下程式
```cpp
uint64_t sh_msk = 0xf * (MASK - 1);
for (size_t i = 0; i < 7; i++) {
uint64_t shift = in & sh_msk;
in &= ~sh_msk;
shift >>= 4;
in |= shift;
sh_msk <<= 4;
}
```
其中，由於最右一位元組的數值已經在正確位置了，因此直接從第二 `byte` 開始運算，透過 `and` 運算可以過濾出所需資料再透過右移依序將資料移至指定位置。
以下為輸入 `deadbeef` 後每一 round 的數值與 MASK 值。
```
MASK: 0f0f0f0f0f0f0f00
VAl: 0d0e0a0d0b0e0e0f
MASK: f0f0f0f0f0f0f000
VAl: 00d0e0a0d0b0e0ef
MASK: 0f0f0f0f0f0f0000
VAl: 000d0e0a0d0b0eef
MASK: f0f0f0f0f0f00000
VAl: 0000d0e0a0d0beef
MASK: 0f0f0f0f0f000000
VAl: 00000d0e0a0dbeef
MASK: f0f0f0f0f0000000
VAl: 000000d0e0adbeef
MASK: 0f0f0f0f00000000
VAl: 0000000d0eadbeef
MASK: f0f0f0f000000000
VAl: 00000000deadbeef
```
透過觀察此流程可以發現，每一回合透過右移都會有新的一組數值被移動至正確位置。此外透過左移 `MASK` ，達到只處理未移動到正確位置的效果。
最後再回傳此變數的低 32 為元即可獲的所需數值。
## 測驗 `3`
```cpp
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;
}
```
- [x] 解釋上述程式的原理;
- [ ] 由 Facebook 公司所維護的 jemalloc 是個高效能的記憶體配置器 (memory allocator，即 malloc 和 free 函式對應的實作)，特別在多核多執行緒的環境有優異表現，在其原始程式碼 include/jemalloc/internal/div.h 和 src/div.c 也運用類似的技巧，請閱讀原始程式碼，並抽離快速除法實作為獨立的程式碼，說明運作原理，也該撰寫測試程式，比較透過處理器的整數除法指令及本技巧的效能差距;
### 議題 `1`
:::info
解釋上述程式的原理;
:::
目標為求得 `n % D` ，其中 `D` 為 3 。由於 `n % 3` 可以被表達為 $n-\dfrac{(int)n}{3}$ ，而 $\dfrac{(int)n}{3}$ 中的 $\dfrac{1}{3}$ 可以被事先運算。由於 $\dfrac{1}{3}$ 為浮點數，為避免浮點數運算並保持精度， `M` 在事前運算時事先 `<< 64` 並在執行時期透過 `>> 64` 補償。然而面臨兩個問題。
1. `64` bit 架構下並無法保存 `1 << 64`
3. 由於 $\dfrac{1}{3}$ 為循環小數，透過整數型態儲存會產生誤差
#### 空間
由於 64 bit 無號數可以保存之最大整數為 $2^{64}-1$ ，無法容納下 `2<<64` ( $2^{64}$ )，因此轉為保存 $(2^{64}-1)+1$ ，在此思路下的 `M` 會變成 $\dfrac{(2^{64}-1) + 1}{3} = \dfrac{0xFFFFFFFFFFFFFFFF + 1}{3}$ 。
然而此算式再實務上會遭遇錯誤，由於除數是 `64` bit ，當其加一時會 `overflow` 成 `0` 。若將算式拆分成 $\dfrac{0xFFFFFFFFFFFFFFFF}{3}+\dfrac{1}{3}$ 則會遭遇到 $\dfrac{1}{3}$ 再整數運算下為 `0` 的問題。
#### 誤差
由於 `1/3` 為循環小數，位移後透過整數儲存會產生誤差，導致 $3 * \dfrac{1}{3} = 0.9999$ 。透過以下程式驗證其在二進制的行為。
```cpp
#include <stdio.h>
#include <stdint.h>
int main(void) {
const uint64_t a = (1ul << 32) / 3;
uint64_t b = (3 * a);
uint32_t c = b >> 32;
printf("%llx\n%llx\n%x\n", a, b, c);
return 0;
}
```
輸出
```cpp
55555555
ffffffff
0
```
---
為了補償以上兩個問題，最終 `M` 的算式為 $\dfrac{0xFFFFFFFFFFFFFFFF}{3} + \lceil{\dfrac{1}{3}}\rceil$ ，透過此方式補償誤差，而溢出的部份在後續的位移運算中被移除因此在需求的精度可以正確運算。
## 測驗 `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(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);
}
```
- [x] 解釋上述程式的原理;
- [ ] 將前述測試程式 main 函式的 char str[] 更換為 char *str，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為
### 議題 `1`
首先透過 `0x80` 的 bit mask 可以檢測該 byte 是否為 `ASCII` code ，若 `n & 0x80 == 0x80` 說明 `n` 為 `EASCII` ，而透過乘上 `0x0101010101010101` 可以將此 bit mask 擴展為 64 位元格式，進而一次檢驗 8 位元組的資料，本題將會大量使用此一技巧。
透過檢測，我們將 `EASCII` 交由 `strlower` 處理。而 `ASCII` 中需要進行大小寫轉換的字元為 `'A' ~ 'Z'` 轉換為 `'a' ~ 'z'` 。
為達此目的，需完成以下兩步驟
1. 檢測該字元是否為 `'A' ~ 'Z'`
2. 若檢測為真，進行轉換。否則維持原字元
由於已知 `ASCII` 數值介於 `0x00` ~ `0x7f` 因此可以利用 `MSB` 作為輔助進行判斷。
所需判斷為數值 n 必須大於等於數值 `'A'` 且小於等於數值 `'Z'` 。透過 `A = n + (0x80 - 'A')` , `Z = n + (0x80 - 'Z' - 1)` ，使變數 `A` 唯有在 `n >= 'A'` 時 `MSB` 為 1 ，而 `Z` 唯有在 `n <= 'Z'` 時 `MSB` 為 0 。因此透過判斷 `A ^ Z` 的 `MSB` 可以達成判斷 `n >= 'A' && n <= 'Z'` 。同時以上操作因為範圍皆在 1 位元組內，因此可以透過前述之 `0x0101010101010101` 擴展為同時運算 8 byte 。
最後透過 `ASCII` 的 feature ，將判斷成功的 0x80 轉成可以切換大小寫的 0x20 。
### 議題 `2`
:::info
將前述測試程式 main 函式的 char str[] 更換為 char *str，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為
:::
- [ ] TODO: 實際翻閱規格書找出確切說明。
在此案例中，使用 `char ` 與 `char[]` 並無區別。
指標與陣列只在宣告參數值等價，在宣告變數時指標會獲得一個可以容納一個記憶體位址的空間，而陣列則會直接獲得一個記憶體區段。
例如以下程式
```cpp
char *ptr;
char arr[10];
```
`ptr` 會獲得一個記憶體空間，此空間可以剛好容納一個記憶體位址做為其 `value` 。例如：
```cpp
c = arr;
```
變會將 `arr` 作為數值存入 `ptr` 所代表的記憶體空間中。根據習慣會稱之為 `ptr 指向 arr` 。
而 `arr` 則會直接獲得 `sizeof(char) * 10` 的空間， `arr` 本身即代表了該記憶體區段的開頭。
需要注意的是， `ptr` 是有其記憶體位址而 `arr` 則是某一記憶體的別名。根據 `c` 語言定義，物件的定義為具有明確記憶體空間，因此 `ptr` (指標)是一種物件，而 `arr` (陣列)並非一種物件。
若對於 `identifier: arr` 取址( `&arr` )，在 gcc 會返回該陣列的起始位址。
## 測驗 `6`
```cpp
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;
}
```
- [x] 解釋上述程式的原理;
- [x] 請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時;
- [x] 延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼;
### 議題 `1`
:::info
解釋上述程式的原理
:::
本議題討論參考自 [此共筆](https://hackmd.io/@RinHizakura/SJ5NuIANP?fbclid=IwAR235mlCHeH8tTizaRWb7xYGQZ_8b23u7QpHcb_IaoaDL1gDXDu55b3tgPA)
首先將問題限制再 1 bit 的狀態下，可以繪製出如下的真值表。
|input|higher lower|higher' lower'|
|-|-|-|
|0|0 0|0 0|
|0|0 1|0 1|
|0|1 0|1 0|
|1|0 0|0 1|
|1|0 1|1 0|
|1|1 0|0 0|
可以觀察到 `lower'` 的數值為 `lower ^ input` 。然而有一例外，當輸入為 `1` 且 `higher lower` 為 `10` 時， `lower'` 為 `0` 。透過將 `higher` 做 `not` 運算成為 mask 可以處理此例外狀況。對應程式碼如下。
```cpp
lower ^= nums[i];
lower &= ~higher;
```
另外可以觀察到 `higher'` 的數值為 `higher ^ input` 。然而也有一例外，當輸入為 `1` 且 `higher lower` 為 `00` 時， `higher'` 為 `0` 。透過將 `lower'` 做 `not` 運算成為 mask 可以處理此例外狀況。對應程式碼如下。
```cpp
higher ^= nums[i];
higher &= ~lower; // 此時的 lower 為 lower'
```
### 議題 `2`
:::info
請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時;
:::
利用卡諾圖思考此議題。
:::info
#define I input
#define H higher
#define L lower
:::
`H'` 的卡諾圖
|I \ HL|00|01|11|10|
|-|-|-|-|-|
|0|0|0|==X==|==1==|
|1|0|==1==|==X==|0|
`L'` 的卡諾圖
|I \ HL|00|01|11|10|
|-|-|-|-|-|
|0|0|==1==|X|0|
|1|==1==|0|X|0|
透過卡諾圖可以得知此循序邏輯為
$H'=H\bar{I}+LI$
$L'=\bar{I}\bar{H}L+I\bar{H}\bar{L}=\bar{H}(I\oplus L)$
實踐上述邏輯的程式
```cpp
int singleNumber(int *nums, int numsSize)
{
int higher = 0, lower = 0;
for (int i=0; i<numsSize; i++) {
int l_buf = lower;
lower = ~higher & (lower ^ nums[i]);
higher = (higher & ~nums[i]) | (l_buf & nums[i]);
}
return lower;
}
```
通過 `leetcode`
執行時間與記憶體用量
### 議題 `3`
:::info
延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼;
:::
完整實作置於 [github](https://github.com/justapig9020/sysprog2020-quiz2/blob/master/question6/topic3)
#### 程式碼截錄
```cpp
bool is_pow2(int n) {
return n>2 && !(n & (n-1));
}
int buf_len(int n) {
return (int)log2((double)n) + !is_pow2(n);
}
int single_num(int nums[], int sz, int times) {
int len = buf_len(times);
int *state = malloc(sizeof(int) * len);
int *mask = malloc(sizeof(int) * len);
for (int i=0; i<len; i++)
state[i] = 0;
times--;
for (int i=0; i<len; i++) {
mask[i] = !!(times & (1 << i)) * -1;
}
for (int i=0; i<sz; i++) {
int carry = nums[i];
int chk = carry;
for (int j=0; j<len; j++) {
chk &= ~(state[j]^mask[j]);
int c_buf = carry & state[j];
state[j] ^= carry;
carry = c_buf;
}
chk = ~chk;
for (int j=0; j<len; j++) {
state[j] &= chk;
}
}
int rst = state[0];
free(state);
free(mask);
return rst;
}
```
由議題 `1` `2` 可知，我們可以透過保存狀態並且在第 `n` 次輸入 1 時回歸初始狀態的手法來解決此一問題。
而對於重複 ``n` 次的輸入我們需要 $\lceil log_2(n) \rceil$ 個 bit 來保存其狀態。
```cpp
bool is_pow2(int n) {
return n>2 && !(n & (n-1));
}
int buf_len(int n) {
return (int)log2((double)n) + !is_pow2(n);
}
```
由於處理的數值為 int ，因此透過長度為 $\lceil log_2(n) \rceil$ 的陣列保存狀態。
```cpp
int len = buf_len(times);
int *state = malloc(sizeof(int) * len);
```
此陣列中每一元素的第 x 個位元所組合成的二進制數值即為第 x 位元當前的狀態。
以有四位狀態位元為例：
```cpp
b0 = state[0] & 0x1 << x;
b1 = state[1] & 0x1 << x;
b2 = state[2] & 0x1 << x;
b3 = state[3] & 0x1 << x;
sx = b3 << 3 | b2 << 2 | b1 << 1 | b0;
```
`sx` 及代表第 x 位元當前的狀態。
而每當該位元輸入 1 時對應的狀態便會加一。
```cpp
int carry = nums[i];
// ...
for (int j=0; j<len; j++) {
// ...
int c_buf = carry & state[j];
state[j] ^= carry;
carry = c_buf;
}
```
而在某狀態為 `n-1` 且該狀態加一時，該狀態必須歸零。
首先我們先找出狀態 `n-1` 並製作 mask 。
```cpp
// times: 重複的次數
int *mask = malloc(sizeof(int) * len);
//...
times--;
for (int i=0; i<len; i++) {
mask[i] = !!(times & (1 << i)) * -1;
}
```
以重複 3 次為例，將獲得 mask
```cpp
mask[0] = 0;
mask[1] = 0xFFFFFFFF;
```
透過此遮罩可以過濾出哪一 bit 需要清零，並在每一回合最後進行清零。
```cpp
int carry = nums[i];
int chk = carry;
for (int j=0; j<len; j++) {
chk &= ~(state[j]^mask[j]);
// ...
}
chk = ~chk;
for (int j=0; j<len; j++) {
state[j] &= chk;
}
```
透過以上操作可以任意擴展重複次數。
以藉由 leetcode `136` `137` 驗證。
Sign in with Wallet
Connect another wallet