# 2020q3 Homework2 (quiz2)
contributed by < `dalaoqi` >

## Outline
[TOC]

## 測驗一

#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;
}

7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。
上面 code 是以一個字元的方式判斷是否是有效的 ASCII code (0~127) 。
若 & 0x80(1000000) 不為0，代表該字元大於127，不是有效的 ASCII code。
但上述的 code 逐一字元比對的效率低，在 64 位元的架構下，我們嘗試一次比對 64 位元的資料 (即 word size)，程式碼改寫如下:

#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;
}

改善原本 code 效率低落的問題，一次比對8個字元，因此 `MMM` 為 `0x8080808080808080`。

### 延伸問題
Why memcpy?
> 為了和 後面的 0x8080808080808080 做 and operation。也就是在While 中每次 iteration 會將 string 的其中 8個字元位址複製給 `payload`。

## 測驗二

uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & 0x40;
    const uint8_t shift = (letter >> 3) | (letter >> 6);
    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，其他輸入都有對應的數值。

hexchar2val(‘F’) 和 hexchar2val(‘f’) 回傳 15、hexchar2val(‘A’) 和 hexchar2val(‘a’) 回傳 10。

| char | hex | binary |
| -------- | -------- | -------- |
| 0 | 0x30 | 00110000 |
| 9 | 0x39 | 00111001 |
| A | 0x41 | 01000001 |
| a | 0x61 | 01100001 |
| F | 0x46 | 01000110 |
| f | 0x66 | 01100110 |

根據表格可以找出規律：
* 0~9 的後四位，就是要回傳的值。
* 非數字字元和數字字元可以由第二位元判斷。

且根據 `(in + shift) & 0xf` 可以得知回傳最低4 bits。因此可以推論出 `MASK` 為 `0x40` (01000000)。

所以根據 `MASK` ，若輸入是數字的話， `letter` 就會是 `00000000` ， `shift` 也會是 `00000000` 。 因此直接回傳輸入的最低4 bits。
若輸入的是非數字， `letter` 就會是 `01000000` 。 根據`(in + shift) & 0xf` 推論， `F`、`f` 應該要回傳15(1111)，因此可以得知 `shift` 要是 1001，因此 `AAA` 為3， `BBB` 為6。

## 測驗三

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;
}

從 return 可以看出餘數是被除數 - 商 * 除數得到的，套用$n \times \frac{\frac{2 ^ N}{d}}{2 ^ N}$ 推論可得：

\begin{align}
n \% 3 &= n - \left \lfloor {\frac{n}{3}} \right \rfloor \times 3 \\
&= n - \left \lfloor n \times \frac{\frac{2 ^ {64}}{3}}{2 ^ {64}}\right \rfloor \times 3 \\
&= n - \left \lfloor n \times {\frac{2 ^ {64}}{3}} \times {\frac{1}{2 ^ {64}}}\right \rfloor \times 3 \\
\end{align}

從式子中可以看出 $M = {\frac{2 ^ {64}}{3}}$，`XXX` 最接近的答案就是 `0xFFFFFFFFFFFFFFF`。
但其實程式碼轉成數學式其實是：$\frac{2 ^ {64}-1}{3} + 1$，把它代回上面的式子:

\begin{align}
\frac{{\frac{2 ^ {64}-1}{3} + 1} \times n}{2 ^ {64}} &=
\frac{{\frac{2 ^ {64} \times n -n}{3} + n}}{2 ^ {64}} \\ &=
\frac{2 ^ {64} \times n -n}{3 \times 2 ^ {64}} + \frac{n}{2 ^ {64}} \\ &= \frac{n}{3} - \frac{n}{3 \times 2 ^ {64}} + \frac{n}{2 ^ {64}} \\ &= \frac{n}{3} + \frac{2n}{3 \times 2 ^ {64}} < \frac{n}{3} + \frac{n}{2 ^ {64}}
\end{align}

因為 $n, d < 2^{32}$， $\dfrac{n}{d}$ 的餘數最大值為 $\dfrac{2^{32}-2}{2^{32}-1}$ 又 $\dfrac{n}{2^{64}} < \dfrac{1}{2^{32}}$，因此$M = {\dfrac{2 ^ {64}}{3}}$ 或 $M = \dfrac{2 ^ {64}-1}{3} + 1$ 結果都會是一樣的。

## 測驗四
延伸測驗 3，我們想判斷某個數值能否被指定的除數所整除，在 D 和 M 都沿用的狀況下，程式碼如下:

bool divisible(uint32_t n)
{
    return n * M <= M-1;
}

從前一題可以看出 $(n \times M) >> 64 = \left \lfloor {\dfrac{n}{3}} \right \rfloor$ ，也就是商的部分， $n \times M$ 則是保留小數的部分。
根據上一題：
\begin{align}
M &= \dfrac{2 ^ {64}-1}{3} + 1 \\
&= \left \lfloor {\dfrac{2 ^ {64}}{3}} \right \rfloor + 1
\\ M - 1 &= \left \lfloor {\dfrac{2 ^ {64}}{3}} \right \rfloor
\end{align}

$M-1 = \left \lfloor {\frac{2 ^ {64}}{3}} \right \rfloor$ 表示為 $\frac{1}{3}$ 的小數部分，若 $n \times M < M - 1$，表示可以被3整除。

## 測驗五

#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 重複擴充成64位元的 unsign int。
* 第一小題和測驗一很像，來判斷式是否為 ascii ，因此 `VV1` 為 `0x80`。
* 變數 A、Z 是用來判斷大寫字母的區間。 A 變數的部分會去計算0x80和 `'A'`之間的距離再加上待測字元，若結果的MSB = 1, 代表待測字元 >= `'A'`。 Z 變數的部分會去計算0x80和 `'Z'-1`之間的距離再加上待測字元，若結果的MSB = 1, 代表待測字元 >= `'Z'`，MSB = 0，代表待測字元 <= `'Z'`。
* 上述的例子分別代入 `'A'` 和 `'Z'` 會更清楚， `VV2` = 0，`VV3` = (-1) 。
* 看到 `*chunk ^= mask;` 這行，就是在做大小寫的轉換，只是前面已經先篩選過了，所以這行只是純粹的大寫轉小寫。參考[運用 bit-wise operator](https://hackmd.io/@sysprog/c-numerics#%E9%81%8B%E7%94%A8-bit-wise-operator)
:::info
:mag_right::mag_right::mag_right:
('a' ^ ' ') // 得到 'A'
('A' ^ ' ') // 得到 'a'
:::
* 空白space為 `0b00100000` 因此在變數 mask 的地方才會去做 `>>2`。而剛剛已經得知若字元處在 `'A'` ~ `'Z'` 區間，`A ^ Z`會是 0b10000000 ，因此 `VV4` 為 `0x80`。

## 測驗六

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

* 做 XOR 運算時，不同得1，相同得0，如下方表格所示。

| A | B | A ^ B |
| -------- | -------- | -------- |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

* `A ^ A` = 0
* 交換率
* 運算順序不影響運算結果。

XOR 以上的特性可以得出 `A ^ B ^ A = B` 這種特性，找出出現一次的數值。此題就是運用此方式來解決。

`lower` 和 `higher` 是用來紀錄數值讀累計次數， `lower` 代表出現過一次， `higher` 代表出現兩次。

為了說明方便假設變數都是只有一個位元。

若陣列的第一個 input 為 1 ，所以 `lower ^ nums[0]` 就會是 `1`。 在經過 `lower &= KKK;` 運算後也要為 `1`，所以可能的答案為 `~higher` 或 `0xFFFFFFFF`。不過考慮到 `lower` 應該要像 `higher` 一樣受到另一個變數的影響，且若選 `0xFFFFFFFF` ，和沒有做這行 `&` 運算是一樣的，因此 `KKK` 為 `~higher`。
而在 `higher ^ nums[0]` 後， `higher` 也變為 `1`，不過應該要是 `0` 。因此， `higher &= JJJ;` ， `JJJ` 應該為 `~lower`。