# 2020q3 Homework3 (quiz3)
contributed by < `zzzxxx00019` >
> [2020q3 第 3 週測驗題](https://hackmd.io/@sysprog/2020-quiz3#2020q3-%E7%AC%AC-3-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C)
> [Github](https://github.com/zzzxxx00019/quiz3)
## 測驗 1
### 題目：
$-5≫^{arith}1=-3$
上述 $-3$ 正是 $\dfrac{-5}{2}$ 的輸出，並向 $−∞$ 進位。
針對有號整數的跨平台 ASR 實作如下:
```cpp
int asr_i(signed int m, unsigned int n)
{
const int logical = (((int) -1) OP1) > 0;
unsigned int fixu = -(logical & (OP2));
int fix = *(int *) &fixu;
return (m >> n) | (fix ^ (fix >> n));
}
```
請補完程式碼。
### 原理：
* 根據 C 語言規格書所述，對有號型態的物件進行算術右移歸屬於 [unspecified behavior](https://hackmd.io/@sysprog/c-undefined-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.
* 因此 logical 所做的事，就是確認目前的執行環境，是「邏輯右移」還是「算數右移」
* 透過 `(int) -1` 確認執行環境狀態，將 `-1` 右移一個 bit ，因此 OP1 為 `>>1`
* 邏輯右移：將最左的 bit 補 0 ，結果 > 0 ，`logical = 1`
* 算數右移：將最左的 bit 補上原本失去的符號，在此補上 1 ，結果 < 0 ，`logical = 0`
* 若執行環境為邏輯右移 ( `logical = 1` )，且` m < 0` ，就需要對最左 bit 補上有號狀態，因此可推測出 OP2 為 `m < 0`
* `*(int *) &fixu` 用意在於將 `fixu` 強制轉型為 `int` 型態
* 若環境為`邏輯右移`且 `m < 0` ， `fix` 經強制轉型後為 `-1`，透過 `(fix ^ (fix >> n))` 保留下需補上的有號 bit ，確保與 `m >> n` 後的結果做 `or` 運算不會失真
**邏輯右移示意圖**
右移後最左 bit 空下來的部分補 0 ，導致輸出結果 > 1， `logical = true`
```graphviz
digraph
{
node[shape = record]
int[label = "(int) -1", shape=plaintext]
data_1 [label = "<f0>1|<f1>1|<f2>...|<f3>1|<f4>1"]
{rank = same ; int data_1}
shift[label = ">>1", shape=plaintext]
data_2 [label = "<f0>0|<f1>1|<f2>...|<f3>1|<f4>1"]
{rank = same ; shift data_2}
data_1:f0 -> data_2:f1
data_1:f1 -> data_2:f2
data_1:f2 -> data_2:f3
data_1:f3 -> data_2:f4
}
```
**算數右移示意圖**
右移後最左 bit 補上原本的算術符號，最後輸出結果 < 0 ，`logical = false`
```graphviz
digraph
{
node[shape = record]
int[label = "(int) -1", shape = plaintext]
data_1 [label = "<f0>1|<f1>1|<f2>...|<f3>1|<f4>1"]
{rank = same ; int data_1}
shift[label = ">>1", shape = plaintext]
data_2 [label = "<f0>1|<f1>1|<f2>...|<f3>1|<f4>1"]
{rank = same ; shift data_2}
data_1:f0 -> data_2:f1
data_1:f1 -> data_2:f2
data_1:f2 -> data_2:f3
data_1:f3 -> data_2:f4
}
```
如果執行環境試算數右移，那麼 logical = false ， fixu = 0 ，因此這邊只針對邏輯位移特別討論，觀察程式是如何補上原本失去的有號狀態，這邊以 $-5≫^{arith}1$ 為例子：
`fixu = -(logical & (m < 0))`
```graphviz
digraph
{
node[shape = record]
logical [label = "(logical) 1", shape = plaintext]
data_1 [label = "<f0>0|<f1>0|<f2>...|<f3>0|<f4>1"]
{rank = same ; logical data_1}
check [label = "(m < 0) 1", shape = plaintext]
data_2 [label = "<f0>0|<f1>0|<f2>...|<f3>0|<f4>1"]
{rank = same ; check data_2}
data_1:f4 -> data_2:f4
and_result [label = " logical & (m < 0) ", shape = plaintext]
data_3 [label = "<f0>0|<f1>0|<f2>...|<f3>0|<f4>1"]
{rank = same ; and_result data_3}
data_2:f4 -> data_3:f4
result [label = "fixu = - ( logical & (m < 0) )", shape = plaintext]
data_4 [label = "<f0>1|<f1>1|<f2>...|<f3>1|<f4>1"]
{rank = same ; result data_4}
data_3:f0 -> data_4:f0
data_3:f1 -> data_4:f1
data_3:f2 -> data_4:f2
data_3:f3 -> data_4:f3
data_3:f4 -> data_4:f4
}
```
從上述過程可以觀察到，一旦邏輯右移與 `m < 0` 同時成立，則 `fixu = 0xff..f` ；反之，若其中一個條件不成立，則 `fixu = 0x0` ，而接下來 fixu 的工作，就是補上右移後所失去的有號狀態，以目前的例子來說明， `-5` 右移 `1 bit` 後，最左邊的 `bit` 會被補上 `0` 導致輸出結果為正數， `fix ^ (fix >> n)` 可將失去的有號狀態補回，再藉由 `or` 運算修正回正常結果；若 `fix` 為 `0` ，則以上運算出來結果並不影響 `m >> n` 的輸出，意即 `result | 0x0 = result`
**fix ^ ( fix >> n ) 運算示意圖**
```graphviz
digraph
{
node[shape = record]
int[label = "fix", shape = plaintext]
data_1 [label = "<f0>1|<f1>1|<f2>...|<f3>1|<f4>1"]
{rank = same ; int data_1}
shift[label = "fix >> 1", shape = plaintext]
data_2 [label = "<f0>0|<f1>1|<f2>...|<f3>1|<f4>1"]
{rank = same ; shift data_2}
data_1:f0 -> data_2:f0
data_1:f1 -> data_2:f1
data_1:f2 -> data_2:f2
data_1:f3 -> data_2:f3
data_1:f4 -> data_2:f4
result[label = " fix ^ ( fix >> 1 )", shape = plaintext]
data_3 [label = "<f0>1|<f1>0|<f2>...|<f3>0|<f4>0"]
{rank = same ; result data_3}
data_2:f0 -> data_3:f0
data_2:f1 -> data_3:f1
data_2:f2 -> data_3:f2
data_2:f3 -> data_3:f3
data_2:f4 -> data_3:f4
}
```
**(m >> n) | (fix ^ (fix >> n)) 修正輸出示意圖**
```graphviz
digraph
{
node[shape = record]
fix[label = " fix ^ ( fix >> 1 )", shape = plaintext]
data_1 [label = "<f0>1|<f1>0|<f2>...|<f3>0|<f4>0"]
{rank = same ; fix data_1}
result [label = "-5 >> 1", shape = plaintext]
data_2 [label = "<f0>0|<f1>1|<f2>...|<f3>0|<f4>1"]
{rank = same ; result data_2}
data_1:f0 -> data_2:f0
fix_result [label = "(m >> n) | (fix ^ (fix >> n))", shape = plaintext]
data_3 [label = "<f0>1|<f1>1|<f2>...|<f3>0|<f4>1"]
{rank = same ; fix_result data_3}
data_2:f0 -> data_3:f0
}
```
## 測驗 2
### 題目：
>Built-in Function: `int __builtin_ctz (unsigned int x)`
>* Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
>
>Built-in Function: `int __builtin_clz (unsigned int x)`
>* Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
我們可用 `__builtin_ctz` 來實作 LeetCode [342. Power of Four](https://leetcode.com/problems/power-of-four/)，假設 int 為 32 位元寬度。實作程式碼如下:
```cpp
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ);
}
```
請補完程式碼。
### 原理：
* 假設 n 為 2 的倍數，且 n > 0 ，從二進制角度觀察， n 的最右個 bit 為 1 ，其他值為 0 ，則 n & n-1 必為 0
* 但題目要求為 4 的倍數，因此需要考慮到 n=2 的情況，若 n=2 ，則 `(__builtin_ctz(num) OPQ)` 不為 0
* 透過 n=4 與 2 代入，只有在 `OPQ=&0x1` 時，符合題目要求
### 延伸問題：
1. 改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量
* 若 n 為 2 的倍數，以二進制表示下，只有其中一值為 1 ，其他皆全為 0
* 若 n 為 4 的倍數，在二進制表示下，一次會向右位移 2 格，因此透過 `__builtin_ctz(num)` 計算的結果，會皆為偶數
* 透過 `__builtin_popcount(num)` ，可知 `1-bits` 的個數
>Built-in Function: int __builtin_popcount (unsigned int x)
>* Returns the number of 1-bits in x.
```cpp=
bool isPowerOfFour(int num)
{
return __builtin_popcount(num) == 1 && ( __builtin_ctz(num)%2) == 0 ;
}
```
2. LeetCode [1009. Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/)
* 透過 xor 運算，做 bit 翻轉
* 利用 `__builtin_clz(N)` ，計算需運算 xor 的有效長度
* 根據 `__builtin_clz(N)` 說明， `N=0 is undefined` ，因此需額外考慮 N=0 的狀況
```cpp=
int bitwiseComplement(int N)
{
if(N==0) return 1 ;
return N^(0xffffffff >> __builtin_clz(N)) ;
}
```
3. LeedCode [41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/)
* 因為此題是為了找出陣列中，未出現的最小正整數，因此可將數值安插在所屬的陣列位置，例如 `1` 放在 `nums[0]` ， 3 放在 `nums[2]` 這樣的手法，再透過對陣列內容尋訪，若該位置 `nums[i]` 沒有放入數值，那麼最小值就是 `i+1` ，若陣列中每個位置都有對應的值，則最小值為 `NumsSize+1`
* 排序過程所需時間複雜度為 $O(n)$ ，而在尋訪陣列尋找最小值時， `wosrt case` 為 $O(n)$ ，即陣列中每個位置都有數值，因此在 `worst case` 下，整體時間複雜度為 $O(2n)$
* 排序方法說明：若 `nums[i]` 不為正整數，就不在排列目標名單中，直接將其值設為 0 ；如果 `nums[i]` 未超出 numsSize (可被安排於陣列內)，且目標位置內尚未存放目標值，則做交換的動作，交換過程需考慮到同值交換 ( 程式碼10~16行 ) 而導致的無窮迴圈
* 以陣列 `[4,1,3,5,6]` 為例，最後排列的結果會為 `[1,0,3,4,5]` ，因此輸出結果為 `2`
```cpp=
int firstMissingPositive(int* nums, int numsSize)
{
for(int i=0 ; i<numsSize ; i++)
{
if(nums[i] > 0)
{
if (nums[i] < (numsSize+1) && (i+1) != nums[i])
{
int tmp = nums[i] ;
if(nums[i] == nums[tmp-1]) nums[i] = 0 ;
else
{
nums[i] = nums[tmp-1] ;
nums[tmp-1] = tmp ;
i-- ;
}
}
else if (nums[i] > numsSize) nums[i] = 0 ;
}
else nums[i] = 0 ;
}
for(int i=0 ; i<numsSize ; i++)
{
if(nums[i] == 0) return i+1 ;
}
return numsSize+1 ;
}
```
## 測驗 3
### 題目：
針對 [LeetCode 1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)，我們可運用 gcc 內建函式實作，假設 int 寬度為 32 位元，程式碼列表如下:
```cpp
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
請補完程式碼。
### 原理：
* 在二進制表示法中，每個 1 最後都要進行 -1 的動作，每向右挪 1 bit 都要進行除 2 的動作，直到最後最後結果剩下 1 ，再做最後的 -1 ，過程有點類似透過「短除法」將十進制轉為二進制
* 透過 `31 - __builtin_clz(num)` 計算需要往右挪多少次
* 再透過 `__builtin_popcount(num)` 計算需要 `-1` 多少次
### 延伸問題：
1. 改寫上述程式碼，提供等價功能的不同實作並解說
* 透過 `(num|0x1)` 的動作，避免 `__builtin_clz()` 發生輸入為 0 的狀況，且不影響整體執行結果
```cpp
int numberOfSteps(int num)
{
return 31 - __builtin_clz(num|0x1) + __builtin_popcount(num) ;
}
```
2. 避免用到編譯器的擴充功能，只用 C99 特徵及 bitwise 運算改寫 [LeetCode 1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)，實作出 branchless 解法，儘量縮減程式碼行數和分支數量
* 引用題目所提供的 `popcnt_branchless` 實作方法來取代原本的 `__builtin_popcount`
* 引用 [Bit Twiddling Hacks](http://graphics.stanford.edu/~seander/bithacks.html) 所提供的 **Find the log base 2 of an N-bit integer in O(lg(N)) operations** 方法來找尋從右邊開始數的最高位有效 bit ，且允許 0 的情況輸入
```cpp=
int log2N(int v)
{
int r; // result of log2(v) will go here
int shift;
r = (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3 ) << 1; v >>= shift; r |= shift;
r |= (v >> 1);
return r ;
}
int popcnt_branchless(uint32_t v)
{
uint32_t n;
n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
v = (v + (v >> 4)) & 0x0F0F0F0F;
v *= 0x01010101;
return v >> 24;
}
int numberOfSteps (int num)
{
return popcnt_branchless(num) + log2N(num) ;
}
```
## 測驗 4
### 題目：
考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式:
```cpp
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
while (!(u & 1))
u /= 2;
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (XXX);
return YYY;
}
```
請補完程式碼。
### 原理：
* 透過一開始的程式碼，了解輾轉相除法的整個過程：
* 根據輾轉相除法的概念，當過程執行到 u 、 v 其中一值為 0 ，則最大公因數為不為 0 的那個數，因此可以得知 $gcd(a,0)=a$ 的特性， `if (!u || !v) return u | v` 此部分就是在確認 u 、 v 是有 0 存在
* 再來輾轉相除法是依循著 $gcd(a,b)=gcd(b,a$ $mod$ $b)$ 這個概念在進行，整個 `while` 迴圈就是在做這樣的重複計算，直到 `v = 0` 為止
```cpp=
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
while (v) {
uint64_t t = v;
v = u % v;
u = t;
}
return u;
}
```
* 回到最大公因數的概念，如果兩數都可被 2 連除，則最大公因數必參雜著 $2^n$
* 透過 `(u | v) & 1` 這個計算動作，確認 u 、 v 兩者皆為偶數，若其中 1 值為奇數，與 1 做 & 計算後會有不為 0 的結果，並透過 shift 這個變數，紀錄總共右移多少次，來得到兩數皆為 0 或產生至少一個奇數的計算結果
* 因為奇數與偶數無法做到整除的動作，因此透過 while 迴圈將判斷 u 是否為偶數，若是的話就進行除 2 的動作
* 再比較 u 、 v 大小，透過相減的方式，使 v < u ，而 else 的部分，則是 v =< u 的狀況，將 u - v，然後再與 v 對調
* 而輾轉相除法的結束條件就是其中一值被減為 0 ，因此 `XXX = v`
* 輾轉相除法的最後結果就如同一開始所述，為 $gcd(a,0)=a$ ，但一開始有做對 2 連除的動作，因此這邊補上連除後的結果，故 `YYY = u << shift`
### 延伸問題：
1. 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升
* 藉由 `__builtin_ctz( u|v )` ，可快速計算出shift的值
* 將原本透過 `while` 計算出的 `shift` 改由 `__builtin_ctz( u|v )` 來執行 ( 5~11 行)
```cpp=
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
int shift;
shift = __builtin_ctz( u|v ) ;
if(shift)
{
u >>= shift ;
v >>= shift ;
}
if (!(u & 1))
u >>= __builtin_ctz(u) ;
do {
if (!(v & 1))
v >>= __builtin_ctz(v) ;
if (u < v)
{
v -= u;
}
else
{
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u<<shift;
}
```
因為 `__builtin_ctz()` 主要是在對一開始判斷是否存在著因數 $2^n$ 進行優化，因此在測試設計上，針對 u 、 v 都為偶數的狀態去做測試，並透過 [perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 進行效能分析：
```gcc
int main()
{
for(int i = 0 ; i < 0xffff ; i+=2)
{
for(int j = 0 ; j < 0xffff ; j+=2)
{
gcd64(i, j) ;
}
}
return 0 ;
}
```
* 以原本的方法進行測試：
```
Performance counter stats for './perf_test.o':
15,0863.80 msec task-clock # 1.000 CPUs utilized
624 context-switches # 0.004 K/sec
23 cpu-migrations # 0.000 K/sec
45 page-faults # 0.000 K/sec
6258,6631,7894 cycles # 4.149 GHz
3804,6978,9838 instructions # 0.61 insn per cycle
976,2472,2490 branches # 647.105 M/sec
141,9692,1133 branch-misses # 14.54% of all branches
150.882867503 seconds time elapsed
150.864725000 seconds user
0.000000000 seconds sys
```
* 透過 `__builtin_ctz()` 取代 while 迴圈的方法測試：
```
Performance counter stats for './perf_test.o':
8,4535.58 msec task-clock # 1.000 CPUs utilized
303 context-switches # 0.004 K/sec
10 cpu-migrations # 0.000 K/sec
45 page-faults # 0.001 K/sec
3499,8308,2866 cycles # 4.140 GHz
2541,5180,7243 instructions # 0.73 insn per cycle
552,3677,8057 branches # 653.415 M/sec
51,5058,8256 branch-misses # 9.32% of all branches
84.536884443 seconds time elapsed
84.536043000 seconds user
0.000000000 seconds sys
```
:::info
可以發現，透過 `while` 的方式計算 shift ，在 `branch` 使用上，比 `__builtin_ctz()` 多了將近一倍的數量，這也是導致效能低落的主要原因。
:::
## 測驗 5
### 題目：
在影像處理中，[bit array](https://en.wikipedia.org/wiki/Bit_array) (也稱 `bitset`) 廣泛使用，考慮以下程式碼:
```cpp
#include <stddef.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
for (size_t k = 0; k < bitmapsize; ++k) {
uint64_t bitset = bitmap[k];
size_t p = k * 64;
for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
}
}
return pos;
}
```
可用 clz 改寫為效率更高且等價的程式碼:
```cpp
#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
uint64_t bitset;
for (size_t k = 0; k < bitmapsize; ++k) {
bitset = bitmap[k];
while (bitset != 0) {
uint64_t t = KKK;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
請補完程式碼。
### 原理：
先理解這個程式的目標是在實作什麼功能，有一個存放 `64-bits` 的 `array ( bitmap )` ，裡面共可存放 `bitmapsize` 個變數，而 `array` 是透過連續記憶體分配的方法去實作，在 `bitmap` 中，每一個數字占用 `64-bits` 的空間， `bitmap[0]` 區段為 0-63 ， `bitmap[1]` 區段為 64-127 以此類推，而整個程式的運作目的是透過 `out` 這個陣列，去依序儲存在這連續的記憶體空間裡面，出現 `bit 1` 的位置，而 `pos` 則是回傳出現 `bit 1` 的數量。
舉個例子來說，輸入 `bitmap = [0,1]` ，會得到 `pos = 1` ，`out[0] = 64` 這樣的結果，因為第一個數字為 0 ，在前 64 個 bit 中，沒有任何 1 出現，而第二個數字為 1 ，因此在第二個數字個第一個 bit 為 1 ，對應的連續位置為 64 。
```graphviz
digraph
{
node[shape = record]
p0 [label = "0", shape = plaintext]
p64 [label = "64", shape = plaintext]
p128 [label = "128", shape = plaintext]
{rank = same ; p0 p64 p128}
//bitmap[label = "bitmap", shape = plaintext]
data [label = "<h0>|<f0> bitmap[0] |<h1>|<f1> bitmap[1]|<h2>|<f2> bitmap[2]|<h3>|<f3> . . . . . . "]
//{rank = same ; bitmap data}
p0 -> data:h0
p64 -> data:h1
p128 -> data:h2
}
```
* `naive` 運作流程解釋：
* 透過 `bitset` 來記錄當前所讀到的數值
* 透過 `p = k*64` 來計算目前數值所對應到的連續位置起始值
* 透過迴圈逐一右移再與 `1` 做 `&` 計算，確認是否為 `bit 1`
* 如果是的話，則將該位置 `p + i` 儲存到 `out` 陣列中
* `improved` 運作流程解釋：
* 透過 `__builtin_ctzll` 來計算當前的 `bitset` 中 `bit 1` 的位置，計算完成後，將該位置的 `bit` 清為 0 ，再繼續判斷 `bitset` 中是否還有 `bit 1` 存在
* 在二進制系統中，負整數的表示方式是透過將正整數的每個 bit 做反轉的動作，最後再加上 1 ，且有進位的動作
* 透過 `bitset & -bitset` 這樣的方法，可以將從右數來的第一個 `bit 1` 設為 `1` ，而其他 `bit` 經過運算後會全為 `0` ，因為經過翻轉後，原本 `0` 的數字會被翻為 `1` ，而原本右邊數來的第一個 `1` 則會被翻轉為 `0` ，透過 `+1` 且進位的運算，最後就會不斷進位直到將那個 `0` 設為 `1` 為止，而將那個 `bit` 設為 `1` 後，後面的 `bit` 則跟原本的 `bit` 全部相反，因此做 `&` 運算後會全為 `0` ，透過這個方法得到可以將從右數來的第一個 `bit 1` 設為 `0` 的 `mask`
* 最後再透過 `bitset ^= t` 將 `ctz` 指出的` bit` 清為 0 ，得以繼續執行 bit 檢查
* 因此 `KKK = bitset & -bitset`
:::info
**[Bloom filter](https://hackmd.io/@sysprog/2020-dict#%E4%BD%95%E8%AC%82-Bloom-Filter)**
透過特定的 `hash function` ，將對應的 `index` 設為 `1` ，當要檢查某個字串是否可能存在，透過檢查 `hash table` 中，對應的 `index` 狀況，若其中一個 `index` 不為 `1` ，就能很快地確定這個字串不出現在這個資料庫中。
對於 `bloom filter` 實作的方法，其中之一就是特過 `bitset` ，透過只記錄 `true` 跟 `false` 的 `array` 來當作 `hash table` 的方法，更改對應的 `array bit` ，來達到 `bloom filter` 的目的。
:::
### 延伸問題：
* 設計實驗，檢驗 clz 改寫的程式碼相較原本的實作有多少改進？
* 在 `ctz` 的改良版中，是針對 `while` 尋找 `bit 1` 做改進
* 透過比較 `naive` 的 `worst case` ，也就是透過代入 `0x8..0` ，如此在二進制中，將只有第 `64 bit` 為 `1` ，其他都為 `0` ，並反覆測試 `300` 次，再透過 `perf` 去分析兩種方法的執行過程
==naive==
```
Performance counter stats for './a.o':
0.25 msec task-clock # 0.514 CPUs utilized
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
48 page-faults # 0.191 M/sec
99,4935 cycles # 3.963 GHz
79,9795 instructions # 0.80 insn per cycle
15,3597 branches # 611.736 M/sec
4332 branch-misses # 2.82% of all branches
0.000488485 seconds time elapsed
0.000499000 seconds user
0.000000000 seconds sys
```
==improved==
```
Performance counter stats for './a.o':
0.21 msec task-clock # 0.499 CPUs utilized
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
46 page-faults # 0.221 M/sec
84,4957 cycles # 4.055 GHz
59,3354 instructions # 0.70 insn per cycle
11,4697 branches # 550.454 M/sec
4004 branch-misses # 3.49% of all branches
0.000417697 seconds time elapsed
0.000438000 seconds user
0.000000000 seconds sys
```
從中不難發現，在 `improved` 版本中， `instructions` 的數量明顯低於 `naive` 版本，因為 `naive` 是透過對每個 `bit` 做 `& 0x1` 的運算來檢查是否為 `bit 1` ，而對比於 `improved` ，則是透過 `ctz` ，直接找到 `bit 1` 的位置，藉此降低在 `branch` 與 `instrcution` 上的使用。
Sign in with Wallet
Connect another wallet