# 2023q1 Homework2 (quiz2)
contributed by < terry23304 >

## 測驗 1

### 運作原理

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 就可以得到要位移的個數

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 計算的效率。

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 的冪次方

    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

const uint64_t *qword = (const uint64_t *) buf;
const uint64_t *end = qword + len >> 3;

每次遍歷 8 byte，用以下操作來找到有幾個 10 開頭的 byte

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 整除的部分。
首先計算整數部分中表示字符的位的總數，然後將未處理的字節按照原來的方法進行計算，最後將結果加總起來得到最終的字符數量

count = (1 << 3) * (len / 8)  - count;
count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;

## 測驗 4

### 運作原理
要判斷的 pattern 是若有出現 1 則必須從 MSB 開始，且中間不可有0

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 及產生器，探討應用範疇