# 2020 sysprog Homework2 (quiz2) ###### tags: `sysprog` contributed by < `sciyen` > [TOC] ## Q1 is_ascii() 題目： ```cpp= #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 & 0x8080808080808080) return false; i += 8; } while (i < size) { if (str[i] & 0x80) return false; i++; } return true; } ``` 已知 extended ASCII 的第8個 bit 為1，若以單一個 byte 來看，用以下方式可以判斷第8個 bit 是否為1 ```cpp= int b = byte & 0x80; ``` :::info For example: 0b11000111 0b10000000 -> 0xf0 0b10000000 ::: 利用相同方式，若有 8 byte，則 Mask 以一個 byte 為單位，用 8組。 ```cpp= 0x8080808080808080 ``` :::warning **Memory alignment problem** 由於傳入的參數 `str` 可能是記憶體中的任意位置(不一定會 alignment )，因此若直接對該記憶體操作有可能因為 unalignment 必須讀兩個記憶體區段再合併導致效能變差，因此利用 `memcpy()` 強制將記憶體 alignment 後再進行後續操作。 ::: #### 延伸問題 - 給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母 ## Q2 hexchar2val() 題目：將十六進位表示的字串 (hexadecimal string) 轉為數值 ```cpp= uint8_t hexchar2val(uint8_t in) { const uint8_t letter = in & 0x40; const uint8_t shift = (letter >> 3) | (letter >> 6); return (in + shift) & 0xf; } ``` :::info 注意 ASCII 中數字與英文字的表示方式 - 數字 0x30~0x39, 前4個 byte 皆為 0b0011 - 小寫英文 0x61~0x66, 前4個 byte 為0b0110 - 大寫英文 0x41~0x46, 前4個 byte 為0b0100 ::: 1. 為了判斷是否為英文，利用第一個 MASK 判斷前 4 byte 中的 4 位置是否為1， 因此 MASK 為0x40。因此 `letter` 的意義為 `in` 是 `>=10` 的值。 2. 接下來，若 `in` 是 `>=10` 的值，則必須要創造出一個 `10` 加進去答案裡面，又若 `in>=10` ， `letter` = `0b01000000`，因此將 `letter` 右移3格得到 `0b00001000`，右移6格得到 `0b00000010`，做 or 運算後得到 `0b00001001` 也就是9。 :::warning | |`0b01000000`| |-|------------| |3|`0b00001000`| |6|`0b00000001`| |OR|`0b00001001`| ::: 4. 最後將 `in` 與 `shift` 相加，若 `in` 為數字，則 `shift` 為0；若 `in` 為 A~Z 或 a~z ，則 `shift` 為9，由於 A~Z 及 a~z 的後4個 byte 皆對應到 A=1, B=2,...，因此 A 為9+1=10，以此類推... 5. 最後，與0x0f做 `AND 運算`將剩餘的前 4 byte 濾掉。 ## Q3 quickmod(uint32_t n) 題目：該算法將除法變形為 乘法 與 shift 的組合。 ```cpp= const uint32_t D = 3; #define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (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; } ``` #### 問題解析 由原式中 \begin{equation} \frac{n}{d}=n \times \frac{\frac{2^N}{d}}{2^N} \end{equation} 可以發現 `M` 應為式中 $\frac{2^N}{d}$ 的部分，而 `N` 為64，但由於 $2^{64}$ 恰好進一位，導致記憶體位置不夠，因此用 `0xFFFFFFFFFFFFFFFF` 代替，最後再加1。 #### 程式碼說明 1. 對於 `#define` 代表利用預處理器先行計算 `((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (D) + 1))` 並視為 constant 處理，因此可以大幅減少執行時期的計算。 2. 對於式中的 $\frac{1}{2^{64}}$ ，由於其為2的倍數，可以用 shift 快速處理。 :::info **Proof** $\frac{2^N}{d}$ 於程式中寫為 $\frac{2^N-1}{d}+1$ 假設：商數為 `q` ，餘數為 `r` 且 $q, r \in \mathbb{N}$ 依據情況可以分為下列兩種： - $2^N$ 整除 `d`： \begin{equation} \left\{ \begin{array}{lr} 2^N=q\times d \\ 2^N-1=(q-1)d+(d-1), \ if \ d>1 \ then \ d-1>0 \end{array} \right. \end{equation} 因此 `q` 必定比原式少1 - $2^N$ 不整除 `d`： \begin{equation} \left\{ \begin{array}{lr} 2^N=q\times d +r, \ where \ 1<r<d \\ 2^N-1=(q-1)d+(r-1) \end{array} \right. \\ \because 1<r<d \\ \therefore 0<r-1<d-1 \end{equation} `d-1`必定無法進位，因此 `q` 必定比原式少1 **結論：** 不管$\frac{2^N-1}{d}$中的 `N` 及 `d` 為多少，所得的 `q` 必定較 $\frac{2^N}{d}$ 少1，因此$\frac{2^N}{d}$ 於程式中寫為 $\frac{2^N-1}{d}+1$。 ::: #### 延伸問題 ## Q4 divisible(uint32_t n) ## Q5 strlower ### 解析 `void strlower(char *s, size_t n)` 程式碼原理 ```c= #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]); } } ``` 觀察 ASCII code 可以發現，其大寫字母與小寫字母差在第 5 個 bit ，例如： A: 0x41 0100 0001 B: 0x61 0110 0001 因此若要將大小寫互換，只要將第 5 個 bit 作 not 運算即可。 ### 利用 64 bit 架構做運算 一次對 8 個 byte 做處理以加速計算： ```c= #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); } ``` - 12行：由於 char array 為連續的記憶體，透過 uint64_t 指標的方式取值可以獲得連續 8 byte 的記憶體。 - 5行：由於要做 64 bit 乘法運算，因此將 `b` 強制轉為 uint64_t ，同時，為確保只有第一個 byte ## Q6 LeetCode [137. Single Number II](https://leetcode.com/problems/single-number-ii/): ```cpp= int singleNumber(int *nums, int numsSize){ int lower = 0, higher = 0; for (int i = 0; i < numsSize; i++) { lower ^= nums[i]; lower &= ~higher; higher ^= nums[i]; higher &= ~lower; } return lower; } ``` ### 首先看 `XOR` 的特性： XOR 重複做兩次後會變回原本的數字 ``` 5: 00000101 5: 00000101 ------------ A: 11111111 5: 00000101 ------------ A: 00000101 ``` 如果從 0 開始，對 0 做 2 次一樣的 `XOR` 後會變回 0 。 **Note**：可以觀察到，對任意數做兩次一樣的 `XOR` 後都會變回原本的數，其原因也很明確，因為相同的數做 `XOR` 後必定全為 1 ，然後任意數對 1 做 `XOR` 後，其值不變。 ``` 0: 00000000 5: 00000101 ------------ A: 11111010 5: 00000101 ------------ A: 00000000 ``` ``` 5: 00000101 3: 00000011 ------------ A: 11111001 5: 00000101 ------------ A: 00000011 5: 00000101 ------------ A: 11111001 5: 00000101 ------------ A: 00000001 ```