# 2023q1 Homework1 (quiz2)
contributed by `JoshuaLee032190`
### 測驗一
* 根據題目的名稱`next_pow2`，我們可以知道這個題目要找出當前整數的下一個2 的冪整數。
* 題目如下：
```c
uint64_t next_pow2(uint64_t x)
{
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> AAAA;
x |= x >> 16;
x |= x >> BBBB;
return CCCC;
}
```
* 要回答這個問題首先可以直接看 pattern，可以看到前面總共做了7次 `x |= x >> 1`，而且`AAAA`的下一行為 16，由此我們可以推測 `AAAA` 為 8
* `BBBB` 為 32
* `CCCC` 就要從前面想了，前面的意思為==把這個整數的某一個位元往右全部填滿 1==，那在全部都是1的狀況，我們只需要 `+ 1` 即可得出最終的結果
:::info
我覺得前面右移做了七次有點多此一舉，而測試後，其實可以把code 改成以下的狀況達到同樣的結果
```c
uint64_t next_pow2(uint64_t x)
{
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
return x + 1;
}
```
:::
### 延伸問題
#### 1. 解釋上述程式碼原理，並用 __builtin_clzl 改寫
```c
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.
int __builtin_clzl (unsigned long)
// Similar to __builtin_clz, except the argument type is unsigned long.
// 利用 __builtin_clzl 改寫完成
uint64_t next_pow2_2(uint64_t x)
{
int hi = __builtin_clzl(x >> 32);
int lo = __builtin_clzl(x);
uint64_t res = 1;
return (hi == 31) ? res << 31 - lo + 1 : res << 64 - hi;
}
```
>
#### 2. 在 Linux 核心原始程式碼找出類似的使用案例並解釋
* 我先使用 `grep -r "roundup" *` 找出了 pci.h
```c
# /include/linux/pci.h
static inline int pci_rebar_bytes_to_size(u64 bytes)
{
bytes = roundup_pow_of_two(bytes);
/* Return BAR size as defined in the resizable BAR specification */
return max(ilog2(bytes), 20) - 20;
}
```
* 這段程式碼主要是為了要初始化及配置空間，其中`20`的數字代表了 1mb 的大小所以先取 `max`
* 可以想像，回傳值是一個大於等於0的常數，如果回傳值為0，那就代表PCI只需要配置1MB的空間，反之，以回傳值來判斷需要多配置多少空間
#### 3. 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？
> 提示: 可執行 gcc -O2 -std=c99 -S next_pow2.c 並觀察產生的 > next_pow2.s 檔案，確認 bsrq 指令 (表示 “Bit Scan Reverse”)
* 有產生bsrq
```
next_pow2_2:
.LFB14:
.cfi_startproc
endbr64
shrq $32, %rdi
movl $64, %ecx
movl $1, %eax
bsrq %rdi, %rdi
xorq $63, %rdi
subl %edi, %ecx
salq %cl, %rax
ret
.cfi_endproc
```
## 測驗二
### 解釋題目
* 由題目敘述得知，這個 function 會回傳1~`輸入`，的二進位連接起來的數字
* 題目如下
```c
int concatenatedBinary(int n)
{
const int M = 1e9 + 7;
int len = 0; /* the bit length to be shifted */
/* use long here as it potentially could overflow for int */
long ans = 0;
for (int i = 1; i <= n; i++) {
/* removing the rightmost set bit
* e.g. 100100 -> 100000
* 000001 -> 000000
* 000000 -> 000000
* after removal, if it is 0, then it means it is power of 2
* as all power of 2 only contains 1 set bit
* if it is power of 2, we increase the bit length
*/
if (!(DDDD))
len++;
ans = (i | (EEEE)) % M;
}
return ans;
}
```
* 由題目內的參數名稱以及 `ans = (i | (EEEE)) & M`可知，`len` 為往左移動的距離
* 而只有在一種條件下 `len` 才會需要 `+ 1`，此情況為：
```python
# 考慮 1 - 10 的位元如下
1 : 0001
2 : 0010
3 : 0011
4 : 0100
5 : 0101
6 : 0110
7 : 0111
8 : 1000
9 : 1001
10: 1010
```
* 我們可以仔細觀察位元進位的時刻，狀況為前一個數字和當前的數字做 `AND` 運算得到 0 的狀況
* 所以 `DDDD` 很明顯就是 i & (i - 1)
* 而每次都需要更新當前的位元到 `ans` 中，可想而知 `EEEE` 為 `ans << len`，如此一來就可以把運算後的數字放入當前空下來的位元
### 使用__builtin 改寫
* __builtin_ffs : 用來找出 LSB 的位置 ==從右邊開始數的第一個bit==
* __builtin_clz : 用來找出 MSB 的位置 ==從左邊開始數的第一個bit==
* __builtin_ctz : 回傳從右邊開始數有幾個0
```c
int concatenatedBinary(int n)
{
const int M = 1e9 + 7;
int len = 0;
long ans = 0;
for (int i = 1; i <= n; i++) {
len = 32 - __builtin_clz(i);
ans = (i | (ans << len)) % M;
}
return ans;
}
```
## 測驗三
* 看不懂 待處理
## 測驗四
### 解釋程式碼
* `is_pattern` 主要是在看輸入的無號整數的編碼是否存在特定樣式
* 此特殊樣式為==從MSB開始往LSB存在連續1==
* 前面的function 可以看到在迴圈中x 總是跟 0x8000 也就是 `1000000000000000` 做and，當位元還沒有被清空時，只要中間的連續1斷開則回傳`false`
> 後面的function 則是找出這個pattern 會發生的事情
```
# 我們來看一下這個 pattern (這個假設在 bit數為5的狀況)
10000
11000
11100
11110
11111
首先，題目很明顯告訴你有一個 xor 跟比大小；也就是我們必須往比大小的方向思考
那要怎麼樣才可以利用這個 pattern 比大小呢？
我們只需要先取 x 的負數，如此一來可以得到
10000 ==> 10000
11000 ==> 01000
11100 ==> 00100
11110 ==> 00010
11111 ==> 00001
此時 x ^ -x 就會變成
00000
10000
11000
11100
11110
最後再與原本的狀況比大小，此時，如果符合這個 pattern 的話，結果一定會比原本的輸入還要小，此時只要比大小，回傳即可。
```
`EEEE` 為 `-x`
`FFFF` 為 `x`
### 在 linux kernel 中找此 bitmask
* 待處理
Sign in with Wallet
Connect another wallet