# 2020q3 Homework2 (quiz2) contributed by < `ignite1771` > ## 1 因為一次要檢查 64-bits, 所以就去 `&` 0x0080 四組 :::danger 錯了，正確答案是 `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; } ``` ### 推論過程 1. 對於大小寫字母而言： 因為 `'A'` 和 `'a'` 其 ASCII 值對應為 `0x61`, `0x41`, 而 `hexchar2val('A')` 和 `hexchar2val('a')` 皆為 10, 觀察程式返回值 `return (in + shift) & 0xf;` 可得到： - shift = 9, 25 (9 + 16), 41 (9 + 16 + 16)... 即 9 + 16k, where k 是 >= 0 之整數 - 以 0x09 為例子，即 `00001001`，又觀察 `const uint8_t shift = (letter >> AAA) | (letter >> BBB);` ，得知需要得到 2 個數值 `00001000` 和 `00000001` 來去做 OR 運算： - 假設 Mask 是 `0x10`, 則大小寫英文字母做完 AND 運算後皆為 0, 故不可能 - 假設 Mask 是 `0x20`, 則大小寫英文字母做完 AND 運算後皆為 `0x20` - 對應的 AAA = 2, BBB = 5 - 假設 Mask 是 `0x40`, 則大小寫英文字母做完 AND 運算後皆為 `0x40` - 對應的 AAA = 3, BBB = 6 - 假設 Mask 是 `0x60`, 則大寫字母做完 AND 運算後為 `0x60`, 小寫字母則為 `0x40` - 大寫不可能產生上述 2 個數值，所以不對 - 假設 Mask 是 `0x80`, 則大小寫英文字母做完 AND 運算後皆為 0, 故不可能 2. 因此，我們推斷 Mask 有兩種可能，接下來分別將其判斷數字 `'0'` ~ `'9'` 的部分： - 假設 Mask 是 `0x20`, 則數字做完 AND 運算後皆為 `0x20` - 與大小寫字母結果相同，所以不對 - 假設 Mask 是 `0x40`, 則數字做完 AND 運算後皆為 `0x00` - 因此就是看其輸入 `in` 本身的 LSB, 對了！ :white_check_mark: 答案: Mask = `0x40`, AAA = `3`, BBB = `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; } ``` 首先觀察 macro `M` 裡面有個 `UINT64_C()`，一開始原本以為是 primitive type，後來看他是大寫命名並有括號才猜測是一個 macro, 查閱 C99 規格書 7.18.4.1 > **7.18.4.1 Macros for minimum-width integer constants** The macro INT**N**_C(value) shall expand to an integer constant expression corresponding to the type int_least**N**_t. The macro UINT**N**_C(value) shall expand to an integer constant expression corresponding to the type uint_least**N**_t. For example, if uint_least**64**_t is a name for the type unsigned long long int, then UINT**64**_C(0x123) might expand to the integer constant 0x123ULL. 在 [stackoverflow: What does the following C macro do?](https://stackoverflow.com/questions/16782442/what-does-the-following-c-macro-do) 即可更加確認： ```c #ifndef INT64_C #define INT64_C(c) (c ## LL) #define UINT64_C(c) (c ## ULL) #endif ``` `##` 為串接起來 token pasting operator, 且可以在 Preprocess 階段來做，而 `strcat` 函式則是只能在 Run-time 階段 - 此 macro 為讓其整數 LL, ULL 更 readable 的一種表示法。 :::warning 經由 try-and-error 知道 XXX = `0xFFFFFFFFFFFFFFFF` (如果是 uint64_t, 則 = $2^{64} - 1$), 但為什麼呢？ ::: 觀察題目，當我們把 $\dfrac{n}{d}$ 分子分母同乘以 $2^N$ 時會變成 $n \times \dfrac{\dfrac{2^N}{d}}{2^N}$ , 看似我們可以令 $M = \dfrac{2^N}{d}$, 而程式的 macro 定義的算式為 $M = \lfloor{\dfrac{2^N - 1}{d}\rfloor + 1}$, 為什麼呢？ 從程式碼第 6, 7 行得知 M 最終應該得到 $\lfloor\dfrac{2^N}{d}\rfloor$, 以致可以 return 餘數 `n - quotient * D` - 那麼 $\lfloor{\dfrac{2^N - 1}{d}\rfloor + 1}$ 會等於 $\lfloor\dfrac{2^N}{d}\rfloor$ ？ 參考 [維基百科 Divison by a constant](https://en.wikipedia.org/wiki/Division_algorithm) 的敘述，得知上方 + 1 的部分應是做 round up, 所以結果會相等。 ## 4 查閱 [C Operator Precedence](https://en.cppreference.com/w/c/language/operator_precedence), 知道優先順序 `* / %` > `+ -` > `>> <<` > `>= <=` (relational) > ... > ... > `<<= >>= =` n * M = $n \times \lfloor\dfrac{2^N}{d}\rfloor$ 因為上一題餘數 = `n - quotient * D`, $D = 3$, 又 quotient = (n * M) >> 64, 即 n * m = quotient << 64 = $quotient \times 2^{64}$, 而要整除的條件是 $n = quotient \times 3$, `n * M <= YYY` 做移項得到 `n * M - YYY <= 0` :::warning 經由 try-and-error 知道 YYY = `M`, 但為什麼呢？ ::: :::danger 錯了，正確答案是 `M - 1` ::: ## 5 - VV1: 首先 `* 0x0101010101010101u` 會讓 `((uint64_t)(b) & (0xff))` 之值複製成為 64 bits, 又 `uint64_t *chunk = (uint64_t *) s;` 讓 `*chunk` 一次指到 64 bits char, 要判斷是不是 ASCII 字元，即判斷一個 byte 是否 <= `0x7f`, 所以 VV1 = `0x80` 如果 AND 運算後不是 0, 那就不是 ASCII 字元 :::warning 以下根據猜測來進行 try-and-error ::: - VV2, VV3: 因為 `'A'`, `'Z'` 是大寫字母的頭跟尾，而 128 是 0x80 > 0x7f, 推測應該是與超過 ASCII 字元能表示範圍有關係，所以跟距離有關係，憑經驗猜測 VV2, VV3 應該是要加回 `1` :::warning 錯了，正確答案是 VV2 = `0`, VV3 = `-1` ::: - VV4: 因為 VV1 = `0x80`, 所以猜測 VV4 也跟 ASCII 表示範圍之類的相關，所以猜測應該也是 `0x80` ## 6 首先，對於 KKK 選項 (`lower &= KKK`) 推測有一些不可能: - (a) higher - (b) ~~lower~~ (lower 值不變，冗) - \(c\) ~higher - (d) ~~~lower~~ (AND 自己的反位元就變 0 了，要幹嘛？) - (e) ~~0xFFFFFFFF~~ (lower 值不變，冗) 因為直接 XOR 對方似乎還缺點什麼，那我們就猜測是 XOR 對方的反位元，即 \(c\) ~higher 我們可以印出每一回合內 lower, higher 經 bit-wise 運算之改變： ```c int singleNumber(int *nums, int numsSize) { int lower = 0, higher = 0; for (int i = 0; i < numsSize; i++) { printf("i = %d\n", i); lower ^= nums[i]; printf("lower = %#.8x\n", lower); lower &= ~higher; // KKK printf("lower = %#.8x\n", lower); higher ^= nums[i]; printf("higher = %#.8x\n", higher); higher &= ~lower; // JJJ printf("higher = %#.8x\n", higher); printf("Round i = 0: lower = %d, higher = %d\n", lower, higher); printf("=================\n"); } return lower; } ``` ``` /* Sample input */ [2, 2, 3, 2] /* Sample output */ i = 0 lower = 0x00000002 lower = 0x00000002 higher = 0x00000002 higher = 00000000 Round i = 0: lower = 2, higher = 0 ================= i = 1 lower = 00000000 lower = 00000000 higher = 0x00000002 higher = 0x00000002 Round i = 0: lower = 0, higher = 2 ================= i = 2 lower = 0x00000003 lower = 0x00000001 higher = 0x00000001 higher = 00000000 Round i = 0: lower = 1, higher = 0 ================= i = 3 lower = 0x00000003 lower = 0x00000003 higher = 0x00000002 higher = 00000000 Round i = 0: lower = 3, higher = 0 ================= ``` 雖然得到了答案，但對於其中運算原理還是不理解，故去看了 [Leetcode 討論區此篇留言](https://leetcode.com/problems/single-number-ii/discuss/43294/Challenge-me-thx/176039) ，得知 `lower ^= num[i]` 和 `higher ^= num[i]` 之 XOR 運算若把其看成是 num[i] 有沒有在該 Set 的話, 那麼會 `(lower ^ num[i]) & ~higher` 有以下的邏輯： ```python IF the set "lower" does not have A[i] Add A[i] to the set "lower" iff it is not in set "higher" ELSE Remove it from the set "lower" ``` 出現第一次的會被放入 lower 此 set, 然後出現第二次會從 lower 此 set 被移出。 同理，`(higher ^ num[i]) & ~lower` 運算代表，出現第二次的會被放入 higher 此 set, 然後出現第三次會從 higher 此 set 被移出，如此可知道最後出現在 lower 此 set 的一定是只出現 1 次的 num. 答案: KKK = `~higher`, JJJ = `~lower`