---
tags: linux2023-homework2
---

> [Linux 核心設計/實作 (Spring 2023)](http://wiki.csie.ncku.edu.tw/linux/schedule)

## 作業要求
> [2023q1 Homework2 (作業區)](https://hackmd.io/@sysprog/linux2023-homework2)
> [L03: quiz2](https://hackmd.io/@sysprog/H143OpNCo)
- [ ] 回答第 2 周測驗題從測驗一到測驗四 (採用 2 月 23 日晚間定案的題目)，附帶的「延伸問題」也需要完成
- [ ] 解釋程式運作原理時，應提供對應的 [Graphviz](https://graphviz.org/) 圖例，可參照 [Linked List 題目 1 + 分析](https://hackmd.io/@sysprog/linked-list-quiz)
- [ ] 比照 [課前測驗參考解答: Q1](https://hackmd.io/@sysprog/bitwise-reverse?type=view), [Linked list 題目分析](https://hackmd.io/@LinYunWen/HyELy5bTz?type=view) 和 [參考題解](https://hackmd.io/@RinHizakura/BysgszHNw) 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及進行相關實驗。

## 測驗 `1`
參照 [你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise) ，考慮 `next_pow2` 可針對給定無號 $64$ 位元數值 $x$ ，找出最接近且大於等於 $2$ 的冪的值，例如:
* `next_pow2(7)` = 8
* `next_pow2(13)` = 16
* `next_pow2(42)` = 64
### 運作原理
* 在二進位中，每個位元皆可各自表示為 $2$ 的冪之值 (e.g. `0001` = $2^{0}$, `0010` = $2^{1}$, `0100` = $2^{2}$, `1000` = $2^{3}$) 。
* 利用 bitwise 操作，將原本數值 `x` 中，從最高位元的 $1$ 至最低位元中的每個位元皆設定為 $1$ (e.g. `00001101` -> `00001111` ) 。
* 設定最高位元至最低位元為 $1$ 後再加 $1$ ，即可進位為 $2$ 的冪的值 (e.g. `00001111 + 1` = `00010000` = $2^{4}$) 。

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;  // AAAA = 8
    x |= x >> 16;
    x |= x >> 32;  // BBBB = 32
    return x + 1;  // CCCC = x + 1
}

### 延伸問題

## 測驗 `2`
LeetCode [1680. Concatenation of Consecutive Binary Numbers](https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/) 給定一整數 $n$ ，回傳將 $1$ 到 $n$ 的二進位表示法依序串接在一起所得到的二進位字串，其所代表的十進位數字 $mod$ $10^{9}$ + $7$ 之值。
* Example $2$ :

Input: n = 3
Output: 27

Explanation of solution:
i            !(i & (i - 1))        len          ans
1 ->  1             1               1             1
2 -> 10             1               2          1 10
3 -> 11             0               2       1 10 11  = 27(dec)

### 運作原理
* 每一個 $2$ 的冪之值，各自可作為二進位表示法中的最小 bit length 之值 (e.g. `100` 為 $len$ = $3$ 最小值， `111` 為 $len$ = $3$ 最大值) 。
* 因為要與上一個連續 Binary Number 串接前，需考慮到目前 Binary Number 的預留位元長度。所以判斷要串接的 Binary Number 之位元長度時，只需考慮到最小 bit length 之值，以此來決定位元長度 `len` 之值。
* 對照上述 Example $2$ ， `if(!(DDDD))` 為判斷是否為 $2$ 的冪之值 (位元長度 = `i` 的最小值) 。
* `(i | (EEEE))` 則為左移預留長度，並與上一個連續 Binary Number 進行 bitwise 串接。

int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    int len = 0;
    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 (!(i & (i - 1)))  // DDDD = i & (i - 1)
            len++;
        ans = (i | (ans << len)) % M;  // EEEE = ans << len
    }
    return ans;
}

### 延伸問題

## 測驗 `3`
UTF-8 字元可由 $1$, $2$, $3$, $4$ 個位元組構成。其中單一位元組的 UTF-8 由 ASCII 字元構成，其 MSB 必為 `0`。
UTF-8 的多位元組字元是由一個首位元組和 $1$, $2$ 或 $3$ 個後續位元組 (continuation byte(s)) 所構成。後續位元組的最高 $2$ 個位元會設定為 `10` 。
| ASCII | 0xxx.xxxx |
| -------- | -------- |
| 2 bytes | 110x.xxxx 10xx.xxxx |
| 3 bytes | 1110.xxxx 10xx.xxxx 10xx.xxxx |
| 4 bytes | 1111.0xxx 10xx.xxxx 10xx.xxxx 10xx.xxxx |

若輸入的字串是一個有效的 UTF-8 序列，則計算其中的後續位元組數量，並將此數字從總字串長度中減去，即可確定字元數量。
### 運作原理
* 逐行拆解程式碼，將原本傳入並佔用一個 byte 的字串 `buf` ，轉換其型態成 unsigned integer type (64-bit)，並且佔用 $8$ 個 byte 。
* 從原本 `buf[0], buf[1], .. , buf[7]`的 $8$ 次處理，調整為 `qword[0]` 的 $1$ 次處理。意即讀取 `qword[0]` 同為一次讀取 `buf` 中 index 0~7 的陣列元素。並且將 `end` 指向 `qword[len >> 3]` 的位址。
* `for` 迴圈中輸入的 `t0` 一共包含 $8$ 個位元組，進行 `not bit6 and bit7` 操做，以 population count 指令來計算其中的後續位元組數量 **(不是 UTF-8 字元數量)**。
* `(1 << 3) * (len / 8)` 可得到 $8$ 的倍數，再減去 `count` 來得到 UTF-8 字元數量。
* 最後，若 `len` 不為 $8$ 的倍數，則以 `count_utf8` 來計算 `buf` 中的 UTF-8 字元個數。

size_t swar_count_utf8(const char *buf, size_t len)
{
    const uint64_t *qword = (const uint64_t *) buf;
    const uint64_t *end = qword + (len >> 3);

    size_t count = 0;
    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);
    }

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

    return count;
}

### 延伸問題

## 測驗 `4`
判定 $16$ 位元無號整數是否符合特定樣式 (pattern)

Valid pattern:
pattern: 8000 (32768)  ->  1000 0000 0000 0000
pattern: c000 (49152)  ->  1100 0000 0000 0000
pattern: e000 (57344)  ->  1110 0000 0000 0000
pattern: f000 (61440)  ->  1111 0000 0000 0000
pattern: f800 (63488)
pattern: fc00 (64512)
pattern: fe00 (65024)
pattern: ff00 (65280)   .
pattern: ff80 (65408)   .
pattern: ffc0 (65472)   .
pattern: ffe0 (65504)
pattern: fff0 (65520)
pattern: fff8 (65528)
pattern: fffc (65532)
pattern: fffe (65534)  ->  1111 1111 1111 1110
pattern: ffff (65535)  ->  1111 1111 1111 1111

### 運作原理
* 直觀解法可參照測驗說明的程式碼，從最高位元往低位元逐一檢查所有的 `1` 是否皆連續相鄰。
* 改寫測驗說明中的程式碼，以避免使用到迴圈。首先觀察 `(n ^ x) < FFFF` 的特性，exclusive or `^` 的邏輯運算，可透過 `(x ^ ~x)` 將二進位數字的所有位元設定為 $1$ 。
* 若把 `x` 作 $2$'s complement `(~x + 1)` ，之後再進行 exclusive or `^` 運算，得到的結果皆比原數少一個最低位的 $1$ (e.g. `11110000` vs `11100000`) ，並且皆小於原數。
* 反之，若不符合測驗中的特定樣式，則 `x` 作 $2$'s complement 之後，無法將最低位 $1$ 後的位元皆清零 (e.g. `~(11110100) + 1 = 00001100`) 。進行 exclusive or `^` 運算後，反而會大於原數 (連續相鄰的 `1` 皆被保留) 。

bool is_pattern(uint16_t x)
{
    const uint16_t n = ~x + 1;  // EEEE = ~x + 1
    return (n ^ x) < x;  // FFFF = x
}

### 延伸問題