# 2020q3 Homework2 (quiz2) contributed by < `carlhutant` > [TOC] ## 測驗 1 ```c= 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 size 為 1 byte 若只使用 7 位元編碼 則須確保 MSB 為 0 因此跟 10000000(0x80) 做 and 即可 一次比對 64 位元時,將 8 個 char 合起來 因此將 8 個 0x80 合起來即可 `MMM = (d) 0x8080808080808080` ## 測驗 2 ```c= uint8_t hexchar2val(uint8_t in) { const uint8_t letter = in & MASK; const uint8_t shift = (letter >> AAA) | (letter >> BBB); return (in + shift) & 0xf; } ``` 第三行判斷 in 是否為字母 因為字母皆有 0x01X0 XXXX 的特徵 所以與 0x0100 0000 and 可得到 0x0100 0000 `MASK = (c) 0x40` 第五行的 & 將所有輸入高位的 byte 去除 從觀察可發現 0~1 剛好變成 0~1 a~f 與 A~F 都變成 1~6 全都加 9 就達到目標 因此 shift 為 0x0000 1001 可知第四行原本 letter 為 0x0100 0000 應該右移 3 與 6 `AAA = (a) 3` `BBB = (b) 6` ## 測驗 3 ```c= 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; } ``` 目標是要達到 $\dfrac{n}{D} = \dfrac{X}{D} \times \dfrac{n}{X}$ $\dfrac{X}{D}$ 可事先算好並重複使用, $\dfrac{n}{X}$ 可透過 shift 就達到 因此只須做乘法計算 從第六行可知 X 應該為 $2^{64}$ 但選項中沒有,而且第二行最後還做了加一的行為 那我們就先設 XXX 為 $2^{64}-x$ 第六行會變成 : ```c=6 uint64_t quotient = ((__uint128_t) ((uint64_t)(UINT64_C(XXX) / (D) + 1)) * n) >> 64; ``` (UINT64_C(XXX) / (D) + 1)) 先計算,結果為 $\left\lfloor{\dfrac{2^{64}-x}{D}} \right\rfloor+1$ ,為整數,因為是 int 運算,小數捨去 也可表示成 $\dfrac{2^{64}-x-r}{D}+1$ ,也為整數, 其中 $r$ 為 $2^{64}-x$ 除以 D 的餘數 接著乘 n ,結果為 $\dfrac{n\times2^{64}-nx-nr}{D}+n$ ,為整數 接著向右 shift 64 bits 可視為除以 $2^{64}$ 後捨去小數 結果為 $\left\lfloor\dfrac{n}{D}-\dfrac{nx}{D\times2^{64}}-\dfrac{nr}{D\times2^{64}}+\dfrac{n}{2^{64}}\right\rfloor=\left\lfloor\dfrac{n}{D}+\dfrac{\dfrac{-nx-nr+nD}{2^{64}}}{D}\right\rfloor$ 因為我們希望最終結果等於$\left\lfloor\dfrac{n}{D}\right\rfloor$ 所以必須確保 $-R<=\dfrac{n(-x-r+D)}{2^{64}}<D-R$ ,其中 $R$ 為 $n$ 除以 $D$ 的餘數 由題目可知 : 1. $n$ 為 32 bits uint 2. $x$ 由選項 A~F 決定,可為 0x0~0xFFFFFFFFFFFFFFFF 的 64 bits uint 3. $r$ 為 $2^{64}-x$ 除以 D 的餘數,範圍在 0~D-1 的 32 bits uint 4. $D$ 為 32 bits uint 發現可透過 $x$ 將 $(-x-r+D)$ 限制在 $2^{32}$ 以內的正數 兩個 32 bits uint 相乘不會超過 64bits 達到 $-R<=0<=\dfrac{n(-x-r+D)}{2^{64}}<1<=D-R$ $D-r$ 的範圍在 $2^{32}$~$1$ ( $2^{32}$ 不確定,但最小是 1 ),所以 $x$ 就只能是 0 或 1 了 `XXX = (f) 0xFFFFFFFFFFFFFFFF` 推測使用 0xFFFFFFFFFFFFFFFF 而非 0xFFFFFFFFFFFFFFFF + 1 是為了記憶體操作方便 ## 測驗 4 ```c= bool divisible(uint32_t n) { return n * M <= YYY; } ``` 此設計的核心建立在 uint64_t 乘法發生的 overflow 上 $D \times (\left\lfloor{\dfrac{2^{64}-1}{D}} \right\rfloor+1)$ 可能為 $2^{64}-1+D$ 或是 $2^{64}-1-r+D$ 其中 $r$ 為 $2^{64}-1$ 除以 D 的餘數 以上兩者皆大於 0xFFFFFFFFFFFFFFFF 因此會 overflow ,在 uint64_t 表示下會是 $D$ 或是 $D-r$ 接著 $n$ 可以拆解為 $t \times D + s$ ,其中 $t$ 與 $s$ 皆為非負整數, $s$ 小於 $D$ $t \times D \times M$ 會 overflow ,在 uint64_t 下是 $t \times D$ 或是 $t \times (D-r)$ $s$ 最大為 $D-1$ 乘上 $M$ 可能為以下兩者 : 1. $\dfrac{2^{64}-1}{D}$ 為整數 -> $2^{64}-1+D-(\dfrac{2^{64}-1}{D}+1)$ 2. $\dfrac{2^{64}-1}{D}$ 不為整數 -> $2^{64}-1-r+D-(\dfrac{2^{64}-1-r}{D}+1)$ 因為 $D$ 為 32 bits uint , 0xFFFFFFFFFFFFFFFF 除以任何 32 bits uint 的商皆會大於除數,也就是分數部分大於 $D$ ,第二種雖然有 $-r$ 但只會使其整除不會改變整數部分 因此兩者都必小於 $2^{64}$ 也就是不會 overflow ,所以只要 $s>0$ 結果必定大於 $M$ 此設計就是 $n$ 拆解為 $t \times D + s$ ,只要 $s>0$, $n \times M$ 就至少為 $M$ ,只要 $s=0$, $n \times M$ 就因為 overflow 小於 $M$ ( 或是 $t=0$ ) 但如何確保 $s>0$ 時,$s \times M$ 不會因為加上 $t \times D \times M$ 的結果而 overflow 變成小於 $M$ ? 首先 $t \times D \times M$ 在 uint64_t 下為 $t \times D$ 或是 $t \times (D-r)$ 皆小於 $2^{32}$ $$ \begin{align} s \times M &\leq (D-1)\times M\\ &=(D-1)(\dfrac{2^{64}-1-r}{D}+1)\\ &\leq\frac{(D-1)2^{64}}{D}\\ &=2^{64}(1-\dfrac{1}{D})\\ &<2^{64}(1-\dfrac{1}{2^{32}})\\ &=2^{64}-2^{32} \end{align} $$ 則 $(t \times D) + (s \times M) < (2^{32})+(2^{64}-2^{32})$ 不會 overflow ,也就是會大於等於 $M$ `YYY = (c) M - 1` ## 測驗 5 ```c= #include <ctype.h> #include <stddef.h> #include <stdint.h> #define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u) 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) { 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); } ``` 程式要做的就只有 1.找出 A~Z 的字元 2.將該字元第 6 個 bit 設為 1 但為了要加速,避免使用 if else 判斷式,並且一次處理 8 個 char 真正改變 bits 的位置在第 16 行,而且從使用 exclusive or 可知道 mask 一定會根據對應的 char 不同而變化,若對應 A~Z 為 0x20 否則為 0x00 在往上看到 `mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2` 可知 `(A ^ Z) & PACKED_BYTE(VV4)` 會是由 0x80 或 0x00 共八個組成 那`PACKED_BYTE(VV4)` 就可能是 0x8080808080808080 並且由 `(A ^ Z)` 對應的 bits 來決定要保留還是改成 0x00 `VV4 = (e) 0x80` 可知當 char 位於 A~Z 時,A 與 Z 該位置的 MSB 彼此會不同 看到 13 14 行, `128 - 'A'` 與 `128 - 'Z'` 為字元到 0x80 的差,此字元以上的 char 加此值 MSB 都會為 1 ,但我們要的是一個 1 一個 0 ,因為選項只有 1 0 -1 所以選擇 "大於等於 A 的 MSB 為 1" 與 "小於 Z+1 的 MSB 為 0" `VV2 = (b) 0` `VV3 = (a) (-1)` 但是要避免加上 A 與 Z 後超出 0xff 影響其他 char ,必須將每個 char 的值限制在 0x7f 以下,也就是 MSB 為 0 ,因此在第 12 行將有大於 0x7f 的資料 8 筆一起交由 strlower 處理 `VV1 = (e) 0x80` ## 測驗 6 ```c= 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; } ``` 當ㄧ個數與其他 xor 在一起後可再次 xor 相同的其他數還原出此數 可想成第一次 xor 會將數字的 information 加入,第二次則會移除 本設計為第一次出現的資訊會出現在 lower 第二次會從 lower 中移除但加入 higher 中 第三次會從 higher 中移除 `KKK = ~higher` `JJJ = ~lower`
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up