# 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:解釋程式碼
:::
Sign in with Wallet
Connect another wallet