2020q3 Homework2 (quiz2)

contributed by < fwfly >

---

測驗 3

原函式

$$n\ast {\displaystyle \frac{2^N}{d}}\ast {\displaystyle \frac{1}{2^N}}$$

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\ast n=n{\displaystyle \frac{2^N}{d}}$$
XXX 的部分就會是 2^N = 0xFFFFFFFFFFFFFFFF

但是這樣並不能解釋這句

其中一種策略是將除法改為乘法運算

原因是 UINT64_C(XXX) / (D) + 1 依然還是除法，既然是除法理論上應該不會變得比較快

1. 避免武斷地說「理論上」，你的「理論」適用於現代電腦架構嗎？
2. 避免說「透過網路上的文章」，你應該明確指出是哪一篇文章和時空背景，再來討論。不要跟記者^TM一般說話。

jserv

依據 Faster remainders when the divisor is a constant 可以得到這句話

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

$ gcc -S W2Q3.c
$ cat W2Q3.s

quickmod:
.LFB0:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        ...
        ...
        movl    $0, %edx
        divq    %rdi

但是如果做了最佳化，就可以看到整個函式是沒有除法的．

$ 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

程式碼包含解答如下

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 次
所以會變成

$$({\displaystyle \frac{2^N}{3}}+1)+({\displaystyle \frac{2^N}{3}}+1)+({\displaystyle \frac{2^N}{3}}+1)=2^N+3$$
2^N = 0xFFF…FFFF = 64位元最大整數
所以再加 3 就會 overflow

那如果 n = 4 會怎麼樣 ?

$$({\displaystyle \frac{2^N}{3}}+1)+({\displaystyle \frac{2^N}{3}}+1)+({\displaystyle \frac{2^N}{3}}+1)+({\displaystyle \frac{2^N}{3}}+1)=2^N+3+({\displaystyle \frac{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 的時候會出現

    return M <= M # 回傳 1 而不是 0 , 因為 n  = 1

因此在這樣的情況下為了產生小於的結果 M 需要做減 1
所以 YYY = M - 1

測驗 6

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 知道, XOR 有一個特性是自己 XOR 自己可以抵消

$$A\oplus A=0.$$

所以如果有兩個數字相同 XOR 自己是會消失的. 比方說 [3,3,2,1,1]

$$3\oplus 3\oplus 2\oplus 1\oplus 1$$

用字要精準，什麼「消失」？又什麼「自己」？你可以嘗試用英語將上述表達翻譯一次，看會得到什麼。

jserv

3 跟 1 會因為自己跟自己 XOR 而為 0, 而 0 跟任何一個數字 XOR 都是原本的數字，所以透過 XOR 可以知道 2 唯一只有存在一個的數字．

但是這樣子不足以解決當重複數字為 3 或奇數的時候

&

Bitwise operation AND

reference:

• https://stackoverflow.com/questions/21297067/single-number-ii-from-leetcode
• leetcode 之 Single Number II
• leetcode-137-Single Number II-第二种解法
• [LeetCode] 137. Single Number II 深入浅出算法讲解和代码示例