---
tags: 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統
---
# 2020q3 Homework3 (quiz3)
contributed by <`RusselCK` >
###### tags: `RusselCK`
> [數值系統 ＆ Bitwise 練習題](https://hackmd.io/@sysprog/2020-quiz3)
> [作業繳交區](https://hackmd.io/@sysprog/2020-homework3)
## Q1.在 [二補數系統](https://hackmd.io/@sysprog/binary-representation) 實作跨平台 有號整數的 arithmetic right shift ( ASR )
在 C 語言中，對有號型態的物件進行算術右移 (arithmetic right shift，以下簡稱 ASR 或 asr) 歸屬於 [unspecified behavior](https://hackmd.io/@sysprog/c-undefined-behavior)
```c=
int asr_i(signed int m, unsigned int n)
{
const int logical = (((int) -1) OP1) > 0; // OP1 = >>1
unsigned int fixu = -(logical & (OP2)); // OP2 = m<0
int fix = *(int *) &fixu;
return (m >> n) | (fix ^ (fix >> n));
}
```
提示: 透過 gcc/clang 編譯程式碼時，可加上 `-fsanitize=undefined` 編譯參數，在執行時期若遇到未定義行為，會得到以下錯誤訊息:
>runtime error: load of misaligned address 0x7ffd8a89be8f for type ‘int’, which requires 4 byte alignment
> 以 8 bits 為例：
> -5 >> 1 = ( 1111 1011 ) >>1 = ( ==1==111 1101 ) = -3
* 程式碼解析：
* 我們並不知道電腦進行負整數 ARS 之後，究竟會在空位 補 0 或 補 1
* 我們想要 ==負整數 ARS 後，電腦在空位 補 1==
* 根據上述推測
* 如果電腦照我們的想要的方式補 0 或 1 ， `(fix ^ (fix >> n))` 可為 0 或 正確的 mask
* 反之，`(fix ^ (fix >> n))` 必須為正確的 mask ，將補位換成我們想要的值
>正確的 mask : ( n = 1 )
>fix = ( 1111 1111 )
>`(fix ^ (fix >> n))` = ( ( 1111 1111 ) ^ ( 0111 1111 ) ) = ( 1000 0000 )
```c
#3 const int logical = (((int) -1) OP1) > 0;
```
> -1 = (1111 1111)
* 想知道電腦在負數右移會如何補位，可以利用 `#3` 來得知
( 只須右移 1 位便可得知，故 **OP1 = >>1** )
* 若 `((int) -1) >>1)` 為 ( 0111 1111 ) ，代表電腦在負整數 ARS 會補 0，`logical` 為 `true` = ( 0000 0001 )
( i.e. 此電腦的右移為 邏輯右移 )
* 若 `((int) -1) >>1)` 為 ( 1111 1111 ) ，代表電腦在負整數 ARS 會補 1，`logical` 為 `false` = ( 0000 0000 )
( i.e. 此電腦的右移為 算術右移 )
:::success
$§\space 6.5.7\space Bitwise \space shift \space operators\space$( p. 85 )
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}$ . ( i.e. 正整數 ARS 不會出錯 ）==
If **E1** has a signed type and a negative value, the resulting value is implementation-defined.
:::
```c
#4 unsigned int fixu = -(logical & (OP2));
```
:::success
```c
unsigned int a = -9;
printd("%d\n", a);
```
* output :
```
-9
```
:::
* 若 m < 0 且 `logical` = `true` ( i.e. 電腦在負數 ARS 補位的方式不正確 ）
* 我們想讓 `fixu` 為 ( 1111 1111 )
* `-(logical & (OP2))` = ( 1111 1111 )
* `(0000 0001) & OP2` = ( 0000 0001 ) `// 2's complement`
* OP2 = ( 0000 0001 ) = `true`
* 若 m >= 0 且 `logical` = `false`
* 我們想讓 `fixu` 為 ( 0000 0000 )
* `-(logical & (OP2))` = ( 0000 0000 )
* `(0000 0001) & OP2` = ( 0000 0000 ) `// 2's complement and overflow`
* OP2 = ( 0000 0000 ) = `false`
* 根據上面推導，可假設**OP2 = `m < 0`**
* 若 `logical` = `false`，OP2 = `m < 0` 仍成立
:::warning
問題：( Form [RinHizakura 同學](https://hackmd.io/NfUj_xJdRDKWeMMJuR2imQ?view) )
```cpp
unsigned int fixu = -(logical & (m < 0));
int fix = *(int *) &fixu;
```
和
```cpp
int fix = -(logical & (m < 0));
```
兩個寫法的差異性？
> 前者可避免編譯器進行過度 (aggressive) 最佳化
> :notes: jserv
:::
## Q1. 進階題
#### 實作其他資料寬度的 ASR
* 參照 [C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor) 撰寫通用的巨集以強化程式碼的共用程度
```cpp=
#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); }
int main(){
...
asr_i(m, n);
...
}
```
* `#1`~`#7` : 根據不同的 [data model](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models)，`asr_i(m, n)` 會使用相對應的 function
* `#15`~`#18`中的`asr(type)` 會轉換成相對應的內容 ( i.e. `#10`~`#13` )
:::warning
問題：( Form [RinHizakura 同學](https://hackmd.io/NfUj_xJdRDKWeMMJuR2imQ?view) )
乍想之下，無論型別都直接轉型成 64 bits 的版本處理，計算出結果後再轉回原本的型別，似乎正確性上是沒有問題的？這樣想是否完全正確呢？排除正確性的話，這樣方式的實作可能有甚麼缺點？
> 不是每款 C 語言編譯器都能正確處理 64 位元，且 data model 會涉及 ABI 議題
> :notes: jserv
:::
## Q2. LeetCode [342. Power of Four](https://leetcode.com/problems/power-of-four/) (`__builtin_ctz` 實作)
* 假設 `int` 為 32 位元寬度
```c=
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ); // OPQ = & 0x1
}
```
:::info
[GCC extension](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 其中兩個是 ctz 和 clz:
* **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.** ( 返回右起第一個 1 之後的 0 的個數 )
* 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.** ( 返回左起第一個 1 之前 0 的個數 )
* If x is 0, the result is undefined.
:::
* 觀察 $4^n$：
| $4^n$ | $4^n$ in binary | __builtin_ctz($4^n$) |
|:----- |:--------------- |:-------------------- |
| $4^0$ | 0000 000==1== | 0 |
| $4^1$ | 0000 0==1==00 | 2 |
| $4^2$ | 000==1== 0000 | 4 |
| $4^3$ | 0==1==00 0000 | 6 |
| $4^k$ | ... | ==2$k$== |
* 程式碼解析：
```c
num > 0
```
* 若 $4^n$ 為整數，則 $4^n$ 必大於 0
```c
(num & (num - 1))==0
```
* 我們可以發現， $4^n$ 在 二進制表示中，只會有 1 個 1
> 以 $4^2$ 為例：
> (num & (num - 1)) = (( 0001 0000 ) & ( 0000 1111 ) ) = ( 0000 0000 )
```c
!(__builtin_ctz(num) OPQ)
```
* 我們可以發現，__builtin_ctz($4^n$) 的值必為偶數
* 必為偶數 = 不為奇數 = 第 1 個 bit 不為 1
* 因此，**OPQ = & 0x1**
* [效能分析](https://leetcode.com/submissions/detail/403008463/)：
## Q2. 進階題
#### 改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量
```cpp=
bool isPowerOfFour(int num)
{
return (__builtin_popcount(num) == 1) &&
!(__builtin_ctz(num) & 0x1);
}
```
* 觀察$4^n$，我們可以發現，只要二進制形式符合下列兩個條件，該數便是 4 的冪
* 只有 1 個 1 ，其餘全為 0
* 1 後面 0 的數量必為 偶數
* [效能分析](https://leetcode.com/submissions/detail/403010290/)：
* 其他的改寫：
* [RinHizakura 同學](https://hackmd.io/NfUj_xJdRDKWeMMJuR2imQ?view#%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AF%A6%E4%BD%9C)
:::info
* **`int builtin_ffs (unsigned int x)`**
* Returns one plus the index of the least significant 1-bit of x
( 返回右起第一個 1 的位置 )
* if x is zero, returns zero.
:::
#### LeetCode [1009. Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/) ( 利用 clz )
* For a given number N in base-10, return the complement of it's binary representation as a base-10 integer.
* Note that except for N = 0, there are no leading zeroes in any binary representation.
```cpp=
int bitwiseComplement(int N){
if (N == 0)
return 1;
int mask = (1 << (32 - __builtin_clz(N))) - 1;
return ~N & mask;
}
```
>Input: 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.
* 程式碼解析：
```cpp=
#2 if (N == 0)
#3 return 1;
```
* 根據題目提示：passing zero to clz(), which is not a valid argument
```cpp
#5 int mask = (1 << ( 32 - __builtin_clz(N) )) -1;
#6 return ~N & mask;
```
> 以 8 bits 為例
> `N` = 5 = ( ==0000 0==101 )~2~
* 依據題目要求，應該會需要 `~N`= ~5 = ( ==1111 1==010 )~2~ `// 1s' complement`
* 黃色標記的部份應該要為 0
* 需要更改的 bits 數 = m = `__builtin_clz(N)` = 5
* 因此，我們還需要一個 `mask` = ( 0000 0111 )~2~
= ( 0000 1000 ) - 1 = ( 1 << 3 ) - 1 = ( 1 << ( 8 - m ) ) - 1
* 綜合上述，並推廣到 32 bits，可得：
* `mask = (1 << ( 32 - __builtin_clz(N) )) - 1`
* 求解即為 `~N & mask`
* [效能分析](https://leetcode.com/submissions/detail/403020096/)：
#### LeetCode [41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/) ( 利用 clz )
* Given an unsorted integer array, find the smallest missing positive integer.
* Your algorithm should run in O(n) time and uses constant extra space.
##### 失敗版
```cpp=
int firstMissingPositive(int* nums, int numsSize){
int note = 0;
for (int i = 0; i < numsSize ; i++){
if (nums[i] > 0 && nums[i] <= numsSize){
note |= (1 << (nums[i] -1));
}
}
if (note==0)
return 1;
for(int j = 0 ; j < (33 - __builtin_clz(note)); j++){
if (!((note >> j) & 0x1))
return j+1;
}
return 0;
}
```
* 利用 `note` 的各 bit 紀錄，有哪些正整數出現過
* 若 `nums` 中有 4，則 `note |= (0000 1000)`
* 最後利用 `!((note >> j) & 0x1)` 找出最早出現 0 的位置，即為所求
:::danger
runtime error: shift exponent 53 is too large for 32-bit type 'int'
:::
* 顯然 bit 數根本不夠用
##### 成功版
```cpp=
#define XORSWAP(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(nums[i],nums[pos]);
i--;
}
}
}
for(int i = 0;i < numsSize;i++){
if(nums[i] != i + 1)
return i + 1;
}
return numsSize + 1;
}
```
>Input: [1,2,0]
Output: 3
>Input: [3,4,-1,1]
Output: 2
>Input: [7,8,9,11,12]
Output: 1
* 在 [Q5](#Q5-bit-array-%E4%B9%9F%E7%A8%B1-bitset-%E5%9C%A8%E5%BD%B1%E5%83%8F%E8%99%95%E7%90%86%E7%9A%84%E4%BD%BF%E7%94%A8) 中 ，**陣列 `out`** 有 記錄 bit 為 1 所在位置 的功能
* 在這題，我們讓 陣列`num` 也擁有 ==記錄== 的功能
* 第一次走訪的過程中 ( `#6`~`#14` )
* 若 0 < `num[i]` < `numsSize`，則將 `num[i]` 和 `num[num[i]-1]` 互換
* 前提：**位置不同** 且 **內容不同** ( i.e.`(pos != i && nums[i] != nums[pos])`)
* `#11`: 交換完之後，`num[i]` 還要在檢查一次 ( 因為內容有更動 ）
* 第二次走訪 ( `#16`~`#19` )
* 若 位置編號 和 內容 對不上 ( i.e. `nums[i] != i + 1` )，代表應該出現的內容為 Missing Positive
* 對得上的情形：`num[0] == 1`、 `num[1] == 2` etc.
* 第一個 沒出現的正確數值，即為 First Missing Positive
#### 研讀 [2017 年修課學生報告](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/Bk-uxCYxz)，理解 clz 的實作方式，並舉出 Exponential Golomb coding 的案例說明
## [Q3](https://hackmd.io/@sysprog/2020-quiz3#%E6%B8%AC%E9%A9%97-3). 利用 `__builtin_popcount` 來實作 [LeetCode 1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)
* Given a non-negative integer num, return the number of steps to reduce it to zero.
* If the current number is even, you have to divide it by 2,
* otherwise, you have to subtract 1 from it.
* 假設 `int` 為 32 位元寬度
```c=
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
// AAA = __builtin_popcount(num)
// BBB = __builtin_clz(num)
}
```
:::info
* [population count](https://en.wikichip.org/wiki/population_count) 簡稱 popcount 或叫 sideways sum，
* **計算數值的二進位表示中，有多少位元是 1**
* 在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 0 元素個數、計算兩個字串的 Hamming distance。
* GCC 提供對應的內建函式: **`__builtin_popcount(x)`**
:::
>以 14 為例：
>> 1. 14 = ( 0000 1110 ) is even; divide by 2 and obtain 7.
>> 3. 7 = ( 0000 0111 ) is odd; subtract 1 and obtain 6.
>> 4. 6 = ( 0000 0110 ) is even; divide by 2 and obtain 3.
>> 5. 3 = ( 0000 0011 ) is odd; subtract 1 and obtain 2.
>> 6. 2 = ( 0000 0010 ) is even; divide by 2 and obtain 1.
>> 7. 1 = ( 0000 0001 ) is odd; subtract 1 and obtain 0.
* 由上述例子，可以有以下推論：
* **1 所在的最高位元是第 4 個bit**，代表需要 divide by 2 ( i.e. 右移 ) ==3 次==
* 最高位元的 1 只須 subtract 1 ，不用 divide by 2
* **總共有 3 個 1** ，代表需要 subtract 1 ==3次==
* 上面兩項加總，3 + 3 = ==6== 即為所求
* 更廣泛的推論：
* **1 所在的最高位元是第 m 個bit**，代表需要 divide by 2 ( i.e. 右移 ) ==( m - 1 ) 次==
* 最高位元的 1 只須 subtract 1 ，不用 divide by 2
* **總共有 k 個 1** ，代表需要 subtract 1 ==k次==
* 上面兩項加總，==( m - 1 ) + k== 即為所求
* 程式碼：
* ( m - 1 ) = ( 32 - `__builtin_clz(num)` ) - 1
* k = `__builtin_popcount(num)`
* ( m - 1 ) + k = [ ( 32 - `__builtin_clz(num)` ) - 1 ] + `__builtin_popcount(num)`
= `__builtin_popcount(num)` + 31 - `__builtin_clz(num)`
* 故 **AAA = `builtin_popcount(num)`**、**BBB = `builtin_clz(num)`**
## Q3. 進階題
#### 改寫程式碼 ( 利用 [Bit Twiddling Hacks](http://graphics.stanford.edu/~seander/bithacks.html) )
>提示: Bit Twiddling Hacks 中提及許多 bitwise operation 的使用，如 bit inverse、abs 等等，是極好的參考材料。
#### 改寫程式碼 ( 避免用到編譯器的擴充功能，只用 C99 特徵及 bitwise 運算 )
## Q4. 64-bit GCD (greatest common divisor, 最大公因數)
* [Greatest Common Divisor 特性和實作考量](https://hackmd.io/@sysprog/gcd-impl)
#### 有使用 `％` 的版本
```c
#include <stdint.h>
__uint64_t gcd64(__uint64_t u, __uint64_t v) {
/* case 1 : gcd(a, 0) = a */
if (!u || !v) return u | v;
while (v) {
__uint64_t t = v;
v = u % v;
u = t;
}
return u;
}
```
- $\gcd(a, 0) = |a|$
- $\gcd(a, b) = \gcd(b, a)$
- $\gcd(a, b) = \gcd(a, b \% a)$
#### 不使用 `％` 的版本
* [Binary GCD](https://en.wikipedia.org/wiki/Binary_GCD_algorithm)
> [Binary GCD Algorithm](https://iq.opengenus.org/binary-gcd-algorithm/)
```c=
#include <stdint.h>
__uint64_t gcd64(__uint64_t u, __uint64_t v) {
/* case 1 : gcd(a, 0) = a */
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); // XXX = v
return YYY; // YYY = u << shift
}
```
* 程式碼解析：
```cpp
#6 int shift;
#7 for (shift = 0; !((u | v) & 1); shift++) {
#8 u /= 2, v /= 2;
#9 }
```
* binary gcd 的精神就是當兩數為偶數時，必有一 $2$ 因子。
$$
\text{gcd}(u, v) = 2·\text{gcd}(\frac{u}{2}, \frac{v}{2})
$$
* `shift` 紀錄有幾個 $2$ 因子
```cpp
#10 while (!(u & 1))
#11 u /= 2;
```
* 且一數為奇數另一數為偶數，則無 $2$ 因子。
$$
\text{gcd}(u, v) = \text{gcd}(u, \frac{v}{2})
$$
```cpp
#12 do {
#13 while (!(v & 1))
#14 v /= 2;
#15 if (u < v) {
#16 v -= u;
#17 } else {
#18 __uint64_t t = u - v;
#19 u = v;
#20 v = t;
#21 }
#22 } while (XXX);
```
* 假設 $u >= v$ ，總結一些定理：
| $u$ | $v$ | $gcd(u, v)$ |
|:---------:|:---------:|:----------------------------------:|
| $u$ | $0$ | $u$ |
| $even$ | $even$ | $2*gcd( \frac{u}{2},\frac{v}{2} )$ |
| $even$ | $odd$ | $gcd( \frac{u}{2},v )$ |
| $odd$ | $even$ | $gcd( u,\frac{v}{2} )$ |
| ==$odd$== | ==$odd$== | ==$gcd( \frac{u-v}{2},v )$== |
* `#12`~`#22` 便是不斷操作 $gcd(u, v)=gcd( \frac{u-v}{2},v )$ 的部份，直到 `v` = 0 為止
* 因此， **XXX = `v`**
```cpp
#23 return YYY;
```
* `#12`~`#22` 結束後，`v` = 0
* $gcd(u, 0)=u$ ，因此 **YYY = `u << shift`**
* 別忘記 `#6`~`#9` 得到 `shift` 個 2 因子
## Q4. 進階題
#### 在 x86_64 上透過 `__builtin_ctz` 改寫 GCD
```c=
#include <stdint.h>
#define min(x, y) \
((x) < (y) ? (x) : (y)) \
__uint64_t gcd64(__uint64_t u, __uint64_t v) {
/* case 1 : gcd(a, 0) = a */
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 ;
}
```
* 我們可以改良為： ( `#10`~`#12` )
$$ \text{even_factor} = \text{min}(\text{ctz}(x), \text{ctz}(y))$$
$$
\text{gcd}(x, y) = \text{even_factor}·\text{gcd}((x\gg \text{even_factor}), (y\gg \text{even_factor}))$$
#### 分析對效能的提升
## Q5. [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;
}
```
* 程式碼解析：
* 由 `uint64_t *bitmap`、`bitmap[k]`，可以判斷 bitmap 為 uint64_t Array
* 由 `uint32_t *out`、`out[pos++]`，可以判斷 out 為 uint32_t Array
:::success
$§\space 6.4.4.4\space Character \space constants \space$( p. 61 )
* A wide character constant has type `wchar_t`, an integer type defined in the `<stddef.h>` header.
The value of a wide character constant containing a single multibyte character that maps to a member of the extended execution character set is the wide character corresponding to that multibyte character, as defined by the `mbtowc` function, with an implementation-defined current locale.
==The value of a wide character constant containing more than one multibyte character, or containing a multibyte character or escape sequence not represented in the extended execution character set, is implementation-defined.==
:::
```cpp
#04 size_t pos = 0;
#05 for (size_t k = 0; k < bitmapsize; ++k) {
#06 uint64_t bitset = bitmap[k];
```
* 每 64 個 bits 一組進行迴圈
```cpp
#07 size_t p = k * 64;
#08 for (int i = 0; i < 64; i++) {
#09 if ((bitset >> i) & 0x1)
#10 out[pos++] = p + i;
// out[pos] = p + i;
// pos +=1 ;
#11 }
```
* `#09` : 逐一檢查 `bitset` 的 64 個 bits ，只要發現該 bit 為 1 (i.e. `((bitset >> i) & 0x1)` 為 true )，便進入 `#10`
* `#10` : 將 `p + i` 寫入 `out[pos++]`
* `#07` : `bitset` 的第 1 個 bit = `bitmap` 中的第 `p` 個 bit
* 1 出現在第`p + i`個 bit 中 ( 以 `bitmap` 的角度來看 )
* 將 出現 1 的編號 ( i.e. `p + i` ) 紀錄於 陣列`out`
* 可推理出 ==`pos` 代表 `bitmap` 中，出現 1 的個數==
> array 由 0 起算；人類 由 1 起算
> 因此，需要 `pos++`
#### `__builtin_ctzll` 改進版 :
```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; // KKK = bitset & -bitset
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
:::info
[GCC 提供對應的內建函式](http://sunmoon-template.blogspot.com/2017/04/gcc-built-in-functions-for-binary-gcc.html):
* **`builtin_ctzll (unsigned long long)`**
* 返回右起第一個 1 之後的 0 的個數
:::
* 程式碼解析：
```cpp
#08 while (bitset != 0){
```
* 第一個改良：若 `bitset` 之中沒有 1 ( i.e. 全為 0 )，則不用進行檢查，可直接進入下一組
```cpp
#10 int r = __builtin_ctzll(bitset);
#11 out[pos++] = k * 64 + r;
```
* `#10`、`#11` 可將 `bitmap` 中出現 1 的 bit 所在 index 紀錄於陣列 `out` 中
```cpp
#09 uint64_t t = KKK;
#12 bitset ^= t;
```
* 觀察程式碼，我們猜測 `#12` 可將 ==`bitset` 中 最低位的 1 換成 0==，如此一來，下個 while 迴圈才能正確執行
> 以 8 bits 為例
* 假設 `bitset` = ( **** *==1==00 )
* `t` 應為 ( 0000 0==1==00 )
* `-bitset` = ( $\bar*$$\bar*$$\bar*$$\bar*$ $\bar*$ ==1==00 ) `// 2's complement`
* 故，`t` = **KKK = `bitset & -bitset`**
## Q5. 進階題
#### 舉出 Q5 用在哪些真實案例中
#### 檢驗 clz 改寫的程式碼相較原本的實作有多少改進
>應考慮到不同的 [bitmap density](http://www.vki.com/2013/Support/docs/vgltools-3.html)
#### 思考進一步的改進空間
Sign in with Wallet
Connect another wallet