# 2020q3 Homework2 (quiz2) contributed by < `fwfly` > --- ### 測驗 3 原函式 $$ n*\dfrac{2^N}{d}*\dfrac{1}{2^N} $$ ```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) { // M*n / 2^N uint64_t quotient = ((__uint128_t) M * n) >> 64; return n - quotient * D; } ``` 從原函式知道 shift 64位元相當於除以 $2^N$ ``` ((__uint128_t) M * n) >> 64 ``` 所以 $$ M*n = n\dfrac{2^N}{d} $$ XXX 的部分就會是 2^N = 0xFFFFFFFFFFFFFFFF 但是這樣並不能解釋這句 :::info 其中一種策略是將除法改為乘法運算 ::: 原因是 `UINT64_C(XXX) / (D) + 1` 依然還是除法，既然是除法理論上應該不會變得比較快 :::danger 1. 避免武斷地說「理論上」，你的「理論」適用於現代電腦架構嗎？ 2. 避免說「透過網路上的文章」，你應該明確指出是哪一篇文章和時空背景，再來討論。不要跟記者^TM^一般說話。 :notes: jserv ::: 依據 [Faster remainders when the divisor is a constant](https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/) 可以得到這句話 :::info Thus if 2N/d has been precomputed, you can compute the division n/d as a multiplication and a shift ::: 也就是說 quickmod 的 quick 是來自於 precomputed．也可以理解 compiler 已經把除法的部份做完了( 因為兩個都是常數 ) #### assembly code 透過組合語言輸出可以看到其實程式還是有做除法 `divq` ```asm $ gcc -S W2Q3.c $ cat W2Q3.s quickmod: .LFB0: .cfi_startproc pushq %rbp .cfi_def_cfa_offset 16 ... ... movl $0, %edx divq %rdi ``` 但是如果做了最佳化，就可以看到整個函式是沒有`除法`的． ```asm $ gcc -S -O1 W2Q3.c $ cat W2Q3.s quickmod: .LFB23: .cfi_startproc movl %edi, %eax movabsq $6148914691236517206, %rdx mulq %rdx leal (%rdx,%rdx,2), %eax subl %eax, %edi movl %edi, %eax ret .cfi_endproc ``` 所以從這邊可以知道要達到 quickmode 的條件有兩個 1. 兩個數字都是常數 (const 跟 0xFFF...) 2. 最佳化需要打開 (-O1 option) --- ### 測驗 4 程式碼包含解答如下 ```c bool divisible(uint32_t n) { uint64_t nm = n * M; uint64_t YYY = M - 1; printf("n: %u\n",n); printf("nM: %lu\n",nm); return n * M <= YYY; } ``` 這裡主要是靠 overflow 去驗證是否能夠被整除 從簡單的 n*M 可以得到以下結果，明顯看得出來能被整除的會導致 overflow ``` n: 695 nM: 12297829382473034874 n: 555 nM: 370 ``` 但是 695 明明就比 555 大卻沒有產生 overflow ? #### 理解 n*M 原因可以這樣看會比較好理解． 在除法部分 2^N/3 可以看成把 2^N 分成 3 等分． 在乘法部分 3*M 可以理解成 : 把 ( 2^N/3 + 1 ) 加了 3 次 所以會變成 $$ (\dfrac{2^N}{3} + 1) + ( \dfrac{2^N}{3}+1) + (\dfrac{2^N}{3} + 1) = 2^N + 3 $$ 2^N = 0xFFF...FFFF = 64位元最大整數 所以再加 3 就會 overflow 那如果 n = 4 會怎麼樣 ? $$ (\dfrac{2^N}{3} + 1) + ( \dfrac{2^N}{3}+1) + (\dfrac{2^N}{3} + 1) + (\dfrac{2^N}{3} + 1) = 2^N + 3 + (\dfrac{2^N}{3} + 1) $$ 事實上也是 overflow , 但是因為多加了一個 M 就看起來會很像沒有 overflow. 有點像是時鐘跑了 12 之後回到 1 重新計算．所以如果實際執行就會產生以下結果 ``` n: 1 nM: 6148914691236517206 n: 2 nM: 12297829382473034412 n: 3 nM: 2 n: 4 nM: 6148914691236517208 n: 5 nM: 12297829382473034414 n: 6 nM: 4 ``` 可以看得出來隨著 n 的變化只是不斷的在 loop. #### YYY 是什麼？ 基本上 YYY 可以等於 M ，但是在當 n = 1 的時候會出現錯誤． 因為當 YYY = M 且 n = 1 的時候會出現 ```C return M <= M # 回傳 1 而不是 0 , 因為 n = 1 ``` 因此在這樣的情況下為了產生小於的結果 M 需要做減 1 所以 YYY = M - 1 ### 測驗 6 ```c 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 swap algorithm](https://en.wikipedia.org/wiki/XOR_swap_algorithm) 知道, XOR 有一個特性是自己 XOR 自己可以抵消 $$ A \oplus A = 0. $$ 所以如果有兩個數字相同 XOR 自己是會消失的. 比方說 [3,3,2,1,1] $$ 3 \oplus 3 \oplus 2 \oplus 1 \oplus 1 $$ :::danger 用字要精準，什麼「消失」？又什麼「自己」？你可以嘗試用英語將上述表達翻譯一次，看會得到什麼。 :notes: jserv ::: 3 跟 1 會因為自己跟自己 XOR 而為 0, 而 0 跟任何一個數字 XOR 都是原本的數字，所以透過 XOR 可以知道 2 唯一只有存在一個的數字． 但是這樣子不足以解決當重複數字為 3 或奇數的時候 #### & [Bitwise operation AND ](https://en.wikipedia.org/wiki/Bitwise_operation#AND) reference: * https://stackoverflow.com/questions/21297067/single-number-ii-from-leetcode * [leetcode 之 Single Number II](https://blog.csdn.net/yutianzuijin/article/details/50597413) * [leetcode-137-Single Number II-第二种解法](https://cloud.tencent.com/developer/article/1131945) * [[LeetCode] 137. Single Number II 深入浅出算法讲解和代码示例](https://blog.csdn.net/karen0310/article/details/78226261)