2020q3 Homework2 (quiz2)

# 2020q3 Homework2 (quiz2) contributed by < `RainbowEye0486` > ## 目錄 [TOC] ## 作業區 ### 測驗一首先了解題目之前的敘述，ASCII碼表示的是128個字元，因此我們的辨識方式就是觀察編碼的範圍是否有超過128，超過的話，有可能是 extended ASCII code 。透過以下程式碼: ```clike= #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; } ``` 解讀程式碼，我們知道傳入的是一個字元陣列，透過 for 迴圈一個一個檢查字串中每個字元是否符合 ASCII code (也就是在128之內)，關鍵便是 `str[i] & 0x80` 這行，透過 AND 的方式能夠知道最高 bit 是否是1(相當於實作一個 bitmask )，因為`0x80`代表++1000++ ++0000++，也就是128或以上的數 `＆` 都不會是 ++0000++ ++0000++，因此直接回傳 `false` 代表字串中至少出現一個或以上的字元不符合 ASCII 標準的字元。接著，回到正式的題目: ```clike= #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; } ``` 我們希望能夠一次比對更多的字元(64位元)，也就是一個word的大小，也就是8個字元，因此在 ```clike=10 while ((i + 8) <= size){ ... ``` 就是說一次抓8個字元比較，剩下不足8個的部分再17~22行依照一開始的方式比對。按照原本的方式比較字串，會是以下表格呈現 | \迴圈數 |1|2|3|4|5|6|7|8| | --- | --- | --- | --- | --- | --- | --- | --- | --- | |**比較值**|0x80|0x80|0x80|0x80|0x80|0x80|0x80|0x80| |**字串**|'c'|'o'|'m'|'p'|'l'|'e'|'t'|'e'| 改寫過後的版本將八個字元合併在一起比較，只要任何一個字串的編碼值大於128，整串64 bit 二進制得到的無號數字必定不等於0，因此回傳 `false` ，如下表格: | \迴圈數 |1| | | | | | | | | --- | --- | --- | --- | --- | --- | --- | --- | --- | |**比較值**|0x80|80|80|80|80|80|80|80| |**字串**|'c'|'o'|'m'|'p'|'l'|'e'|'t'|'e'| 因此我們要選擇的是 **0x8080808080808080** 題目 MMM = ? `(a)` 0x0080008000800080 `(b)` 0x8000800080008000 `(c)` 0x0808080808080808 `(d)` 0x8080808080808080 `(e)` 0x8888888888888888 `(f)` 0xFFFFFFFFFFFFFFFF **答案選擇**`(d)`**0x8080808080808080** ### 測驗二關於大小寫轉換的問題，我們實作一個不需要 branch 的案例，將大小寫都轉換為同一個數字，原本為數字的話維持不變 ```clike= uint8_t hexchar2val(uint8_t in) { const uint8_t letter = in & MASK; const uint8_t shift = (letter >> AAA) | (letter >> BBB); return (in + shift) & 0xf; } ``` 這題我覺得十分的巧妙，由於不能使用任何的 branch ，代表任何 if 、 while 、 for 都必須被禁用，這邊實作的原理是利用到 ASCII code 自己本身的特性，數字皆為`0x3..`作為開頭，小寫為`0x4..`作為開頭，大寫則是`0x6..`作為開頭，只看這樣可能不夠直覺，所以我們將他換成 bit 的方式表示: | 數字 | 大寫 | 小寫 | | --- | --- | --- | | ++0011++ ++(0000~1001)++|++0100++ ++(0000~0110)++|++0110++ ++(0000~0110)++| 我們再回來看程式碼: ```clike=3 const uint8_t letter = in & MASK; ``` 我們可以猜到這行的目的是要將數字以及字母分隔開來，所以我們需要做一個 `bit mask` 做出區別: MASK = ? `(a)` 0x10 `(b)` 0x20 `(c)` 0x40 `(d)` 0x60 `(e)` 0x80 透過觀察，我們發現數字與字母的最大差別便是第二個 bit 不一樣，因此選項我們必須選擇++0100++ ++0000++並且與我們原本的 `in` 做 AND 運算，這樣如果是數字輸出結果便會是++0000++ ++0000++，字母的話則是++0100++ ++0000++。 **答案選**`(c)` **0x40** 接著我們還需要將大小寫通通轉成同一個數字輸出，首先看到 ```clike=4 const uint8_t shift = (letter >> AAA) | (letter >> BBB); ``` `letter` 在這邊數字是0，因此經過 shift 之後仍然是0;字母的話是++0100++ ++0000++，其實很好的為我們只留了一個1，因此透過這個1我們就可以製作另一個遮罩，將高位元的四個 bit 變成是一樣的，參考範例，以 `f` 及 `F` 為例，回傳值皆為15，也就是`基準數9`加上原本 `f` 、 `F` 共同的末4個 bit ，也就是6 (`in` + `shift`)，再去除高位元的4個 bit ，輸出就會都是15了，解決完字母，我們再檢查數字，因為 `shift` 是0，其實就是單純的遮蔽掉最高四個位元而已。回到答案的部分，為了製作出9這個基準數，我們將原本得到的++0100++ ++0000++ `shift` 3 和 6 並 OR 運算成功獲得 ++0000++ ++1001++，對於數字基準數則是++0000++ ++0000++。 AAA = ? `(a)` 3 `(b)` 2 `(c)` 1 `(d)` 0 **答案選** `(a)` **3** BBB = ? `(a)` 7 `(b)` 6 `(c)` 5 `(d)` 4 **答案選** `(b)` **6** ### 測驗三 ```cpp= 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; } ``` 根據題目提示: >對 2 的 N 次方 (power of 2) 進行除法，在無號整數的操作就等同於右移 (shift) N 個位元，又當d (除數) 的數值是已知的狀況下，$\frac{2^N}{d}$可預先計算我們猜測這邊的 M 可能就是$\frac{2^N}{d}$，既然如此，後面的$n × \frac{\frac{2^N}{d}}{2^N}$便是由 ```cpp=7 uint64_t quotient = ((__uint128_t) M * n) >> 64; ``` 實現。因此，我們知道後面這 `shift` 64位元的動作就是相當於除於$2^N$，所以$N$就是64，即$2^{64}$ ，回推回去$M$就是$\frac{2^{64}}{d}$，但是因為能夠紀錄的位數不夠，所以必須先用**0xFFFFFFFFFFFFFFFF**暫時替代，並且在計算完後再把**1**加回來，同時也可以預先支付之後右移64位元的無條件捨去。 XXX = ? `(a)` 0x00F000F000F00080 `(b)` 0xF000F000F000F000 `(c)` 0x0F0F0F0F0F0F0F0F `(d)` 0xF0F0F0F0F0F0F0F0 `(e)` 0x8888888888888888 `(f)` 0xFFFFFFFFFFFFFFFF **答案選擇**`(f)`**0xFFFFFFFFFFFFFFFF** ### 測驗四 ```clike= bool divisible(uint32_t n) { return n * M <= YYY; } ``` 這題想了很久還是想不出來，後來是看了[fwfly](https://hackmd.io/@fwfly/quiz2)同學的共筆，才發現原來是使用 overflow 的方式判斷有沒有辦法整除。如果是整除，回傳值應該是1，代表整數時，` n * M <= YYY` 為真。 1. $M=\frac{0xFFFFFFFFFFFFFFFF}{3}+1=0x5555555555555556$ 2. $n$總共有三種可能性: $3K$ 、 $3K+1$ 和 $3K+2$ ， $K>=0$ `case1:`$3K$ >3KM = K(0xFFFFFFFFFFFFFFFF+3)，這個數字已經超過64 bit 能夠表示的最大上限，所以 overflow 之後的結果會是一個蠻小的數字。 `case2:`$3K+1$ >(3K+1)M = K(0xFFFFFFFFFFFFFFFF+3)+0x5555555555555556，前面我們已經知道K(0xFFFFFFFFFFFFFFFF+3)會是一個跟M比起來足夠小的數字，所以我們知道(3K+1)M會是比M大一些些的數字 `case3:`$3K+2$ >(3K+2)M = K(0xFFFFFFFFFFFFFFFF+3)+0xaaaaaaaaaaaaaac，必定也是比 M 大的一個數字直覺上來說，我們選擇 M 當作答案應該不會有錯，因為 overflow 的關係，被整除的數字 n * M 都會得到一個跟 M 比起來特別小的數字，但是當 $K=0$ 的時候有個例外，也就是得到 `(3K+1)M = K(0xFFFFFFFFFFFFFFFF+3)+0x5555555555555556 =0x5555555555555556`，而這個答案並不滿足 `n * M <= M`必須等於0，所以我們要選擇**YYY=M-1**這個答案來避免這個特殊情形。 YYY = ? `(a)` M + 1 `(b)` M `(c)` M - 1 `(d)` (M >> 1) `(e)` (M << 1) **答案選** `(c)` **M - 1** ### 測驗五考慮 `strlower` 函式的作用是將指定的字串 (或部分字串) 的英文字母全改為小寫 ```cpp= #include <ctype.h> #include <stddef.h> /* in-place implementation for converting all characters into lowercase. */ void strlower(char *s, size_t n) { for (size_t j = 0; j < n; j++) { if (s[j] >= 'A' && s[j] <= 'Z') s[j] ^= 1 << 5; else if ((unsigned) s[j] >= '\x7f') /* extended ASCII */ s[j] = tolower(s[j]); } } ``` 實作原理，首先我們根據第三題，知道大寫的最高4 bit 為++0100++ ，小寫是 ++0110++，所以大小寫轉換成小寫的方式就是把第3個 bit 設定成1，就可以讓大小寫的開頭皆為++0110++(小寫)，設定方式: ```cpp=7 if (s[j] >= 'A' && s[j] <= 'Z') ``` 先檢查是否是大寫 ```cpp=8 s[j] ^= 1 << 5; ``` 這邊的動作是 `XOR` 了 ++0010++ ++0000++，對於0來說，原本的 bit 會被留下來，如果是1的話，會將 bit 反向處理，將大小寫通通變成 ++0110++ 開頭。在 64 位元處理器架構 (以下針對 `x86_64`, little endian)，我們可引入向量化 (vectorized) 的手段，避免一次比對一個字元，而是直接操作一整個 word (對 `x86_64` 來說，就是 64 bits，或 8 個位元組)。沿用上述的 `strlower` 函式，我們用這樣的思路實作向量化的 `strlower`，程式碼列表如下: ```cpp= #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(VV1)) == 0) { /* is ASCII? */ uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2); uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3); uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2; *chunk ^= mask; } else strlower(s, 8); } k = n % 8; if (k) strlower(s, k); } ``` 首先，我們要先了解巨集 ```cpp= #define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u) ``` 的意思，這邊其實是先將傳進來64 bit 的無號整數作 `bit mask` ，留下最後需要"複製"的字元(8 bits )，最後透過乘上 `0x0101010101010101u`一次比較8個字元是否在範圍內，萬一任何一個字元編碼大於經過 `bit mask` 的 b ，得到最後的結果都會大於0。對於**VV1**，目的是想要一次比對8個字元，判別是不是全部都在 ASCII code 的範圍內，所以每個字元都應該不比128，也就是++1000++ ++0000++ (**0x80**)還要大，如果其中一個比128大，這個判斷式就會大於0 ```cpp=13 if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */ ``` VV1 = ? `(a)` 0x10 `(b)` 0x20 `(c)` 0x40 `(d)` 0x60 `(e)` 0x80 **因為遮罩條件是 ASCII 上限128，所以選擇遮罩為**`0x80`，`(e)` **0x80** ```cpp=14 uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2); ``` ```cpp=15 uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3); ``` 我們知道這兩行的目的是作一個遮罩的上限和下限， VV2 選擇0，因為讓大寫的字母相加後的最後一個位元一定是 1，VV3 選擇-1 是因為需要讓 A~Z 相減必須是 26 以容納 26 個英文字母。 VV2 = ? `(a)` (-1) `(b)` 0 `(c)` 1 **答案選擇**`(b)` **0** VV3 = ? `(a)` (-1) `(b)` 0 `(c)` 1 **答案選擇**`(a)` **(-1)** ```cpp=16 uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2; ``` 這邊考的觀念其實是我們想要設定的 bit 到底是在哪個位置而已，因為我們知道大寫跟小寫的差別是在第三個 bit ，所以由後面的 `shift` 2 bit 知道前面放的應該是++1000++ ++0000++，也就是0x80。 VV4 = ? `(a)` 0x10 `(b)` 0x20 `(c)` 0x40 `(d)` 0x60 `(e)` 0x80 **答案選擇**`(e)` **0x80** ### 測驗六 ```clike= 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; } ``` KKK = ? `(a)` higher `(b)` lower `(c)` ~higher `(d)` ~lower `(e)` 0xFFFFFFFF JJJ = ? `(a)` higher `(b)` lower `(c)` ~higher `(d)` ~lower `(e)` 0xFFFFFFFF :::success TODO:解釋程式碼 :::

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.