# 2023q1 Homework2 (quiz2)
contributed by < terry23304 >
## 測驗 1
### 運作原理
```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 >> 8;
x |= x >> 16;
x |= x >> 32;
return x + 1;
}
```
2 的冪次方除了最高位的 1 其餘都是 0
把最高位的 1 右邊的 bit 都設為 1，最後加一就可以得到 next_pow
### 用 __builtin_clzl 改寫
unsinged long 跟 uint64_t 等價
`__builtin_clzl(x)` 會回傳最高位的 1 前面有幾個 0 ，減去總長 64 bit 就可以得到要位移的個數
```c
uint64_t new_next_pow2(uint64_t x)
{
if (!x)
return 1;
int n = 64 - __builtin_clzl(x);
return 1 << n;
}
```
### 在 Linux 核心原始程式碼找出類似的使用案例並解釋
參考 [kfifo.c](https://github.com/torvalds/linux/blob/master/lib/kfifo.c)使用 `roundup_pow_of_two` 來保證 `size` 是二的冪次方， `size` 是 circular buffer 的大小，當 `size` 是二的冪次方時可以使用位元運算代替除法跟模數的運算，可以提高 index 計算的效率。
```c
int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,
size_t esize, gfp_t gfp_mask)
{
/*
* round up to the next power of 2, since our 'let the indices
* wrap' technique works only in this case.
*/
size = roundup_pow_of_two(size);
fifo->in = 0;
fifo->out = 0;
fifo->esize = esize;
if (size < 2) {
fifo->data = NULL;
fifo->mask = 0;
return -EINVAL;
}
fifo->data = kmalloc_array(esize, size, gfp_mask);
if (!fifo->data) {
fifo->mask = 0;
return -ENOMEM;
}
fifo->mask = size - 1;
return 0;
}
```
### 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？
可以發現編譯器有產生 `bsrq` 指令
```
new_next_pow2:
.LFB14:
.cfi_startproc
endbr64
bsrq %rdi, %rdi
movl $64, %ecx
movl $1, %eax
xorq $63, %rdi
subl %edi, %ecx
sall %cl, %eax
cltq
ret
.cfi_endproc
```
## 測驗 2
### 運作原理
目標: 把 1~n 的十進位轉為二進位，再串接再一起，求出十進位值
`len` 紀錄要左移的位元數
用 `!(i & (i-1))` 檢查 `i` 使否為 2 的冪次方
若 `i` 不是 2 的冪次方則 `len` 不變，因為此時 `i` 的二進位表示法中有多個 1。如果 `i` 是 2 的冪次方，則 `len` 加 1，因為此時 `i` 的二進位表示法中只有一個 1，且其位置在前面，必須左移更多位元才能將其串接起來。
當前結果與前面迴圈結果左移做 logical or 再 mod M 避免溢位
`ans = (i | (ans << len)) % M;`
### 嘗試使用 \_\_builtin_{clz,ctz,ffs} 改寫，並改進 mod $10^9 + 7$ 的運算
- 檢查 `i` 使否為 2 的冪次方
把 `if (!(i & (i-1)))` 改成 `if ((__builtin_clz(i) + __builtin_ctz(i)) == 31)`
代表 32 位元中只有一位是 1
`len++` 可改成 `len = __builtin_ffs(i);` 得到 `i` 的 leading 1 位置
原本為在 2 的冪次的時候 `len++` ，但改用 `__builtin_ffs(i)` 更新 `len`，只有在 2 的冪次方的時候 `len` 才會改變，所以就不用檢查 `i` 是否為 2 的冪次方
```c
for (int i = 1; i <= n; i++) {
len = __builtin_ffs(i);
ans = (i | (ans << len)) % M;
}
```
- 也可用 `if(__builtin_popcount(i) == 1)`
`__builtin_popcount(i)` 會回傳 `i` 中有幾個 bit 是 1
Built-in Function: int __builtin_ffs (int x)
從最低位開始的第一個 1 的位置。如果 x 是 0，則返回 0。
## 測驗 3
### 運作原理
在 UTF-8 編碼中，如果一個字節的最高位是 0，那這個字節所表示的就是 ASCII 字符；如果最高位是 1，那麼它所表示的就是一個多字節序列的開始字節。對於多字節序列的開始字節，最高位的 1 的數量表示了這個序列所包含的字節數量，例如，最高位有 2 個 1 的字節表示的是一個由 2 個字節組成的序列。
`if (p[i] > -65)`可用來判斷一個字節是否是一個多字節序列的開始字節
使用 SWAR 對 64 位數進行運算來加速計算
將 UTF-8 字符串分成若干個 64 位整數，然後對每個整數進行位運算，最後統計所有 64 位整數中表示字符的位數之和，得到最終的字符數量。
計算 buf 總共有幾個 8 byte
```c
const uint64_t *qword = (const uint64_t *) buf;
const uint64_t *end = qword + len >> 3;
```
每次遍歷 8 byte，用以下操作來找到有幾個 10 開頭的 byte
```c
for (; qword != end; qword++) {
const uint64_t t0 = *qword;
const uint64_t t1 = ~t0;
const uint64_t t2 = t1 & 0x04040404040404040llu;
const uint64_t t3 = t2 + t2;
const uint64_t t4 = t0 & t3;
count += __builtin_popcountll(t4);
}
```
上一步操作只處理了整數部分，還要處理不能被 8 整除的部分。
首先計算整數部分中表示字符的位的總數，然後將未處理的字節按照原來的方法進行計算，最後將結果加總起來得到最終的字符數量
```c
count = (1 << 3) * (len / 8) - count;
count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;
```
## 測驗 4
### 運作原理
要判斷的 pattern 是若有出現 1 則必須從 MSB 開始，且中間不可有0
```c
bool is_pattern(uint16_t x)
{
const uint16_t n = -x;
return (n ^ x) < x;
}
```
```
x: 1101000
-x: 0011000 // 把1跟1之間的0變成1，保留最後的1
-x^x: 1110000 // 把1跟1之間的0變成1，就會大於原本的x
```
### 在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇
Sign in with Wallet
Connect another wallet