# 2023q1 Homework2 (quiz2)
contributed by < [Huaxin](https://github.com/p96114175) >
## 測驗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;
}
```
### 原理解釋
目標:
該程式針對無號64位元數值 `x`，找出最接近且大於等於 2 的冪的值
核心想法:
找出 x 的最高位元的位置，把 `x` 位元到最低位元都設成 `1`，接著加 `1`，便能取得最高位元的下一個位元，再執行二進位轉成十進位便為答案
實際做法:
透過 `x |= x >> n` 完成， `n` 為我們的位移量，依序跑完63次位元後，便可完成最高位元至最低位元設成 `1` 的想法，之後再進位即可完成。
以 10 (二進位表示為 0..1010 )為例子=>
`x >> 1` 為 `0..0101` ，接著執行 ` x |= x >> 1;` 我們便可以得到 `0..1111` ，後續再將62次位元位移完成，但其實你可以發現後面62次位元位移其實是沒有必要的，因為我們已完成最高位至最低位設定為 `1` 的想法，之後再執行 `++x;` 便完成進位的操作。
改良後程式碼如下
```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 = 0010000000000000`，流程如下
```
x = 0010000000000000 # initial
x = 0011000000000000 # x |= x >> 1;
x = 0011110000000000 # x |= x >> 2;
x = 0011111111000000 # x |= x >> 4;
x = 0011111111111111 # x |= x >> 8;
x = 0011111111111111 # x |= x >> 16;
x = 0011111111111111 # x |= x >> 32;
x = 0011111111111111 # ++x;
```
### 使用 `__builtin_{clz,ctz,ffs}` 改寫
```c
uint64_t next_pow2_origin(uint64_t x)
{
int c = __builtin_clzl(x);
return 1 << (64 - c);
}
```
我們可使用`__builtin_clzl` 找出 `x` 最左邊的位元至 `x` 的最高位元前有多少個零，再藉由 `(64 - c)` 找出位移量，再配合 `1 << (64 - c);` 取得我們 2 的冪的位置，即為解答。
### 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？
### 延伸問題
1. 解釋上述程式碼原理，並用 [__builtin_clzl](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 改寫
> int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
int __builtin_clzl (unsigned long)
Similar to __builtin_clz, except the argument type is unsigned long.
2. 在 Linux 核心原始程式碼找出類似的使用案例並解釋
3. 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？
> 提示: 可執行 cc -O2 -std=c99 -S next_pow2.c 並觀察產生的 next_pow2.s 檔案，確認 bsrq 指令 (表示 “Bit Scan Reverse”)
## 測驗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;
}
```
該程式我們可以專注在以下程式碼
```c
for (int i = 1; i <= n; i++) {
if (!(i & (i - 1)))
len++;
ans = (i | (ans << len)) % M;
}
```
我們可以藉由 `if (!(i & (i - 1)))` 來幫助我們判斷 `i` 是不是 2 的冪次，進而決定 `len` 是否要進行累加。
例如 `i=4`:
我們可以得到 4 = 0100 ,3 = 0011 接著 0100 & 0011 得到 0000，再進行!(0000)，`if (!(4 & (4 - 1)))` 判斷結果為 `true`。
例如 `i=3`
我們可以得到 3 = 0011 ,2 = 0010 接著 0011 & 0010 得到 0010，再進行!(0010)，`if (!(3 & (3 - 1)))` 判斷結果為 `false`。
```c
ans = (i | (ans << len)) % M;
```
將上一個迭代結果 `ans` 往左位移 `len` 位元，再和 `i` 進行 `OR` 完成合併
### 延伸問題
1. 解釋上述程式碼運作原理
2. 嘗試使用 `__builtin_{clz,ctz,ffs}` 改寫，並改進 $mod 10^9 + 7$ 的運算
## 測驗3
### 原理解釋
該程式可用於判斷一個64位元整數xy的前32位和後32位是否都是奇數
```c
static uint64_t SWAR_ODD_MASK = (1L << 32) + 1;
bool both_odd_swar(uint64_t xy) {
return (xy & SWAR_ODD_MASK) == SWAR_ODD_MASK;
}
```
* 首先定義出一個 `SWAR_ODD_MASK` 64位元整數型別，值為二的32次方加1
* 函數 `both_odd_swar` 會接收一個無號64位元整數 `xy` 作為參數，然後使用 `&` 取xy的前32位和後32位，然後比較兩個32位的值是否都是奇數(最低位為 1 )，若都是奇數，則返回 `true`
下方程式的輸入字串是一個有效的 UTF-8 序列，則計算其中的後續位元組數量，並將此數字從總字串長度中減去，即可確定字元數量。
```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;
}
```
* 輸入一個指向 UTF-8 `char` 的指標 `buf` 和 `char` 的長度 `len` 。
* 先將 `buf` 轉換為 64 位元整數的指標 `qword`，並且計算出 `char` 中包含位元組的數量。
* 過程中會迭代 `qword`，每次處理 8 個 `Byte`(一個64位元整數)。
* 對 `qword` 進行位元取反，然後將結果和 `0x04040404040404040llu` 取 `&` ，得到一個64位元整數 `t2`，接著，程式將t2 和自身相加，得到一個新的64位元整數 `t3` 。
* `t0` 和 `t3` 做 `&` 得到 `t4`
* 使用 `__builtin_popcountll` 計算 `t4` 中包含 1 的位元數量(算出有多少位元組為 continuation bytes)，並將這個數量加到計數器count中。
* 當 for loop 不滿足 `qword != end` 便離開
* 最後從 `(1 << 3) * (len / 8)` 得到總位元組數量，再扣掉 continuation bytes 數量，得到字元總數
```c
count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;
```
接下來對剩下不足 8 的 bytes 處理，若 `(len & 7)` (len % 8)得到滿足，意味著有餘數，便使用 `count_utf8` 處理，若不滿足 `(len & 7)` 代表沒有不足 8 的 bytes。
### 延伸問題
1. 解釋上述程式碼運作原理，比較 SWAR 和原本的實作效能落差
2. 在 Linux 核心原始程式碼找出 UTF-8 和 Unicode 相關字串處理的程式碼，探討其原理，並指出可能的改進空間
## 測驗4
### 原理解釋
該程式碼可判定 16 位元無號整數是否符合特定樣式 (pattern)。
```c
for (; x > 0; x <<= 1) {
if (!(x & 0x8000))
return false;
}
```
每次迭代只要 `x>0` 被滿足，便會執行 `if (!(x & 0x8000))` 判斷，若你的`x` 的最高位元為 `0` 便可以離開迴圈。若最高位元不是 `0` ， 則會將 `x` 左移 1 位元。
改寫上述程式碼，使其達到等價行為，但更精簡有效。
```c
bool is_pattern(uint16_t x)
{
const uint16_t n = ~x + 1;
return (n ^ x) < x;
}
```
對 `x` 取二補數，得到 `n`，接著 `n` 和 `x` 進行 `XOR`，如果小於 `x` 便返回 `true`，若大於 `x` 便返回 `false`。
假設我們輸入 `x = 1111000000000000` ，這是符合樣式的，那我們進行以下流程
```
x = 1111000000000000 #step1
~x = 0000111111111111 #step2
~x+1 = 0001000000000000 #step3
n = 0001000000000000 #step4
n^x = 1110000000000000 #step5
n^x < x 返回 true #step6
```
最後得到結果是 `true`
若輸入個不符合樣式的， `x = 1001000000000000` ，讓我們進行以下流程
```
x = 1001000000000000 #step1
~x = 0110111111111111 #step2
~x+1 = 0111000000000000 #step3
n = 0111000000000000 #step4
n^x = 1110000000000000 #step5
n^x < x 返回 false #step6
```
最後得到結果是 `false`
### 延伸問題
1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇
Sign in with Wallet
Connect another wallet