# 2020q3 Homework2 (quiz2)

## 測驗一
考慮到下列程式碼，必須要一次判斷 64 位元的資料

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

所以要判斷每個 char 是不是 >= 128 ，也就是針對每個 char 做 `str[i] & 0x80` 。
而每個char又是 1 byte ，因此一個 uint64_t 可以塞下 8 個 char ，因此 MMM 為八個 `0x80` 也就是 `0x8080808080808080`

### 測驗一延伸問題
1. 為何使用 `memcpy` ？
考慮到 `str[i]` 可能不是對齊，在 bit wise 操作上會需要載入兩次，所以先宣告一個確定對齊的空間，再做比對比較好。

## 測驗二
考慮到 `0xa` ~ `0xf` 與 `0xA` ~ `0xF` 判斷上是一樣的數字，但是要與 `0x0` ~ `0x9` 不一樣，因此觀察兩者的二進位

'1' = 0011 0001
'a' = 0110 0001
'A' = 0100 0001

觀察到英文的都是 01?0 ，而數字的則是 00?1 ，因此可以藉由第 2 bit 或第 4 bit 來判斷

接著看到下方的程式碼

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

可以判斷是英文的部分要用shift的方式讓他 +10 ，所以知道上方的判斷的是英文字，也就是第 2 bit 的部分，因此 `MASK = 0x40`
而接下來要用 shift 的方式讓其後面 4 bit 可以加十，觀察其二進位

0x40 = 0100 0000
10 = 0000 1001 + 0000 0001

因此需要 shift 3 bit 與 shift 6 bit ，才可以讓 `a` 或是 `A` 變成 10 。因此 AAA 與 BBB 分別為 3 與 6 。

### 測驗二延伸問題

1. 解釋上述程式的運作原理
上面的程式碼需要先判斷是不是英文，如果是英文則將其後四位 +9 ，若不是則加 0 ，最後取後 4 bit 並且回傳。

## 測驗三
考慮以下程式碼：

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

除法的算法為 ${n \over d}=n * {{2^N \over d} \over 2^N}$
而在這裡是除以 $2^{64}$ ，也就是 64 bit
因此 M 就是 ${2^N \over d}$ ，但是 $2^{64}$ 會超過 uint64_t 的大小，因此必須要使用 ${{2^N -1} \over d}+1$ ，所以 XXX 就是 $2^N-1$ 也就是 `0xffffffffffffffff`

### 測驗三延伸題目

1. 解釋上述程式的原理

## 測驗四
考慮以下程式碼：

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

如果 $n \over d$ 有小數的部分，則他不能被整除。
我們要判斷知道 ${2^N \over d}*n$ 是不是不大於 YYY
我們已經知道數字大小就是 64 bit ，因此將 $n \over d$ 乘以 $2^64$ 就是只取其小數的部分
但是如果小數部分小於 $1 \over {2^{64}}$ ，則可以判斷他沒有餘數，所以就是可以判斷它可以被整除。

## 測驗五

PACKED_BYTE(b) 是 (((uint64_t)(b) & (0xff)) * 0x0101010101010101u ，這代表把 b 只取最後一個 byte 並且複製 8 個到 uint64_t
所以 VV1 要判斷 8 個 byte 是不是在 ascii 內，所以就是每個 byte 是不是在 128 的範圍內，因此 VV1 是 `0x80`

接著觀察大小寫的二進位：

a for 0110 0001
A for 0100 0001
128 - A 0011 1111
128 - Z 0010 0110

也就是說，如果要換成小寫的話，就是把 A ~ Z 範圍內的字元的第三 bit 換成 1
所以將 chunk 加上 128 與 'A' 的距離成為結果 A ，以及 128 與 'Z' + 1 的距離成為結果 Z ，
如果 A 超過 128 但是 Z 沒超過 128 ，則可以判斷他是在 A ~ Z 的範圍內。
所以兩者 XOR 後會出現 `1xxx xxxx` ，將他只取第一 bit 並且 >> 2 後，與原本的 chuck 進行 XOR ，
就可以將大寫換成小寫(因為將第三 bit 換成 1 了)
因此可以判斷 VV2 為零， VV3 為 -1 (因為 128 - ('Z' + 1) = 128 - 'Z' - 1)， VV4 為 `0x80` (因為只取第一 bit)

### 測驗五延伸問題
1. 解釋上述程式的原理

## 測驗六
題目要判斷出現一次的數字，其他數字都是出現三次
考慮到任意數 XOR 同一個數字兩次，會變成原本的數字