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

> [2020q3 第 2 週測驗題](https://hackmd.io/@sysprog/2020-quiz2)

## 測驗 1
選擇0x8080808080808080，因爲將其轉換爲二進制後可容易見到

1000000010000000100000001000000010000000100000001000000010000000

爲[10000000] 重複8次

這是一個檢查8個 byte e.g. 01111111 是否超過127，即檢查是否爲題目定義的有效的 ASCII 字元。

因爲64 位元架構的CPU一次可以讀取 64 bit，因此有以上一次檢查8個位元組的方式。

至於爲甚麼要用 memcpy, 而不是直接 casting 從而省去 copy 的時間呢？

uint64_t *payload = (uint64_t *);

留意到這裏 payload 直接獲取 str 的 位址，而這個位置未必是對uint64_t word aligned 的。

而 memcpy 則 可以保證 word aligned, 參考glibc的做法由於我們只是 copy 8個 bit，所以在此實作上是逐 byte copy。

參考
[非對齊訪問和Alignment Fault](https://www.itread01.com/content/1544492598.html)
[glibc](https://github.com/lattera/glibc/blob/master/string/memcpy.c)

## 測驗 2

如果將題目的輸入寫成 8 bit 二進制的形式, 默認MSB在最左邊

'0' - '9': 00110000 ... 00111001
'a' - 'f': 01100001 ... 01100110
'A' - 'F': 01000001 ... 01000110

則易見從左往右第二個 bit 決定是數字或是字母，因此
MASK 爲 0x40 (01000000),

'0' - '9' 與遮罩&運算後全爲零，與0xf(00001111) & 運算後可得 0-9

字母與遮罩&運算後全爲01000000，已知與0xf(00001111) & 運算目的是取最右邊的四位，對於字母而言，需要加9。

letter = 0b0100000

const uint8_t shift = (letter >> AAA) | (letter >> BBB);

因此需要用 | 運算 合成 9 （00001001），AAA = 3 , BBB = 6

## 測驗 3

容易知道 N = 64 , 而M是接近$\frac{2^n}{d}$ 的數因此0xFFFFFFFFFFFFFFFF，具體未明。

參考[別人的答案](https://hackmd.io/@RinHizakura/SJ5NuIANP)後，修改如下（只是括號位置有錯）

> 在 [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) 也有相關的技巧運用。在 div.c 的註解中，有比較詳細數學推導：
> * 假設 n / d 是整數
> * 對於式子
> $$
>   \left\lfloor{\left\lceil\frac{2^k}{d}\right\rceil \times \frac{n}{2^k}} \right\rfloor  
> $$
> 我們可以拆解成: (注意這裡的除法除至小數點以下，而非取整)
> $$
>     = \left\lfloor{\frac{2^k+r}{d} \times \frac{n}{2^k}} \right\rfloor  
> $$
>     其中 k 為任意整數，而 r = $(-2^k)\mod d$
> * 展開上述的式子，可以得到:
> $$
>  = \left\lfloor{\frac{2^k}{d} \times \frac{n}{2^k} + \frac{r}{d} \times \frac{n}{2^k}} \right\rfloor  \\
>   = \left\lfloor{\frac{n}{d} + \frac{r}{d} \times \frac{n}{2^k}} \right\rfloor  
> $$
> * 如前所述，由於假設 $\frac{n}{d}$ 為整數(小數點部份為 0)，因此上面的式子可以寫成：
> $$
>  \frac{n}{d} + \left\lfloor{\frac{r}{d} \times \frac{n}{2^k}} \right\rfloor  
> $$
> 也就是說，如果可以滿足
> $$
> \frac{r}{d} \times \frac{n}{2^k} < 1
> $$
> 則 n / d 可以被改寫成   $\left\lfloor{\left\lceil\frac{2^k}{d}\right\rceil \times \frac{n}{2^k}} \right\rfloor$
> * 因為  r < d 且 r / d < 1 總是滿足，為使 $n / 2^k$ < 1，對於不會超出 $2^{32}$ 的 n，可以令 k = 32 來滿足此條件

有了以上推導以後，容易知道 M=$\lceil\frac{2^k}{d}\rceil$, 接下來只要證明爲甚麼 $M = \lfloor\frac{2^k-1}{d}\rfloor + 1 = \lceil\frac{2^k}{d}\rceil$

分情況討論，
1. 如果2的 k 次方是 d 的倍數，則 $\lfloor\frac{2^k-1}{d}\rfloor + 1 = \frac{2^k}{d} - 1 + 1=\lceil\frac{2^k}{d}\rceil$, 因爲$\frac{2^k}{d}$是整數,對其分子減1再向下取整會有上述效果。
2. 如果2的 k 次方不是 d 的倍數，則 $\lfloor\frac{2^k-1}{d}\rfloor + 1 = \lfloor\frac{2^k}{d} - \frac{1}{d}\rfloor + 1=
\lfloor\frac{2^k}{d} \rfloor + 1=\lceil\frac{2^k}{d}\rceil$, 因爲
$\frac{2^k}{d}$的小數部分(餘數除以d) 大於或等於 $\frac{1}{d}$ , 因此多減一個 $\frac{1}{d}$ 並不會影響向下取整。

因此 $M = \lfloor\frac{2^k-1}{d}\rfloor + 1$