2020q3 Homework3 (quiz3)

--- tags: 進階電腦系統理論與實作 --- # 2020q3 Homework3 (quiz3) contributed by < `RinHizakura` > >[2020q3 第 3 週測驗題](https://hackmd.io/@sysprog/2020-quiz3?fbclid=IwAR2VKM07QHTneLdK1VBa9XgZ9ca10sZsEKUgVXTXumv0PBhKUGibXLKxEe0) > [GitHub](https://github.com/RinHizakura/NCKU-System-Software-Quiz/tree/master/quiz3) ## 測驗 `1` 根據 C 語言規格書，對**有號型別的負數**算術右移(Arithmetic right shift) 在 C 語言中是 [unspecified behavior](https://en.wikipedia.org/wiki/Unspecified_behavior)。 > The result of E1 >> E2 is E1 right-shifted E2 bit positions. > ... > If E1 has a signed type and a negative value, the resulting value is implementation-defined. 意即其行為結果雖在語言規範中並無規定，但可以根據平台或者編譯器的參考文件得知。而算術右移無非就是 2 進位的最左位元補 0 或者補 1 兩種。由題意描述可知，期待的結果是如果原本數字為負數的情形下，右移後最左邊補 1。因此，如果 `(m >> n)` 的結果已經如同預期(左邊補 1)，則 `(fix ^ (fix >> n));` 可以為 0，也就是 `fix` 可以為 0。由此可以反推 `logical` 是在判斷右移的結果為何，因此 `OP1` = `(b) >>1` : * 如果 -1 算術右移最左邊補 0，(-1) >> 1 是正數，> 0 為 true，則 logical = 1 * 如果 -1 算術右移最左邊補 1，(-1) >> 1 是負數，> 0 為 false，則 logical = 0。此情況下 `fix` 必為 0，符合我們預想的 `m >> n` 的結果就如預期，不需額外更動為求圖解精簡，圖例以 8 bits 為例，推廣到 32 bits 則同理。即使負數右移後左邊是補 0，但在 `m` 為正數的情況下，規格書明確的說 `m >> n` 的結果會等同是最左位元補 0。 > The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / $2^{E2}$. 所以 `fix` 仍可為 0，由此可以反推 `OP2` = `(c) m < 0`。只有在滿足 1. 負數的右移結果為最左位元補 0 2. m 為負數的情況下，`fixu` 會有真正的內容，且此時 `fixu` 會是 0x11111111，轉到 int 表示的 `fix` 就是 -1，則 `| (fix ^ (fix >> n))` 就會把右移的位元都補成 1，讓結果符合期待。 :::warning 問題： ```cpp unsigned int fixu = -(logical & (m < 0)); int fix = *(int *) &fixu; ``` 和 ```cpp int fix = -(logical & (m < 0)); ``` 兩個寫法的差異性？ > 前者可避免編譯器進行過度 (aggressive) 最佳化 > :notes: jserv ::: ### 驗證正確性因為在我的電腦上對負數算術右移是左邊補 1，為了確認程式在左邊補 0 的狀況下同樣正確，所以我就先實作了一個很在我的電腦中可以保證左邊補 0 的 right shift，再透過 `asr_i` 去比較和左邊補 1 的 right shift 結果是否有差異，檢驗 `asr_i` 是否是可以適用於跨平台的實作。 :::warning :warning: 顯然這個方法很暴力，而且也欠缺對 data model 的考量，不過因為重點只是確保 `asr_i` 的正確性所以就無傷大雅。 ::: ```c= int zero_rs(int a, int n) { for (int i = 0; i < n; i++) { a = (a >> 1) & 0x7FFFFFFF; } return a; } int asr_i(signed int m, unsigned int n) { const int logical = zero_rs(((int) -1), 1) > 0; unsigned int fixu = -(logical & (m < 0)); int fix = *(int *) &fixu; return zero_rs(m, n) | (fix ^ zero_rs(fix, n)); } ``` ### 通用的 ASR 實作可以針對不同資料寬度的 ASR。 ```c= #define asr_i(m, n) \ _Generic((m), \ int8_t: asr_i8, \ int16_t: asr_i16, \ int32_t: asr_i32, \ int64_t: asr_i64 \ )(m,n) #define asr(type) \ const type logical = (((type) -1) >> 1) > 0; \ u##type fixu = -(logical & (m < 0)); \ type fix = *(type *) &fixu; \ return (m >> n) | (fix ^ (fix >> n)) int8_t asr_i8(int8_t m, unsigned int n) { asr(int8_t); } int16_t asr_i16(int16_t m, unsigned int n) { asr(int16_t); } int32_t asr_i32(int32_t m, unsigned int n) { asr(int32_t); } int64_t asr_i64(int64_t m, unsigned int n) { asr(int64_t); } ``` 根據幾點考量而如此實作: * 根據 [data model](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models) 的不同，`int`、`long` 等等型別的長度可能有所差異，我認為根據 bits 實際的長度選擇正確寬度的 ASR 是比較好的作法 * 透過 `u##type`([Concatenation](https://gcc.gnu.org/onlinedocs/cpp/Concatenation.html)) 技巧連接字串 * 透過 [_Generic](https://hackmd.io/@sysprog/c-preprocessor#_Generic-C11) 達到類似 C++ template 的效果 :::warning 延伸問題：乍想之下，無論型別都直接轉型成 64 bits 的版本處理，計算出結果後再轉回原本的型別，似乎正確性上是沒有問題的？這樣想是否完全正確呢？排除正確性的話，這樣方式的實作可能有甚麼缺點？ > 不是每款 C 語言編譯器都能正確處理 64 位元，且 data model 會涉及 ABI 議題 > :notes: jserv ::: ## 測驗 `2` * `num > 0`: 因為 $4^n$ 必定 >= 1 * `(num & (num - 1))`: 可以判斷非負數的 `num` 是否為 $2^n$(n 為整數)，因為如果 `num` 不是 $2^n$ 就必不為 $4^n$ * 在[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics#%E9%81%8B%E7%94%A8-bit-wise-operator)有提及相關內容，或者可以參考[這個筆記](https://hackmd.io/9tGfpJtLTwyyOzDvlyJS2w?view#x-amp-x---1--0) * 如果是 $4^n$: | Column 1 | Column 2 | | -------- |:--------- | | $4^0$ | 0b1 | | 4 | 0b100 | | $4^2$ | 0b10000 | | $4^3$ | 0b1000000 | 在滿足前兩個條件的前提下，從右往左數到第 1 個 1 之前的 0 總數(也就是`ctz`)為偶數個，因此 `OPQ` = `(f) & 0x1` ### 不同的實作要判斷是否是 4 的倍數，可以有許多不同的實作方式。 ```c= bool isPowerOfFour_new(int num) { return !(__builtin_popcount(num) ^ 1) && __builtin_ffs(num) & 1; } ``` 一種思路是可以擅用 popcount 和 find first set，因為要判斷是否是 $4^n$ 只要滿足: 1. 2 進位表示中僅有一個 1 2. 且此 1 的位置為奇數(注意是從 1 開始數，所以 `__builtin_ffs(1) == 1`。事實上，`ctz` 計算後其實就可以達到同等 `ffs` 的效果) 或者也可以改寫成: (注意 `&&` 左右的 statement 是不能交換的，因為這裡的小技巧是通過 `&&` 左邊如果為 0 的狀況就不會去執行右邊的特性，避免 num >> 32 這樣的非法操作。) ```c= bool isPowerOfFour_new(int num) { int ffs = __builtin_ffs(num); return (ffs & 1) && !(num >> ffs); } ``` ### [1009. Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/) 題解為： ```c= int bitwiseComplement(int N){ if(N == 0) return 1; int mask = (1 << (31-__builtin_clz(N)))- 1; return ~N & mask; } ``` 根據題意，目標是將足以表示該數字的 2 進位表示做 complement(例如 5 可以表示成 0b101，所以有效部份為 3 個 bit)。因此，我們只需找到這個位元數 `n`，取直接對數字做 complement 的後 `n`，其他則維持為 0，就可以得到正確答案。我們可以透過 `clz` 來計算，透過 `(1 << (31-__builtin_clz(N)))- 1` 可以得到需要的位元位置為 1，其他為 0 的 mask(舉例來說，5 = 0b000...00101，則 mask 就會是 0b000...00111)，對 5 取補數後再和 `mask` 做 and 運算，就可以得到正確的結果。附上在 leetcode 中執行正確且通過的證明： ![](https://i.imgur.com/9ijqTI8.png) ### [41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/) 題解為： ```c= #define XORSWAP_UNSAFE(a, b) \ ((a) ^= (b), (b) ^= (a), \ (a) ^= (b)) int firstMissingPositive(int* nums, int numsSize){ for(int i=0;i<numsSize;i++){ if(nums[i] > 0 && nums[i] < numsSize){ int pos = nums[i] - 1; if(pos != i && nums[i] != nums[pos]){ XORSWAP_UNSAFE(nums[i],nums[pos]); i--; } } } for(int i = 0;i < numsSize;i++){ if(nums[i] != i + 1) return i + 1; } return numsSize + 1; } ``` 此題的解題思路是：因為目標是找到最小不在陣列中的正整數解，因此我們可以經歷整個陣列，如果找到 `1` 就放在陣列的 `0` 、找到 `2`，就放在陣列的 `1`，依照此規則擺放。則再從頭檢查陣列時，如果陣列 `0` 位置不是 `1`，就表示原始的陣列中沒有 `1`，為正確答案，依照同樣的規則，就知道原始的陣列是不是有 `2`、`3`...，依此類推。如果陣列中的內容都照規則擺放，則最小的正整數解就是 `numSize + 1`。附上在 leetcode 中執行正確且通過的證明： ![](https://i.imgur.com/ngJIqr6.png) :::warning 想不到這題用甚麼解法會需要 `clz` > 最後一個迴圈內的結束條件，可用到 `clz` > :notes: jserv ::: ## Golomb coding [Golomb coding](https://en.wikipedia.org/wiki/Golomb_coding) 是一種無損的資料壓縮方法，屬於 [Prefix code](https://en.wikipedia.org/wiki/Prefix_code) 的分組編碼系統，可以對非負整數進行編碼。其演算法流程為: 1. 根據一個定義的參數 M，對於編碼目標 N，計算出 N / M 的商 q 以及餘數 r 2. 最終的編碼會是 `<對 q 的編碼><對 r 的編碼>` 。對於 q 的編碼，使用 [unary coding](https://en.wikipedia.org/wiki/Unary_coding)，對於 r 則使用 [Truncated binary encoding](https://en.wikipedia.org/wiki/Truncated_binary_encoding) 3. 因此對 q 的編碼為: q 個 1 加上 1 個 0(或者 q 個 0 加上 1 個 1) 4. 對 r 的編碼，根據情形會有不同的截斷量，令 b = $\lfloor log_{2}M \rfloor$，則: * 如果 r < $2^{b+1}$ - M，則用 b 個 bits 表示 r 作為編碼 * 否則，用 b + 1 個 bits 表示 r + $2^{b+1}$ - M 作為編碼因此，每一個商 q 最多可以對應 M 種結果。詳情參照 [Wikipedia 範例](https://en.wikipedia.org/wiki/Golomb_coding#Example)可以更容易理解。 ### Golomb-Rice coding Golomb-Rice coding 是 Golomb coding 的特例，規定前面提到的參數 M 必須是 $2^N$ (N 為整數)，這可以帶來幾個好處: * 可以透過 bitwise operation 計算餘數(`r = N & (M - 1)`) * 對於 r 的編碼，一致取 r 二進位表示的低 $log_{2}m$ 位元來表示 ### Exponential-Golomb coding [Exponential-Golomb coding](https://en.wikipedia.org/wiki/Exponential-Golomb_coding)(order-k exp-Golomb code) 是另一種對 Golomb coding 的延伸。其演算法流程為: 1. 對於一個數字 A，去掉最低的 k 個位元後加一，得到數字 B 2. 在數字 B 的前面，加上等同 B 的位元數量減 1 個零 3. 將前面去掉的 k 個位元補回尾端與前面的方法最大的不同點是，Exponential-Golomb coding 的每一個 group 成員數量不同，會成指數型的成長。 Reference: [Golomb 及指数哥伦布编码原理介绍及实现 ](https://www.cnblogs.com/wangguchangqing/p/6297792.html) ### x-compressor [x-compressor](https://github.com/jserv/x-compressor) 是以 Golomb-Rice coding 為基礎的資料壓縮器。這裡我們先特別關注其中 Golomb coding 相關的實作。 #### `generic_io_t` ```cpp typedef struct { uint32_t *ptr; /* pointer to memory */ void *end; uint32_t b; /* bit buffer */ size_t c; /* bit counter */ } generic_io_t; ``` 為了可以更好的理解程式碼，大致敘述 `generic_io_t` 的用途： * 編碼使用的位元數目不固定，但整數型別有固定的長寬 * 因此解法為：每次 append 新的 bit 時，對於那些不足以一個 32 位元的表示的 bit 就放在 `b` 中，並用 `c` 紀錄多少部份是那些 append 的 bit * 每當 append 滿 32 bits，就把 `b` 轉過去 `ptr` 中，並清空 b 和 c，以供新的 bit 置放(透過 `flush_buffer` 函式來完成，因為非此章重點就暫不詳細說明) #### `write_golomb` 在壓縮時，會透過 write_golomb 來填入對應的 bit ```cpp static void write_golomb(generic_io_t *io, size_t k, uint32_t N) { assert(k < 32); write_unary(io, N >> k); write_bits(io, N, k); } ``` * 對於 N / $2^k$ 的商部份，使用 unary code 編碼 * 對於 N % $2^k$ ，也就是 N / $2^k$ 餘數部份，計算相應結果後寫入 #### `write_unary` ```cpp static void write_unary(generic_io_t *io, uint32_t N) { for (; N > 32; N -= 32) write_zero_bits(io, 32); write_zero_bits(io, N); put_nonzero_bit(io); } ``` * `write_unary` 會根據商的結果寫入 q 個 0 加上一個 1 * `write_zero_bits` 一次最多允許寫 32 個 bits，因此如果要寫的總數超過，要透過 for 迴圈依次進行 * `put_nonzero_bit` 寫入一個 1 #### `write_bits` ```cpp static void write_bits(generic_io_t *io, uint32_t b, size_t n) { assert(n <= 32); for (int i = 0; i < 2; ++i) { assert(io->c < 32); size_t m = MIN(32 - io->c, n); io->b |= (b & (((uint32_t) 1 << m) - 1)) << io->c; io->c += m; if (io->c == 32) flush_buffer(io); b >>= m; n -= m; if (n == 0) return; } } ``` * 把 b 的後 n 個 bits 寫入，事實上就等同在取 `b % n` 的結果做編碼，但需考慮到餘數編碼可能會橫跨兩個 byte 儲存，需要兩個迴圈去做對應的處理 #### `read_golom` 反之將資料解壓縮 ```cpp static uint32_t read_golom(generic_io_t *io, size_t k) { uint32_t N = read_unary(io) << k; N |= read_bits(io, k); return N; } ``` * 根據 `read_unary`，從 leading zero 到第一個 1 的 prefix 可以得出原本數字的商 * 結合 read_bits 得到的餘數部份，則可以解壓縮出原本的數字 `N` 下面來檢驗一下我們對程式的理解是否有錯誤: * 假設壓縮一個文字檔，其中內容只有 `A` (ASCll = 65) 和一個換行符號 (ASCll = 10) * 對於 65 / 8 = 8 ... 1 因此對於 `A` 的編碼為 001100000000(注意要從右往左看) * 對於 10 / 8 = 1 ... 2 因此對於換行符號的編碼為01010 * 因此整合兩個結果會是 0 1010 0011 0000 0000，因此前 4 個 byte 會是 a300，這一致於 hexdump 輸出的結果 ```shell $ hexdump output 0000000 a300 0000 0000 0002 0000008 ``` * 最後還會對 EOF(ASCll = 256) 做編碼，這裡就不繼續說明 ### 改寫 x-compressor 為 Exponential-Golomb coding 原本的壓縮是使用 Golomb-Rice coding，這裡我們基於原始的實作，根據維基百科上對演算法的敘述，抽換壓縮技巧為 Exponential-Golomb coding。 #### `write_expgolomb` ```cpp static uint32_t reverse(uint32_t x) { x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); return((x >> 16) | (x << 16)); } static void write_expgolomb(generic_io_t *io, size_t order, uint32_t N) { // 1. Encode ⌊x/2k⌋ using order-0 exp-Golomb code uint32_t B = (N >> order) + 1; assert(B != 0); int zero_write = 32 - __builtin_clz(B) - 1; // since zero_write won't larger then 32, so we can write zero bits directly write_zero_bits(io, zero_write); int total_bits = 32 - __builtin_clz(B); write_bits(io, reverse(B) >> (32 - total_bits), total_bits); // 2. Encode x mod 2k in binary uint32_t mod = N & ((1 << order) - 1); write_bits(io, mod, order); } ``` 將 `x_compress` 中兩處的 `write_golomb` 換成 `write_expgolomb`，其中有幾點需注意: * order 為多少才可以最好的壓縮我們的資料呢？之後會再根據文獻或者實驗去對參數的選擇做修改。 * 為使解碼正確，先將 `B` 反轉再編碼，如何反轉？編碼的部份如何有效的 bitwise 處理？目前尚未周延考慮何種才是最佳的作法下面來檢驗一下程式是否有錯誤(以 order 0 為例): * 假設壓縮一個文字檔，其中內容只有 `A`(ASCll = 65) 和一個換行符號(ASCll = 10) * 對於 65 + 1 = 0b1000010 因此對於 A 的編碼為 0100001000000(注意要從右往左看) * 對於 10 + 1 = 0b1011 因此對於換行符號的編碼為1101000 * 因此整合兩個結果會是 1101 0000 1000 0100 0000，因此前 5 個 byte 會是 d0840，這一致於 hexdump 輸出的結果 ```shell $ hexdump out 0000000 0840 000d 0000 0010 0000008 ``` #### `read_expgolomb` ```cpp static uint32_t read_expgolom(generic_io_t *io, size_t order) { uint32_t N = read_unary(io); uint32_t rb =read_bits(io, N); uint32_t num = reverse((rb << 1) | 1) >> (32 - N - 1); rb = read_bits(io, order); return (((num - 1) << order) | rb ) ; } ``` 解讀的部份則顯而易懂：首先藉由 0 的數量決定後續要讀出的數量，經過反轉和位移處理後則可以得到原本的數字。根據 order 的不同，後續也要做出相對應的處理。詳細請參考 [RinHizakura/x-compressor](https://github.com/RinHizakura/x-compressor)(目前用 `make check` 測試 order = 0, 1, 2 都沒問題) :::warning TODO: 1. 依據資料特性，比較 Exponential-Golomb coding 及 Golomb-Rice coding 對資料壓縮的影響; 2. 參照 `git log`，原本 `x-compressor` 支援多個 layer，用以強化壓縮率 :notes: jserv ::: ## 測驗 `3` 思考一下各步驟在 bitwise 操作上的意義： * 如果是奇數：表示最後一個位元是 1，減 1 是把最後一個 bit 設為 0 * 如果是偶數：表示最後一個位元是 0，除 2 就是向右位移把演算法的流程圖畫出來就像這樣： ```graphviz digraph g{ node [shape="box", fontcolor=black,fontsize=16,style=filled, fillcolor=aquamarine ] start[shape=ellipse, fontcolor=white,style=filled, fillcolor=tomato,label="start"] condition[label="last bit == 1?",shape="diamond", fontcolor=white, fillcolor=darkorange] terminate[label="total bit == 1?",shape="diamond", fontcolor=white, fillcolor=darkorange] C[label="total bit = ??",fillcolor=yellow] { rank = same A[label="right shift \n(step++, total bit -= 1)"] B[label="set last bit to 0 \n (step ++)"] end[shape=ellipse, fontcolor=white,style=filled, fillcolor=tomato] } start->C->terminate condition->B[label=" yes", fontcolor=blue,fontsize=24,color=green] B->terminate terminate:w->condition[label=" no", fontcolor=blue,fontsize=24] condition:w->A[label=" no", fontcolor=blue,fontsize=24,color=red] terminate->end[label=" yes", fontcolor=blue,fontsize=24] A->condition } ``` 終止條件是 `total bit == 1`(因為最後一步必然是 1 變成 0，表示最後一個位元不需要做 right shift)，所以紅色的 edge 會走剛好整整 `total bit - 1` 次，而走過綠色 edge 的次數則是根據整個 `num` 中有幾個 1，也就是 `popcount` 在計算的數量。至於 `total bit` 實際上是多少呢？就是表達該數字需要的最少位元數量(比如說 8 = 0b1000，所以 total bit = 4)，而這個數量可以根據 32 - `clz(num)` 就可以被計算出來。所以此題的答案是 `__builtin_popcount(num) + 32 - __builtin_clz(num) - 1` = `__builtin_popcount(num) + 31 - __builtin_clz(num)` 。`AAA` = `(a) __builtin_popcount(num)`，`BBB` = `__builtin_clz(num)` ## 測驗 `4` 根據 [Greatest Common Divisor 特性和實作考量](https://hackmd.io/@sysprog/gcd-impl) 中的 [Binary GCD Algorithm](https://iq.opengenus.org/binary-gcd-algorithm/) 來閱讀程式。 * `for (shift = 0; !((u | v) & 1); shift++)` 迴圈在判斷是否 u 和 v 皆為偶數，如果 u 和 v 皆為偶數，則 gcd(u, v) = 2 * gcd(u/2, v/2) * 經過前面步驟的 u 和 v 的數值可能會改變(假設是 $u'$、$v'$)，所以接下來要先解 gcd($u'$, $v'$)，最後的結果再位移先前除 2 的次數 * `while (!(u & 1))` 在計算: 如果 $u'$ 為偶數，則 gcd($u'$, $v'$) = gcd($u'$/2, $v'$) * `do` 迴圈的第一個 iteration，`while (!(v & 1))` 在計算: 如果 $v'$ 為偶數，則 gcd($u'$, $v'$) = gcd($u', v'$/2) * 然後剩下的其實就是輾轉相除法(Euclidean algorithm)，並且會確保進入下一個迴圈的 v' 是比較小的那個值，重複直到**進入這次輾轉相除時的 u 和 v 相同**，因此 `XXX` = `(b) v`(因為在判斷式時 v 已經是前面計算的 t) * 則這個相同的數字就是最大公因數，也就是 $u'$，再位移最開始除 2 的次數，所以 `YYY` = `(e) u << shift` ### 透過 `__builtin_ctz` 改寫注意到下面的實驗中會將 quiz3 中題目的作法命名為 `fast gcd`，使用 `__builtin_ctz` 調整後的版本則稱為 `faster gcd` 以方便解釋。前面的 `for (shift = 0; !((u | v) & 1); shift++)` 迴圈可以使用 `__builtin_ctz` 來改寫為如下: ```cpp #ifndef min #define min(x, y) ((x) < (y) ? (x) : (y)) #endif uint64_t faster_gcd64(uint64_t u, uint64_t v){ if (!u || !v) return u | v; int shift = min(__builtin_ctz(u), __builtin_ctz(v)); u >>= shift; v>>= shift; while (!(u & 1)) u >>= 1; do { while (!(v & 1)) v >>= 1; if (u < v) { v -= u; } else { uint64_t t = u - v; u = v; v = t; } } while (v); return u << shift; } ``` 則可以將 for 迴圈中的操作化簡，減少程式分支和對此操作的總指令數量。而為了比較兩者的效能區別而設計對應的實驗：對於相同 ctz 的 a 和 b，進行 50 次實驗並測量時間，注意一些細節: * 為了確保平等的比較兩個方法，原本的 fast gcd 中的 `/ 2` 都替換成 `<< 1` (雖然經過最佳化後可能沒有差別) * 這裡我使用了一些技巧來確保 a 和 b 可以有固定數量的 trailing zero，當然時間的比較會基於相同 a、b 來計算 * 此外，這個實驗中 a 和 b 會是同樣數量的 trailing zero，但是也該考慮 trailing zero 的不同排列組合來設計實驗(暫時還沒想到如何視覺化可以比較好的觀察結果) 實驗程式以最佳化參數 `-O2` 進行編譯，初步我嘗試用 3 維的圖形來觀察希望可以更好的視覺化實驗結果，不過似乎不是那麼理想QQ 但還是可以從圖中觀察觀察一些資訊 * 紅色的點(透過 `__builtin_ctz` 改寫的版本) 整體上會有較佳的執行時間 * 隨著數字的 ctz 越大，Euclidean algorithm 的操作次數就有機會變得更少，所以 y 軸是向 ctz of and b = 30 的地方傾斜的 ![](https://i.imgur.com/TKTNFBt.png) 重新設計實驗：對兩個方法進行 1000 次的實驗，排除標準差 2 外的 outlier 後繪制 boxplot 來視覺化實驗結果，則可以進一步看出其中差距 ![](https://i.imgur.com/wZgxS3Y.png) 可以看到藍色的 fasted_gcd 執行的效率較佳，同時也可以看出前面所說時間會往 ctz = 30 傾斜的狀況。 ## 測驗 `5` `bitmap` 中有 `bitmapsize` 個 64 位元的整數，因此可以用來表示一串 64 * `bitmapsize` 的數字。而 `naive` 程式就是在計算這些數字中哪些位置為 1，儲存在 `out` 中，而 `pos` 則是結果為 1 的總數。在 `naive` 的解法中，我們會逐一檢查每一個 bit 是否為 1，去紀錄該位置。但事實上，如果我們把問題轉換成： **找出最右邊的 1**(顯然可以透過前面的 `ctz` 做到) + 將最右邊的 1 設成 0，則重複此步驟，我們就可以不必依序檢查每個 bits，得到相同的結果。如何將最右邊的 1 設成 0 呢？我們知道如果 A & $\bar{A}$ = 0(每個 bit 都相異)，$A$ & $(\bar{A} + 1)$ 則會得到和 A 最右邊的 1 相同位置為 1，其他為 0 的 mask `t`，與此 mask 做 XOR 運算就可以消除最右邊的 1 。因此此題答案為：`KKK` = `(e) bitset & -bitset`。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.