# 2020q3 Homework2 (quiz2) ## 測驗一 考慮到下列程式碼,必須要一次判斷 64 位元的資料 ```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; } ``` 所以要判斷每個 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 來判斷 接著看到下方的程式碼 ```clike= 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 並且回傳。 ## 測驗三 考慮以下程式碼: ```clike= 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. 解釋上述程式的原理 ## 測驗四 考慮以下程式碼: ```clike= 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 同一個數字兩次,會變成原本的數字
×
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