# 2023q1 Homework2 (quiz2)
contributed by < `PlusThousand0107` >

## 實驗環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         4100.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4399.99

## 測驗 `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的冪的值

#### 作法 :
利用 `bitwise` 的技巧，讓 x 和右移後的 x 做 `or` 操作，此操作能將最高位的 `1` 之後的所有bit都設成 `1` ，這樣最後只要再做 `x + 1` 即可得到最接近且大於等於2的冪的值

#### 例子 :
以 `next_pow2(19)` = 32 為例
1. 首先，x = 19~(10)~ = 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 0011~(2)~
2. 進行 `x >> 1` 的操作後會得到 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1001~(2)~
3. 將兩數做 `or` 可得 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1011~(2)~，在這能觀察到在最高位的 `1` 後面中有本來是 `0` 的bit被設成 `1` 了
4. 再做一輪能發現到 x 變成 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111~(2)~，這時最高位的 `1` 後面已經全設成 `1` 了，只要再做 `x + 1` 就可得到 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0010 0000~(2)~ = 32~(10)~

### 用 `__builtin_clzl` 進行改寫
`__builtin_clzl` 可以返回從最高位到第一個 `1` 之前有幾個 `0` ，所以用 64 減去此值可知道需位移的量，最後再用 1 向左移此位移量的距離即可得到最接近且大於等於2的冪的值，程式碼如下

uint64_t new_next_pow2(uint64_t x)
{
    int shift = 64 - __builtin_clzl(x); 
    return (uint64_t)1 << shift;
}

#### 例子 :
以 `next_pow2(35)` = 64 為例
1. 首先，x = 35~(10)~ = 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0010 0011~(2)~
2. 對 x 做 `__builtin_clzl` 會得到 58 ，再用 64 減去 58 得到 6 並將此值設給 `shift`
3. 讓 `(uint64_t)1` 往左移 `shift` 個單位後即可得到 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0100 0000~(2)~ = 64~(10)~

## 測驗 `2`
### 解釋程式碼原理

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 (!((i & (i - 1)))
        len++;
    ans = (i | (ans << len)) % M;
}

#### 目的 :
給定一個整數n，將1到n的二進位表示串在一起合成一個二進位字串，將其轉乘十進位數後再 mod $10^9$ + 7

#### 作法 :
1. 先將 `M` 設為 `1e9 + 7` 以表示 $10^9$ + 7
2. 在 `for` 迴圈中會經過 1 到 n ，透過 `len` 紀錄整數 `i` 以二進位表示後的位元長度，在迴圈中還有一個判斷是用 `(i & (i - 1)` 的方式確認 `i` 是否為2的冪的值，如果是的話就 `len++`
- EX : x = 8~(10)~ = 1000~(2)~ ， x - 1 = 7~(10)~ = 0111~(2)~ ， x & (x - 1) = 1000 & 0111 = 0000
3. 最後，因為要把 `i` 串到 `ans` 後面，所以藉由之前以 `len` 記錄下的長度進行 `ans << len` 的位移，並將 mod 完 `M` 後的值傳給 `ans`

#### 例子 :
以 n = 5 為例
1. 從 1 開始，由於 1 是 2 的冪的值，所以 1 和 (1 - 1 = 0) 做 `and` 會得到 0 ，所以 `len` 會從 0 增加到 1 ，最後得到的 `ans` 為 1
2. 由於 2 也是 2 的冪的值，所以 `len` 會從 1 增加到 2 ，這代表目前的這個數的二進位表示法需用到的長度為 2 ，所以用 `ans << len` 將 1 位移成 100 後，再做 `or` 並 mod $10^9$ + 7 會得到 110 ，所以 `ans` 現在是 110
3. 而 3 不是 2 的冪的值，所以 `len` 不會增加，做 `ans << len` 後可得 11000 ，做完 `or` 再 mod $10^9$ + 7 會得到 11011
4. 因為 4 是 2 的冪的值，所以 `len` 會再從 2 增加到 3 ，做 `ans << len` 後會得到 11011000 ，最後的運算結果為 `ans` 是 11011100
5. 最後是 5 ，它不是 2 的冪的值，所以 `len` 維持不變，做 `ans << len` 後可得 11011100000 ，經過 `or` 和 mod $10^9$ + 7 的運算後得到 11011100101 ，再將這個結果回傳

## 測驗 `3`
### 解釋程式碼原理

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;
    count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;

    return count;
}

這裡參考到了 [Ahsen-lab](https://hackmd.io/@Ahsen-lab/linux2023_quiz2) 同學的講解
#### 目的 :
用 SWAR 的技巧，計算所給定的 UTF-8 字串中 Unicode的字元數量
#### 作法 :

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

- 首先先將 UTF-8 字串的 `buf` 用 `uint64_t` 型態的指標 `qword` 紀錄
- `end` 為 `qword` 的中止條件，這裡從 `qword` 開始算，後面還須加上 `len >> 3` ，意思為 `len / 8`

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` 紀錄位元組數量，並用迴圈的方式進行累加
- 在迴圈中會先用 `t0` 取得位元組， 再用 `t1` 紀錄做完反向運算的結果，之後會讓 `t1` 和 `0x4040404040404040` 做 `and` ，目的為隔離反向的第 6 個位元， `t3 = t2 + t2` 則是為了左移 1 位元，從第 6 位元移動到第 7 位元，之後的 `t4 = t0 & t3` 相當於在做 `not bit6 and bit7` ，最後再用 `__builtin_popcountll` 計算，並將結果累加給 `count`

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

return count;

- 從迴圈跳脫出來後，會讓 `len` 除 8 ，再用 `bitwise` 的方式乘 8 ，減去後續位元組的數量後即可得到 UTF-8 字元的數量
- 因為總位元組數不一定是 8 的倍數，所以這裡用 `len & 7` 的方式來做判斷，如果餘數大於 0 就用 `count_utf8` 處理剩餘的位元組，並將結果加到 `count` ，若餘數等於 0 則是將 0 加到 count

## 測驗 `4`
### 解釋程式碼原理

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

#### 目的 :
判定16位元無號整數是否符合特定樣式，根據給定的範例可發現樣式規定為「最高位必須為 `1` ，且到最低位的 `1` 之間的bit也必須都是 `1` 」，例子如下
- f000~(16)~ = 1111 0000 0000 0000~(2)~ => True
- f300~(16)~ = 1111 0011 0000 0000~(2)~ => False
- f800~(16)~ = 1111 1000 0000 0000~(2)~ => True

#### 作法 :
做 `~x + 1` 的目的是對 `x` 取二補數，而做 `(~x + 1) ^ x ` 則是想去掉最右邊的 `1` ，最後再做 `((~x + 1) ^ x) < x ` 以判別 `x` 是否符合樣式

#### 例子 :
1. 以 f800~(16)~ 為例
- x = f800~(16)~ = 1111 1000 0000 0000~(2)~ ， ~x + 1 = 0000 1000 0000 0000~(2)~ ， (~x + 1) ^ x = 1111 0000 0000 0000~(2)~ ， 又 1111 0000 0000 0000~(2)~ < 1111 1000 0000 0000~(2)~ ，故回傳 `True`
2. 以 f300~(16)~ 為例
- x = f300~(16)~ = 1111 0011 0000 0000~(2)~ ， ~x + 1 = 0000 1101 0000 0000~(2)~ ， (~x + 1) ^ x = 1111 1110 0000 0000~(2)~ ， 而 1111 1110 0000 0000~(2)~ > 1111 0011 0000 0000~(2)~ ，所以回傳 `False` ，表示不符合樣式