---
# System prepended metadata

title: 2023q1 Homework2 (quiz2)

---



# 2023q1 Homework2 (quiz2)

contributed by < [ctc2324](https://github.com/ctc2324) >

## 測驗 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 >> 1;
    x |= x >> 16;
    x |= x >> 32;
    return (x+1);
}
```
### 延伸問題
1. 解釋上述程式碼原理，並用 `__builtin_clzl` 改寫
1. 在 Linux 核心原始程式碼找出類似的使用案例並解釋
1. 當上述 `clz` 內建函式已運用時，編譯器能否產生對應的 `x86` 指令？

#### 1. 解釋上述程式碼原理，並用 `__builtin_clzl` 改寫
##### 程式碼原理

以上程式目標為針對給定的無號64位元數值 `x` ，找出最接近且大於等於 `2` 的冪的值。
因此我們只要將此數最大位元之後的位元全數填滿 `1` ，再將最後 `return` 值加上1，就可以得到最接近 `x` 的冪值。
此程式透過將 `x` 位元移動，並與 `x` 做 OR 運算，來將後面位元填滿 1 。
因此可以知道在64位元的清況下，最多只需要操作63次即可達成。已知每次操作都會以 2 的倍數成長，因此可以將程式碼優化為：
```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);
}
```
也可以達成一樣的效果。

以下舉例 `x` 為 `0x30000000` ，其在二進位表示下為 `0011 0000 0000 0000 0000 0000 0000 0000`
```c
uint64_t next_pow2(uint64_t x)
{
    // x = 0011 0000 0000 0000 0000 0000 0000 0000
    x |= x >> 1;  // x = 0011 1100 0000 0000 0000 0000 0000 0000
    x |= x >> 2;  // x = 0011 1111 0000 0000 0000 0000 0000 0000
    x |= x >> 4;  // x = 0011 1111 1111 0000 0000 0000 0000 0000
    x |= x >> 8;  // x = 0011 1111 1111 1111 1111 0000 0000 0000
    x |= x >> 16; // x = 0011 1111 1111 1111 1111 1111 1111 1111
    x |= x >> 32; // x = 0011 1111 1111 1111 1111 1111 1111 1111
    return (x+1); // x = 0100 0000 0000 0000 0000 0000 0000 0000
}
```
輸出為 `0100 0000 0000 0000 0000 0000 0000 0000` 即十進位的 `1073741824`。

##### 用 `__builtin_clzl` 改寫
`__builtin_clzl` 函式定義為傳回輸入數 `x` 最高位開始連續的 0 的個數。以上面的 `0x30000000` 為例：
:::info
x = 0011 0000 0000 0000 0000 0000 0000 0000
最高位數字為從左邊數來的第35位元，因此 `__builtin_clzl` 函式會回傳34，表示在最高位元左邊有連續34個0。
:::

了解 `__builtin_clzl` 函式的作用後，我們便可以將程式改寫成：
```c
uint64_t next_pow2(uint64_t x)
{
    if(x==0)
        return 1;
    
    int clz;
    clz = __builtin_clzl(x);
    
    return 1 << (64-clz);
}
```
此處須注意在 `__builtin_clzl` 中提及若傳入值為 0 是未定義的情況，因此若傳入值為 0 則直接回傳 1 。
#### 3.當上述 `clz` 內建函式已運用時，編譯器能否產生對應的 `x86` 指令？

在linux系統編輯 `test.c` 透過gcc確定可編譯後，執行 `cc -O2 -std=c99 -S test.c` ，此時會產生出test.s檔，打開便可看到對應的 x86 指令如下：
```
next_pow2:
.LFB13:
	.cfi_startproc
	endbr64
	movl	$1, %eax
	testq	%rdi, %rdi
	je	.L1
	bsrq	%rdi, %rdi
	movl	$64, %ecx
	xorq	$63, %rdi
	subl	%edi, %ecx
	sall	%cl, %eax
	cltq
```

:::warning
1. 在 Linux 核心原始程式碼找出類似的使用案例並解釋
:::


## 測驗 2
### 題目程式碼
```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 (!(i & (i-1)))
            len++;
        ans = (i | (ans << len)) % M;
    }
    return ans;
}
```
### 延伸問題
1. 解釋上述程式碼運作原理
1. 嘗試使用 `__builtin_{clz,ctz,ffs}` 改寫，並改進 mod $10^9+7$ 的運算


#### 1.解釋上述程式碼運作原理

本程式碼目標為給定一整數 $n$ ，回傳將 1 到 $n$ 的二進位表示法依序串接在一起所得到的二進位字串，其所代表的十進位數字 mod $10^9+7$ 之值。

使用 `len` 紀錄數字的長度，由於若遇到 2 的冪值，2進位的數字長度會加 1 ，因此此處判斷 `i` 及 `i-1` 經過 `AND` 運算的值是否等於0。例如：

:::info
該數非2的冪值：
5 -> 0101
4 -> 0100
`AND`運算後為0100 並非為0，則 5 非 2 的冪值。

該數為2的冪值：
4 -> 0100
4 -> 0011
`AND`運算後為0000 為0，則 4 為 2 的冪值。
:::

因此若是 `AND` 運算後為0，此數即為 2 的冪值，將 `len` 值+1。
最後再將 `ans` 向左位移 `len` 數的位元並與 `i` 做 `OR` 運算，實現將數字的二進位串接在一起的功能。每次進行 `OR` 運算後再mod $10^9+7$。最後回傳 `ans` 值。

#### 2.嘗試使用 `__builtin_{clz,ctz,ffs}` 改寫，並改進 mod $10^9+7$ 的運算
```c
int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    int len = 0; 
    long ans = 0;
    for (int i = 1; i <= n; i++) {
        
        len = 64 - __builtin_clzl(i);
        ans = (i | (ans << len)) % M;
    }
    return ans;
}
```
使用第一題使用過的 `__builtin_clzl` 函式來獲得輸入值 `n` 的二進位最高位元位置，代表整串二進位長度，其他與題目程式碼無異。
:::warning
改進 mod $10^9+7$ 的運算
:::

## 測驗 3
### 題目程式碼
```c
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;
}
```


### 延伸問題
1. 解釋上述程式碼運作原理，比較 SWAR 和原本的實作效能落差
1. 在 Linux 核心原始程式碼找出 UTF-8 和 Unicode 相關字串處理的程式碼，探討其原理，並指出可能的改進空間

#### 1.解釋上述程式碼運作原理，比較 SWAR 和原本的實作效能落差
本程式透過 SWAR 技巧來計算輸入一 UTF-8 字串中的Unicode數量。


首先將傳入的 `buf` 轉換成 `uint64_t` 的形式，並且設變數 `end` 指向 64 bits 中的最後一位數，以便接下來的迴圈有終止點。

接下來設定迴圈，一次8個 bytes 來做檢查。目標為找出最高2個位元設定為 `10` 的**後續位元組**。
```c
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);
    }
```

1.此處與原題目相同，假設 `t0` 為：
```c
t0 = [00xx.xxxx|01xx.xxxx|10xx.xxxx|11xx.xxxx]
                          ^^^^^^^^^
                     *continuation bytes*
```

2.反轉位元：
```c
t1 = ~t0;

t0 = [00xx.xxxx|01xx.xxxx|10xx.xxxx|11xx.xxxx]
t1 = [11xx.xxxx|10xx.xxxx|01xx.xxxx|00xx.xxxx]
```
3.透過與 0x40404040 進行 `AND` 運算來隔離反向的第六個位元。
```c
t2 = t1 & 0x40404040;

t2 = [0100.0000|0000.0000|0100.0000|0000.0000]
```

4.對第 6 個位元，向左位移 1 個位元 (移至第 7 個位元的位置)
```c
t3 = t2 +t2;

t3 = [1000.0000|0000.0000|1000.0000|0000.0000]
```
5.進行 `not bit6 and bit7`
```c
t4 = t0 & t3;

t4 = [0000.0000|0000.0000|1000.0000|0000.0000]
```
此時可以發現，只剩下第三個位元組有數字。

6.使用函式 `__builtin_popcountll` 來計算1的數量。
```c
count += __builtin_popcountll(t4);

count = 1; 
```
此時計數器 count 即為後續位元組的數量。





## 測驗 4
### 題目程式碼
```c
bool is_pattern(uint16_t x)
{
    const uint16_t n = -x;
    return (n ^ x) < x;
}
```
### 延伸問題
1. 解釋上述程式碼運作原理
1. 在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇

#### 1.解釋上述程式碼運作原理
此程式碼目標為判別目標數在二進位下是否符合某些條件。
```c
#include <stdint.h>
#include <stdbool.h>

bool is_pattern(uint16_t x)
{
    if (!x)
        return 0;

    for (; x > 0; x <<= 1) {
        if (!(x & 0x8000))
            return false;
    }

    return true;
}
```
從題目第一個程式碼中可以推測出，條件為判斷此二進位是否符合 "從LSB 到RSB 中間是否都為 1"
舉例來說：

:::info
十六進位 -> 二進位

符合：
8000 -> 1000000000000000(從 LSB 至 RSB 皆為 1)
FFF0 -> 1111111111110000(從 LSB 至 RSB 皆為 1)

不符合：
8001 -> 1000000000000001
:::

因此精簡後的程式先設16位元變數 `n` 等於 `-x` ，也就是對 `x` 取負值，並且透過與原 `x` 進行 `XOR` 運算，若此數滿足以上條件，則其與原 `x` 做 `XOR` 運算其值必小於 `x` 。

舉例來說：
以 FFF0 (16進位)為例， `x = 1111111111110000` 取負號後即對二進位每個位元反轉後加一， `n = 0000000000010000` ，此數與原 `x` 進行 `XOR` 運算後為 `1111111111100000` ，此數比原本的 `x` 小，故 FFF0 為符合規定的數。

再舉 FFF1 (16進位)為例，`x = 1111111111110001` 取負號後即對二進位每個位元反轉後加一，`n = 0000000000001111` ，此數與原 `x` 進行 `XOR` 運算後為 `1111111111111110` ，此數比原本的 `x` 大，故 FFF1 為不符合規定的數。

#### 在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇


