---
tags: sysprog2020
---
# 2020q3 Homework2 (quiz2)
contributed by < `nickchenchj` >
## Prerequisite
* [problems for quiz2 (2020q3)](https://hackmd.io/@sysprog/2020-quiz2)
## Problem 1
### Required Functions
* Check if the input string is in ASCII
* Process 64 bits at once (8 chars)
### Code Snippets
* `is_ascii` (8-bit version)
```c=
#include <stdbool.h>
#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;
}
```
* `is_ascii` (64-bit version)
```c=
#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;
/* Processes 8 chars at once in each iteration */
while ((i + 8) <= size) {
uint64_t payload;
memcpy(&payload, str + i, 8);
if (payload & MMM)
return false;
i += 8;
}
/* Processes the remaining chars one by one */
while (i < size) {
if (str[i] & 0x80)
return false;
i++;
}
return true;
}
```
#### MMM = ?
* `(a)` `0x0080008000800080`
* `(b)` `0x8000800080008000`
* `(c)` `0x0808080808080808`
* `(d)` `0x8080808080808080`
* `(e)` `0x8888888888888888`
* `(f)` `0xFFFFFFFFFFFFFFFF`
### How `is_ascii` (8-bit version) works?
| Base | ASCII | Extended ASCII |
|:----:|:---------------------:|:---------------------:|
| 2 | 0000 0000 ~ 0111 1111 | 1000 0000 ~ 1111 1111 |
| 16 | 0x00 ~ 0x7F | 0x80 ~ 0xFF |
:::info
:bulb: From the table, we can find that the [MSB](https://en.wikipedia.org/wiki/Bit_numbering#Most_significant_bit) of the char in ASCII is always `0` (binary), and that of the char in extended ASCII is always `1` (binary).
:::
* to extract the value of the 8th bit, apply `str[i] & 0x80`:
| Type | str[i] | str[i] & 0x80 | Result |
|:--------------:|:---------:|:-------------:|:-------:|
| ASCII | 0100 0011 | ==0==000 0000 | `0` |
| extended ASCII | 1100 0011 | ==1==000 0000 | not `0` |
###### Note: `0100 0011` and `1100 0011` were just examples for this demonstration
* after filtering, all bit values except for the [MSB](https://en.wikipedia.org/wiki/Bit_numbering#Most_significant_bit) were set to `0`, and the value of MSB remained unchanged
* from the result, all we need to do is to check whether the result is `0` or not
* if the result is `0`, then the char is in ASCII
### How `is_ascii` (64-bit version) works?
* similarly, we can apply the same method to `is_ascii` (64-bit version)
* we simply extend `0x80` to `0x8080808080808080` and perform bitwise AND on the input string (8 chars at once) until the result is non-zero or less than 8 chars remain
* by doing so, if the result of bitwise AND is `0`, it means that the 8 chars are all in ASCII
* if there are less than 8 chars remain in the input string, process them with `is_ascii` (8-bit version)
:::success
Answer: `(d)` `0x8080808080808080`
:::
<!-- ### Why `memcpy`?
### Advanced Applications
#### Example 1
A function that can check if a string of known length contains letters
#### Example 2
A function that can check if an input string doesn't contain any invalid characters
-->
## Problem 2
:::info
打英文好累，我還是乖乖打中文
:::
### Required Functions
* 將十六進為表示的字元轉為數值 (case insensitive)
* e.g.
* `0` => 0
* `1` => 1
* `A`, `a` => 10
* `F`, `f` => 15
### Code Snippets
* `hexchar2val`
```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;
}
```
#### MASK = ?
* `(a)` `0x10`
* `(b)` `0x20`
* `(c)` `0x40`
* `(d)` `0x60`
* `(e)` `0x80`
#### AAA = ?
* `(a)` 3
* `(b)` 2
* `(c)` 1
* `(d)` 0
#### BBB = ?
* `(a)` 7
* `(b)` 6
* `(c)` 5
* `(d)` 4
### 解題思路
:::info
以下摘自 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`
:::
* 首先考慮數字 `'0'`~`'9'`, 僅需將 `0x3X` 的 `3` 過濾掉即可得到正確數值
* 再來考慮英文的大小寫，可以由上方提供的資訊看出 `'a'` 與 `'A'` 都是從 `0xX1` 開始，而我們期望 `'a'` 與 `'A'` 的值都變成 10，因此需要做的事情就是先將 `'a'` 與 `'A'` 轉換成 `0x01` 再加上 9 (`0000 1001`) 即可得到期望的數值 (適用於所有英文字元)
* 那麼要如何取得 9 (`0000 1001`) 呢? 這時需要運用 bitwise AND 的技巧得到英文字元的特徵，同時也必須過濾掉數字 `'0'`~`'9'` 的特徵 (`0x3X` 的 `3`)
| 字元 | 二進位表示 | 過濾後 (letter) |
|:-----:|:----------:|:---------------:|
| `'1'` | 0011 0001 | 0==0==00 0000 |
| `'a'` | 0110 0001 | 0==1==00 0000 |
| `'A'` | 0100 0001 | 0==1==00 0000 |
* 根據上面的表格來推斷，只要將字元和 `0100 0000` 做 bitwise AND 之後就可以萃取出左邊第二個 bit 的值，因此可以得知 `MASK` = `0x40` (`0100 0000`)
* 上面有提到，將英文字元轉換成值的時候需要加上 9 (`0000 1001`)，這時只要運算 `shift = (letter >> 3) | (letter >> 6)` 就可獲得我們想要的值
| 字元 | shift |
|:------------------------:|:---------:|
| `'0'`~`'9'` | 0000 0000 |
| `'a'`~`'z'`, `'A'`~`'Z'` | 0000 1001 |
* 最後用 `(in + shift) & 0xf` 取得最小的 4 個位元就是答案了!
:::success
Answer:
MASK = `0x40`
AAA = 3
BBB = 6
:::
## Problem 3
### Required Functions
* 快速取餘數
### Code Snippets
* `quickmod`
```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;
}
```
#### XXX = ?
* `(a)` `0x00F000F000F00080`
* `(b)` `0xF000F000F000F000`
* `(c)` `0x0F0F0F0F0F0F0F0F`
* `(d)` `0xF0F0F0F0F0F0F0F0`
* `(e)` `0x8888888888888888`
* `(f)` `0xFFFFFFFFFFFFFFFF`
### 解題思路
* 從第 6 行可以看出 `((__uint128_t) M * n) >> 64` 是 `n / D` 的商 (`quotient`)
* 從上述的程式可以推導出:
$$
M \times n = quotient \times 2^{64} = \frac{n}{D} \times 2^{64}\\
\Rightarrow M = \frac{2^{64}}{D}
$$
* 但是 `uint64_t` 的上限只到 $2^{64} - 1$, 因此代入 $XXX = 2^{64} - 1$ 後再加 $1$
* 可得到 $M = \lfloor{\frac{2^{64} - 1}{D}}\rfloor + 1$
#### 驗證 $M = \lfloor{\frac{2^{64} - 1}{D}}\rfloor + 1$ 的正確性
* 已知:
$$
quotient = \lfloor{\frac{n}{D}}\rfloor
$$
* 且假設:
$$
2^{64} - 1 = aD + r; \text{ where 0} \leq \text{ r < D}
$$
* 證明下列式子成立:
$$
\lfloor{\frac{n}{D}}\rfloor
= \lfloor{\frac{(\lfloor{\frac{2^{64} - 1}{D}}\rfloor + 1) \times n}{2^{64}}}\rfloor
$$
* 推導過程:
$$
\lfloor{\frac{(\lfloor{\frac{2^{64} - 1}{D}}\rfloor + 1) \times n}{2^{64}}}\rfloor
= \lfloor{\frac{(a + 1) \times n}{2^{64}}}\rfloor
= \lfloor{\frac{\frac{(a + 1) \times D}{D} \times n}{2^{64}}}\rfloor
= \lfloor{\frac{\frac{(a + 1) \times D}{D} \times n}{aD + r + 1}}\rfloor
= \lfloor{\frac{\frac{aD + D}{D} \times n}{aD + r + 1}}\rfloor
$$
因為 $(aD + D) \ mod \ D = 0$, 所以可以將除數 $D$ 移到被除數 $n$ 底下:
$$
\lfloor{\frac{\frac{aD + D}{D} \times n}{aD + r + 1}}\rfloor
= \lfloor{\frac{aD + D}{aD + r + 1}}\rfloor \times \lfloor{\frac{n}{D}}\rfloor
$$
由於 $r + 1 \leq D$，因此:
$$
\frac{aD + D}{aD + r + 1} \geq 1
\Rightarrow \lfloor{\frac{aD + D}{aD + r + 1}}\rfloor = 1
$$
將上面結果代回推導式中:
$$
\lfloor{\frac{aD + D}{aD + r + 1}}\rfloor \times \lfloor{\frac{n}{D}}\rfloor
= 1 \times \lfloor{\frac{n}{D}}\rfloor
= \lfloor{\frac{n}{D}}\rfloor
= quotient
$$
* 證明完成!
:::success
Answer: `(f)` `0xFFFFFFFFFFFFFFFF`
:::
## Problem 4
### Required Functions
* 判斷是否能被整除
### Code Snippets
* `divisible`
```c=
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
#### YYY = ?
* `(a)` `M + 1`
* `(b)` `M`
* `(c)` `M - 1`
* `(d)` `(M >> 1)`
* `(e)` `(M << 1)`
### 解題思路
* 延續上一題，已知 $M = \frac{0xFF...F}{3} + 1$，算出 $M = 0x5555\ 5555\ 5555\ 5555 + 1$
* 已知 $D = 3$，因此考慮 $n = 3k，3k + 1，3k + 2$ 三種情況
* $n = 3k:$
$M \times n = (0x555...5 + 1) \times 3k = (0xFFF...F + 3) \times k = 0x000...02 \times k = 2k$
* $n = 3k + 1:$
$M \times n = (0x555...5 + 1) \times (3k + 1) = (0x555...5 + 1) \times 3k + (0x555...5 + 1) = 2k + M$
* $n = 3k + 2:$
$M \times n = (0x555...5 + 1) \times (3k + 2) = (0x555...5 + 1) \times 3k + (0x555...5 + 1) \times 2 = 2k + 2M$
從上面結果可發現，只要 $n \times M < M$ 就代表 $n$ 可以被 $D$ 整除，因此可能的選項有 YYY = `M - 1` 或 `(M >> 1)`。如果考慮極端值 $n = 0xFFFF\ FFFF$，則 $k\_max = 0x5555\ 5555$
結果...還是沒有辦法剔除其中一個選項
:::success
Answer: `(c)` `M - 1` or `(d)` `(M >> 1)` (maybe)
:::
## Problem 5
### Required Functions
* 將指定的字串 (或部分字串) 的英文字母全改為小寫
### Code Snippets
* `strlower` (process one `char` in each iteration)
```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]);
}
}
```
* `strlower_vector` (process 8 chars at once)
```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);
}
```
#### VV1 = ?
* `(a)` `0x10`
* `(b)` `0x20`
* `(c)` `0x40`
* `(d)` `0x60`
* `(e)` `0x80`
#### VV2 = ?
* `(a)` `(-1)`
* `(b)` `0`
* `(c)` `1`
#### VV3 = ?
* `(a)` `(-1)`
* `(b)` `0`
* `(c)` `1`
#### VV4 = ?
* `(a)` `0x10`
* `(b)` `0x20`
* `(c)` `0x40`
* `(d)` `0x60`
* `(e)` `0x80`
### 解題思路
* `strlower_vector` 中的 `PACKED_BYTE(b)` 可以在 64 個 bit 中萃取出最小的 8 個 bit，然後將這 8 個 bit 複製到整個 64 bit
* 例如: `PACKED_BYTE(0x80)` => `0x8080 8080 8080 8080`
#### VV1
* VV1 沿用 [Problem 1](#Problem-1) 的技巧來判斷字串裡的字元是否都在 ASCII 表裡面，因此答案選擇 `0x80`
#### VV2, VV3
* 從 `strlower_vector` 的第 14, 15 行中，我們可以推斷它在判斷字串是否在 `'A'` 至 `'Z'` 的範圍裡
* `A`: 只要 `*chunk` 中的 字元都在 `'A'` 之後，那麼 `*chunk + PACKED_BYTE(128 - 'A' + VV2)` 的 8 的倍數的位元都會是 `1`
* `Z`: 只要 `*chunk` 中的 字元都在 `'Z'` 之前，那麼 `*chunk + PACKED_BYTE(128 - 'Z' + VV3)` 的 8 的倍數的位元都會是 `0`
| char | binary | `128 - 'A' + VV2` | `128 - 'Z' + VV3` | MSB_1 ^ MSB_2 |
|:-----:|:---------:|:-----------------:|:-----------------:|:-------------:|
| `' '` | 0010 0000 | ==0==101 1111 | ==0==100 0101 | 0 |
| `'A'` | 0100 0001 | ==1==000 0000 | ==0==110 0110 | 1 |
| `'Z'` | 0101 1010 | ==1==001 1001 | ==0==111 1111 | 1 |
| `'a'` | 0110 0001 | ==1==010 0000 | ==1==000 0110 | 0 |
* 為了達到上述結果，VV2 必須是 `0`，VV3 則必須是 `(-1)`
#### VV4
* 由於我們只需要 MSB (每 8 個 bit 取一個 MSB) 來判斷是否在範圍內，因此使用 `& 0x80` 來過濾掉非必要的資訊
:::success
Answer:
VV1 = `0x80`
VV2 = 0
VV3 = (-1)
VV4 = `0x80`
:::
## Problem 6
### Required Functions
* 找到只出現過一次的值
### Code Snippets
* `singleNumber`
```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;
}
```
#### KKK = ?
* `(a)` `higher`
* `(b)` `lower`
* `(c)` `~higher`
* `(d)` `~lower`
* `(e)` `0xFFFFFFFF`
#### JJJ = ?
* `(a)` `higher`
* `(b)` `lower`
* `(c)` `~higher`
* `(d)` `~lower`
* `(e)` `0xFFFFFFFF`
### 解題思維
我們需要 2 個變數 `higher` 和 `lower` 來表示 3 個狀態，分別是 `00`，`01`，`10`，並且根據當前的 `higher`，`lower` 和 `input` 的值來決定下一個 `higher` 和 `lower` 的值
* 以下的 `input` 只有一個 bit 的長度，但此概念也可套用在多個 bit 的情況
#### Transition
* $input\_bit = 1:$ `00` => `01` => `10` => `00` => ...
* $input\_bit = 0:$ 不改變狀態
* Transition table (overall):
| higher state | lower state | input bit | (higher state)' | (lower state)' |
|:------------:|:-----------:|:---------:|:---------------:|:--------------:|
| 0 | 0 | 1 | ==0== | ==1== |
| 0 | 1 | 1 | ==1== | ==0== |
| 1 | 0 | 1 | ==0== | ==0== |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
#### `lower` transition:
* Transition table (`lower`):
| higher state | lower state | input bit | (lower state)' |
|:------------:|:-----------:|:---------:|:--------------:|
| 0 | 0 | 1 | ==1== |
| 0 | 1 | 1 | ==0== |
| 1 | 0 | 1 | ==0== |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 |
* 如果 $input\_bit = 0$，`lower` 不做改變，如果 $input\_bit = 1$, `lower` 狀態會變化 (`0` => `1`; `1` => `0`)，所以我們可以使用 $lower' = input\_bit \hat{} lower$ 來達到我們想要的變化
* 但是可以發現，當 $higher = 1$ 且 $input\_bit = 1$ 的時候， $lower'$ 會等於 `1`，並非我們所期望的 `0`。因此，我們也把 `higher` 加入考量
* 經過觀察，只有在 $higher = 1$ 的時候需要將 $input\_bit \hat{} lower$ 的值反轉 (`1` => `0`)，所以我們選擇先反轉 `higher`，將其變成 `0` 之後再跟 $input\_bit \hat{} lower$ 進行 bitwise AND 運算
* 最終，我們得到:
$lower' = (input\_bit \hat{} lower) \& (\text{~} higher)$
* `input` 為多個 bit 時仍適用上方公式，因此可得:
$\Rightarrow lower' = (input \hat{} lower) \& (\text{~} higher)$
#### `higher` transition:
* Transition table (`higher`):
| higher state | (lower state)' | input bit | (higher state)' |
|:------------:|:--------------:|:---------:|:---------------:|
| 0 | ==1== | 1 | ==0== |
| 0 | ==0== | 1 | ==1== |
| 1 | ==0== | 1 | ==0== |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 |
* 如果 $input\_bit = 0$，`higher` 不做改變，如果 $input\_bit = 1$, `higher` 狀態會變化 (`0` => `1`; `1` => `0`)，所以我們可以使用 $higher' = input\_bit \hat{} higher$ 來達到我們想要的變化
* 但是可以發現，當 $lower' = 1$ 且 $input\_bit = 1$ 的時候， $higher'$ 會等於 `0`，並非我們所期望的 `1`。因此，我們也把 `lower'` 加入考量
* 經過觀察，只有在 $lower' = 1$ 的時候需要將 $input\_bit \hat{} higher$ 的值反轉 (`0` => `1`)，所以我們選擇先反轉 `lower'`，將其變成 `0` 之後再跟 $input\_bit \hat{} higher$ 進行 bitwise AND 運算
* 最終，我們得到:
$higher' = (input\_bit \hat{} higher) \& (\text{~} lower)$
* `input` 為多個 bit 時仍適用上方公式，因此可得:
$\Rightarrow higher' = (input \hat{} higher) \& (\text{~} lower)$
:::warning
:warning: `lower` 已在 **lower transition** 中被更新過了，因此 $higher' = (input \hat{} higher) \& (\text{~} lower)$ 中的 `lower` 即代表 `(lower state)'`
:::
:::success
Answer:
KKK = `~higher`
JJJ = `~lower`
:::
<!-- ## References -->
Sign in with Wallet
Connect another wallet