# 2020q3 Homework2 (quiz2)
contributed by < `quantabase13` >
# :memo: Table of Contents
[TOC]

---
## 程式運作原理
### 測驗 1

#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/*MMM*/)
            return false;
        i += 8;
    }
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}

* ASCII code 共有128個字元，以7位 bit 進行編碼 ; 另外， char 類的大小為8個 bits。所以若要確定一個 char 是否為 ASCII code ，只要確認其最高位是否為1即可。
* `is_ascii` 的 `while` loop 裡聲明了長度為64 bits 的 `payload`，並且透過 `memcpy` 從地址 `str + i` 複製8個 bytes 到 payload。由於一個 `char` 長1個 byte，`payload` 裝有8個 bytes，因此對 `payload` 做 bitwise operation 可以一次檢測 8 個 char 是否屬於 ASCII code。
* 當剩餘的 char 數量 < 8 時(也就是 i + 8 > size)，就換成一次檢查1個 byte。

### 測驗 2

uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & 0x40/*MASK*/;
    const uint8_t shift = (letter >> 3/*AAA*/) | (letter >> 6 /*BBB*/);
    return (in + shift) & 0xf;
}

數字的 ASCII code 高4位為0011，大寫英文字母的高4位為 0100， 小寫英文字母的高4位為 0110。
於是取 `MASk` 為0x40的話，`letter` 在 `in` 為字母時數值為 0100 ，`in` 為數字時數值為 0。另外，不論大小寫字母，低四位皆是從0001開始遞增，因此要輸出其代表的十進位數值的話，只要將低四位+9即可(因為 a 表示十進位的10)。
整體程式碼的思路如下：
1. 計算 `shift` 值（0 => `in`為數字, 9 => `in` 為字母）
2. 取低四位 + `shift` 的值
### 測驗 3

const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF/*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;
}

此題參考 [jemalloc](https://github.com/jemalloc/jemalloc) 原始碼中 [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) 的註解，可以知道實現的思路(以下的除法是實際除法，不是 C 的 rounding 版本)：

$$
\begin{aligned}\lfloor{(
\lceil\dfrac{2^k}{d}\rceil\cdot{\dfrac{n}{2^k}}})\rfloor&=\lfloor{(
\dfrac{2^k+r}{d}\cdot{\dfrac{n}{2^k}}})\rfloor\\&=\lfloor{(
\dfrac{2^k\cdot{n}}{d\cdot{2^k}}}）+{(
\dfrac{r\cdot{n}}{d\cdot{2^k}}})\rfloor\\&=\lfloor{(
\dfrac{{n}}{d}}）+{(
\dfrac{r\cdot{n}}{d\cdot{2^k}}})\rfloor\\&={\frac{n}{d}}+{\lfloor(
\dfrac{r\cdot{n}}{d\cdot{2^k}}})\rfloor
\end{aligned}
$$
其中
${r} = -({2^k})\space{mod}\space{d}\space,{n}= q\cdot{d}$。
由於${r}<{q}$ , 要讓最後的 flooring function 為 0 只要使$\dfrac{n}{2^k}\space < 1$ 即可(原始碼取 k = 32)，就能達成利用$\lfloor{(
\lceil\dfrac{2^k}{d}\rceil\cdot{\dfrac{n}{2^k}}})\rfloor$ 計算 $\dfrac{n}{d}$ 的目標。
了解上述數學式後，就可以對此題的程式碼作相同的數學分析：
此處

$$
\begin{aligned}\lfloor{(
\lceil\dfrac{2^k-1}{d}\rceil\cdot{\dfrac{n}{2^k}}})\rfloor
&=\lfloor{(
\dfrac{2^k+{r}\prime}{d}\cdot{\dfrac{n}{2^k}}})\rfloor\\
&=\lfloor{(
\dfrac{2^k\cdot{n}}{d\cdot{2^k}}}）+{(
\dfrac{{r\prime}\cdot{n}}{d\cdot{2^k}}})\rfloor\\
&=\lfloor{(
\dfrac{{n}}{d}}）+{(
\dfrac{{r\prime}\cdot{n}}{d\cdot{2^k}}})\rfloor\\
&=\lfloor{(
\dfrac{{n-t}}{d}}）+{\dfrac{t}{d}}+{(
\dfrac{{r\prime}\cdot{n}}{d\cdot{2^k}}})\rfloor\\
&={\frac{n-t}{d}}+{\lfloor(
{\dfrac{t}{d}}+\dfrac{{r\prime}\cdot{n}}{d\cdot{2^k}}})\rfloor
\end{aligned}
$$
其中
${r\prime} = 1+(-({2^k})\space{mod}\space{d})\space,{\dfrac{n-t}{d}}= \lfloor{\dfrac{n}{d}}\rfloor$ ，$t < d$。
我們只需讓${(
{\dfrac{t}{d}}+\dfrac{{r\prime}\cdot{n}}{d\cdot{2^k}}})$ < 1 即可。

固定$k = 64$，分析邊界情況。
當$\dfrac{r\prime}{d} = 1$ , $\dfrac{n}{2^k}=\dfrac{2^{32}-1}{2^{64}}$(兩者都達到最大值)時，
取${\dfrac{t}{d}}={\dfrac{(2^{32})-1}{2^{32}}}$
會發現${(
{\dfrac{t}{d}}+\dfrac{{r\prime}\cdot{n}}{d\cdot{2^k}}})$ < 1 ，
由於${\dfrac{(2^{32}-1)-1}{2^{32}-1}} < {\dfrac{(2^{32})-1}{2^{32}}}$，
因此就算${\dfrac{t}{d}}$為最大值(${\dfrac{(2^{32}-1)-1}{2^{32}-1}}$)，
${(
{\dfrac{t}{d}}+\dfrac{{r\prime}\cdot{n}}{d\cdot{2^k}}})$ < 1。
所以可以用$\lfloor{(
\lceil\dfrac{2^k-1}{d}\rceil\cdot{\dfrac{n}{2^k}}})\rfloor$求得$\lfloor{\dfrac{n}{d}}\rfloor$。
### 測驗 4

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

因為${M}=\lfloor\dfrac{2^{64}-1}{d}\rfloor + 1=0x5555555555555556$ , 當 M 與其他數相乘時可以分成三種 case:
1. $M\cdot({3m})=(0x{\overbrace{5555....5555}^{共16個}}+1)\cdot({3m})=0+2m$
3. $M\cdot({3m+1})=(0x{\overbrace{5555....5555}^{共16個}}+1)\cdot({3m+1})=0+2m+(M-1)$
4. $M\cdot({3m+2})=(0x{\overbrace{5555....5555}^{共16個}}+1)\cdot({3m})=0+2m+2(M-1)$
當 m >= 0 時，只有$M\cdot({3m})<(M-1)$。故要判定某數 n 是否為 3 的倍數時，只要確定$M\cdot({n})<(M-1)$即可。
### 測驗 5

#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/*VV1*/)) == 0) { /* is ASCII? */
            uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + 0/*VV2*/); 
            uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + (-1)/*VV3*/);
            uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80/*VV4*/)) >> 2;
            *chunk ^= mask;
        } else
            strlower(s, 8);
    }
    
    k = n % 8;
    if (k)
        strlower(s, k);
}

從程式碼的後半段開始倒著分析，可以發現關鍵在

 uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80/*VV4*/)) >> 2;

這行，因為 0x80 >> 2 = 1 << 5，而大寫字母 A ^= (1 << 5) 就會轉為小寫。所以只要控制 (A ^ Z) 的值就能決定8個 char 中那一個要轉小寫。
PACKED_BYTE(0x80) = $0x\overbrace{8080...8080}^{共8個80}$，我們需要控制每個80最左邊的1，也就是說(A^Z)的每8個 bits 需要長得像以下形式：
1xxxxxxx、0xxxxxxx。
於是我們必須設定只有當 char 確實是大寫字母時， A 和 Z 的 most significant bit 會不同。
可以使用
* $128+char-'A'$
以及
* $128+char-'Z'-1$

的結果來判斷。只有當 char 為大寫字母時兩個數的 most significant bit 不同。所以我們令：
$A = 128+char-'A'$
$B = 128+char-'Z'-1$>，
透過 (A ^ B)&0x80 來決定對應 mask 的其中8 bits。
以向量的形式表示，就能寫成：

            uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + 0/*VV2*/); 
            uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + (-1)/*VV3*/);
            uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80/*VV4*/)) >> 2;

### 測驗 6

int singleNumber(int *nums, int numsSize)
{
    int lower = 0, higher = 0;
    for (int i = 0; i < numsSize; i++) {
        lower ^= nums[i];
        lower &= ~higher/*KKK*/;
        higher ^= nums[i];
        higher &= ~lower/*JJJ*/;
    }
    return lower;
} 

以下參考[csdn yutianzuijin](https://blog.csdn.net/yutianzuijin/article/details/50597413)：
如果題目改成除了 Single Number 外每個數皆出現兩次，那只要這麼寫即可：

int singleNumber2(int *nums, int numsSize)
{
    int lower = 0, higher = 0;
    for (int i = 0; i < numsSize; i++) {
        lower ^= nums[i];
    }
    return lower;
} 

每個 bit 的狀態隨 input 的變化可以用以下真值表表示：
|bit state|input|output|
|-|-|-|
|0|0|0|
|0|1|1|
|1|1|0|
|1|0|1|
可以發現因為只有兩個狀態需要記錄(數出現0次或1次)，所以只需要1個 bit 記錄1個 bit 的變化。
換成原題的話，有三個狀態(數出現0、1、2次)，所以需要2個 bit 記錄狀態(00->01->10->00)。
記錄狀態的 bit 由higher 和 lower 構成，bit 隨input 的變化可以用以下真值表表示：
|higher|lower|input|higher_bit output|lower_bit output|
|-|-|-|-|-|
|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_bit output 即是所求的 Single Number。
可以用以下邏輯表達式表達 lower_bit output:
$$
\begin{aligned}
lower&=lower\cdot\bar{higher}\cdot\bar{input}+\bar{lower}\cdot\bar{higher}\cdot{input}\\
&=\bar{higher} \cdot(lower\cdot\bar{input}+\bar{lower}\cdot{input})\\
&=\bar{higher}\cdot(lower\oplus{input})
\end{aligned}
$$
另外，higher 更新時的所用的 lower 值為新的 lower 值。將新的 lower 值作為輸入，可以畫出以下真值表：
|higher|lower|input|higer_bit output|
|-|-|-|-|
|0|0|0|0|
|0|1|1|0|
|0|1|0|0|
|0|0|1|1|
|1|0|0|1|
|1|0|1|0|
可以用以下邏輯表達式表達 higher_bit output:
$$
\begin{aligned}
higher&=\bar{lower}\cdot{higher}\cdot\bar{input}+\bar{lower}\cdot\bar{higher}\cdot{input}\\
&=\bar{lower} \cdot(higher\cdot\bar{input}+\bar{higher}\cdot{input})\\
&=\bar{lower}\cdot(higher\oplus{input})
\end{aligned}
$$
至此我們得出 higher 和 lower bit 的邏輯表達式，轉換成 C 程式後即得原問題的解。