# 2020q3 Homework2 (quiz2)
contributed by < ddj5523fa >

---

### 想法 & 思考

測驗一

題目:

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

ANS: MMM = (d) 0x8080808080808080 。

回答:
1.
(1)該題前段有個比較原始版的程式碼提到0x80，首先先知道0x80是128的16進制
轉2進制是1000 0000 ；而ACII 是0~127，所以當str[i]跟0x80會等於true ，代表str[i]大於等於128，超過ACII的範圍了，以此來判斷is_ascii。

(2)上面程式碼則是在 64 位元的架構下，我們嘗試一次比對 64 位元的資料 (即 word size)。上面程式中，str中一個是1byte(8位元)，而一次檢查64bit(8byte)，所以每一輪過後 "+8"。

(3)memcpy() 的實做是跟data alaigment有關，會先使 memory address目前位址到 word aligned 的位址，然後以 word 為單位做複製。
[此段是參考某臉書的貼文](https://www.facebook.com/pcman.im/posts/1623916640981340/)
還有參考:作業中延伸學習的提示與詳閱。

(4)承上(1)、(3)得知每次進行式一個word(64bbit是8byte)，而每byte中要判定其是否是 ACII 是與 0x80 做 AND，所以8byte便是 ==0x8080808080808080==

2.判斷是否是英文字母，也許可參考測驗2解析器 (parser)。//=="未完"==

-------------------------------------------------------
測驗二
開發解析器 (parser) 時，常會將十六進位表示的字串 (hexadecimal string) 轉為數值，例如 '0xF' (大寫 F 字元) 和 '0xf' (小寫 f 字元) 都該轉換為 15。考慮以下不需要分支 (branchless) 的實作:

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

1.
(1)0x30的2進制為0011 0000 =>0x31到0x39都是數字
0x40的2進制為0100 0000
0x60的2進制為0110 0000
=>0x41以後包含了大小寫英文字母。
所以程式碼==const uint8_t letter = in & MASK;==
是先區別開數字與英文字母。
而==MASK=0x40== <ANS>

(2)接下來透過觀察可知:(拿0(0x30)a(0x41)、A(0x61)來比較與觀察)

|EX:|0|a|A|
|----|----|----|----|
|HEX:|0x30|0x41|0x61|
|Binary:|0011 0000|0100 0001|0110 0001|
|output(val):|0|10|10|
|output(Binary)|0000 0000|0000 1010|0000 1010|
而依據程式碼可得知:如果in是英文字母，則letter=0x40=0100 0000
所以讓letter可以變成A的output這樣的話便是右移3格與右移6格的letter做 OR:會得0000 1001 (相當於+9)配合後面return的程式碼。
==const uint8_t shift = (letter >> AAA) | (letter >> BBB);==
==可得知AAA、BBB的答案為3與6。== <ANS>

----------------------------------------------------

測驗三:

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

原理:
1.首先依題目，其打算先取得餘數與商數(quotient) 然後可簡化成 * 與+ 還有位移的運算。
2.先從上面程式碼quickmod func.開始看起，得知商等於M*n>>64;而依據題目我們可知道: $$quotient = \frac{n}{D} = n \times \frac{2^N}{D} \times \frac{1}{2^{N}}$$
==p.s.== 題目上此處提示寫成了$$ n \times \frac{\frac{2^N}{d}}{2^N} $$讓人會誤以為是變成 $$ {2^{N}} \times {2^{N}} $$再除 d ，思考了很久。

3. 上述程式碼:quotient = ((__uint128_t) M * n) >> 64;
可以知道 >>64 可看作除以2的64次方，根據承2. 的公式:
得到 $$ \frac{n}{D} = n \times M \times \frac{1}{2^{64}}$$
代入 M 的定義: $$ \frac{n}{D} = n \times \frac{1}{2^{64}} \times (\frac{(XXX)}{D}+1)----(1)$$
應該要符合，$$quotient = \frac{n}{D} = n \times \frac{2^N}{D} \times \frac{1}{2^{N}}----(2)$$ 所以可得知 XXX 中必定包含 << 64 。

上述的兩等式(1)(2)合併一下 可得出:$$ (\frac{(XXX)}{D}+1)=\frac{2^N}{D} $$ ，(此時N=64) ； $$ XXX={2^{64}}-1 $$

==答案:XXX = 0xFFFFFFFFFFFFFFFF==

----------------------------------------------------

測驗四:

假設D為d時，$\frac{n}{d}$的餘數為0,1,2,...,d-1 可分別討論:

1.餘數=0時候:(n set k*d+0)
=> $n \times M = k*d \times (\frac{2^{64}-1}{d}+1) = k*2^{64}-k +kd + 0M$

2.餘數=1，n set kd+1:
=> $n \times M = (kd+1) \times (\frac{2^{64}-1}{d}+1) = k*2^{64}-k +kd + M$

3.餘數=2，n set kd+2:
=> $n \times M = (kd+2) \times (\frac{2^{64}-1}{d}+1) = k*2^{64}-k +kd + 2M$

4.餘數=3，n set kd+3:
=> $n \times M = (kd+3) \times (\frac{2^{64}-1}{d}+1) = k*2^{64}-k +kd + 3M$
.
.
.
.
5.當餘數來到d-1時候 ，n set kd+(d-1)
=> $n \times M = (kd+(d-1)) \times (\frac{2^{64}-1}{d}+1) = k*2^{64}-k +kd + (d-1)M$

=>根據上面觀察 只有1.能被整除 而1 沒有像其他假設一樣有多出?個M。
==補充==:上述有提到的，每個都會算出 $k*2^{64}-k$，在64位元下$2^{64}$的會變成0(有數值1的部分溢位被除去了)，所以$k*2^{64}-k +kd + 0M$會變成 $0-k+kd+0M$會小於M
所以，n*M < M時候代表可整除， 而程式碼為<= 所以選擇題選項應選擇M-1!

----------------------------------------------------

測驗五:程式碼有用到在測驗二上

----------------------------------------------------
測驗六:

以下程式碼為 LeetCode 137. Single Number II 的題解:

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

1.
(1)第一個想法是，A = A XOR B 兩次會變回原本的，所以lower在XOR後，下一行lower &=KKK 不應該改變結果，否則可能影響XOR的用處。然後實際用例子去run一次試試看!，KKK若不是因為選擇題，(我可能會持續想很久也不見得有答案。)

延伸學習2+3.
[參考網址](https://www.cnblogs.com/grandyang/p/4263927.html)

2.Leetcode 我是依據上面參考網址教學的其中一種方式寫的。

3.延伸衝婦到4次5次甚至有規律個式子，我以上述的一個方法覺得比較好整合來作為我的實作:

int singleNumber(int nums[], int numsSize, int times)
{
    int res = 0;
    for (int i = 0; i < 32; ++i)
    {
        int sum = 0;
        for (int j = 0; j < numsSize; ++j)
        {
            sum += (nums[j] >> i) & 1;
        }
        res |= (sum % times) << i;
    }
    return res;
}

此方法思路為:以每一個bit分別做Sum，再去mod 次數(重複3、4、5...)
最後每一bit留下的值組合出的數字便是沒有單獨的該解答!

所以程式碼中第9行便是一直左移將bit拿到 &1是為了確保只有比較最低位元。
res |= (sum % fre) << i; 便是將位元左移損失的倍率還原回來。

for迴圈用32次是因為int： 4個位元組 所以是32 bit。

不過此方法在leetcode上不會過關，因為當字串遇到負數會runtime error。
所以我在此程式碼基礎上```res |= (sum % times) << i;```多加了(unsigned int)

=>``` res |= (unsigned int)(sum % 3) << i; ```