2023q1 Homework2 (quiz2)

contributed by < KHLee529 >

測驗問題

實驗環境

$gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$lscpu
Architecture:            x86_64
CPU op-mode(s):          32-bit, 64-bit
Byte Order:              Little Endian
Address sizes:           39 bits physical, 48 bits virtual
CPU(s):                  8
On-line CPU(s) list:     0-7
Thread(s) per core:      2
Core(s) per socket:      4
Socket(s):               1
NUMA node(s):            1
Vendor ID:               GenuineIntel
CPU family:              6
Model:                   94
Model name:              Intel(R) Core(TM) i7-6770HQ CPU @ 2.60GHz
Stepping:                3
CPU max MHz:             3500.0000
CPU min MHz:             800.0000
BogoMIPS:                5199.98
Virtualization:          VT-x
L1d cache:               128 KiB 
L1i cache:               128 KiB 
L2 cache:                1 MiB 
L3 cache:                6 MiB 
NUMA node0 CPU(s):       0-7

測驗 1

程式運作原理

最初的的程式是透過類似二分搜尋法的方式，使得 hi 與 lo 逐漸收斂至一個特定值，代表相對應的二的冪。
而透過填補位元的概念計算 next_pow2 的方式為，從 MSB 開始計算開頭的 0 的數量，在最後一個 0 的位置改為 1 後接下來的位元皆設定為 0 便是 next_pow2 的結果。以題目中的例子

• $7_{10}={00000111}_2\to \text{next\_pow}2(7)={00001000}_2=8_{10}$
• ${13}_{10}={00001101}_2\to \text{next\_pow}2(13)={00010000}_2={16}_{10}$
• ${42}_{10}={00101010}_2\to \text{next\_pow}2(42)={01000000}_2={64}_{10}$

因此，不存在分支的程式填補的概念便是透過從在位元移動的過程中，將從第一個非零位元以後的位元全部填補為 1 的技巧，之後再將結果加上 1 時便可以得到下一個 2 的冪。

故在程式碼當中的前 7 個先將最前面的 7 個位元設定為 1 後，可以透過一次移動 8 位元、16 位元、32 位元的方式依序加速。事實上，前面的 7 個位元設定亦可以調整為 1, 2, 4 三次移動。改寫如下

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;
}

而若是使用用於資料當中計算開頭 0 (leading zeros) 的數量的 __builtin_clzl 函數，首先計算開頭的 0 的數量 (令為

$n_{\text{lz}}$，之後便可以直接透過

$2^{(64-n_{\text{lz}})}$ 計算出下一個 2 的冪數值。改寫如下

#include <stdint.h>
static inline uint64_t pow2(uint8_t e) { return ((uint64_t)1) << e; }

uint64_t next_pow2(uint64_t x)
{
    int nlz = __builtin_clzl(x);
    return pow2(64 - nlz);
}

透過此函數以編譯器參數 gcc -O2 -S 編譯得到的組合語言結果如下所示。可以看到當中確實出現了相對應的 x86 bsrq 指令，透過硬體提供的功能進行計算。

next_pow2:
.LFB51:
	.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

程式運作原理

此程式首先運用到線性運算後餘數仍保持不變的性質，如下所示。

$$(na+b\mathrm{mod}M)=(n\times (a\mathrm{mod}M)+(b\mathrm{mod}M))\mathrm{mod}M$$

由於位元相接可以視為

$\text{ans}\times 2^{\text{len}}+i$ 為一個對於 ans 的線性運算，因此可以在位元相接的過程中先計算

$\mathrm{mod}{10}^9+7$ 而不會改變結果。

其中位元相接的過程可以分為「左移必要位元數」與「對兩值進行位元或運算」，其中需要左移的位元數會隨著 2 的冪進行變化，每遇到一次 2 的冪，皆需要增加一個左移位數。如下，有箭頭的數字皆是所需位元多一位的時機。

• $1_{10}=1_2\leftarrow$
• $2_{10}={10}_2\leftarrow$
• $3_{10}={11}_2$
• $4_{10}={100}_2\leftarrow$
• $5_{10}={101}_2$
• $6_{10}={110}_2$
• $7_{10}={111}_2$
• $8_{10}={1000}_2\leftarrow$

而要判斷 2 的冪的方式可以透過 位元運算 i & (i-1) 進行，由於 2 的冪在減一後皆會退後一個位元，因此對兩數進行位元且運算時皆會為 0，可以透過此性質進行判斷。
最後只需要在迭代過程當中每一個答案左移後加上下一個值便可求得相應的結果。

測驗 3

程式運作原理

在 SWAR 的實作當中，透過批次處理 8 個位元組以減少迭代次數並計算其中 [10xx.xxxx] 位元組的數目

$n_{\text{continuation}}$，接著將整個長度減去

$n_{continuation}$ 後便可以得到對應的 UTF-8 字元數。

而程式首先將輸入的字元陣列轉換為 uint64_t 的資料型態確保其得以進行相關位元運算。接著由於一個 uint64_t 包含 8 個位元組，可以同時處理 8 個位元組的資料，透過題幹當中的 not bit6 and bit7 的方式達到計算 [10xx.xxxx] 位元組的數目。
此時由於當輸入長度並非 8 的倍數時，會有最後的剩餘數個位元組需要進行相關計算，因此在運用以上技巧計算完 [10xx.xxxx] 的位元組數量後，將「以處理的位元數量」減去計算得到的數量，最後透過簡單迭代函式 count_utf8 對於剩餘未處理的位元組 (

$<8$ 個) 進行計算，再將計算結果相加便完成本次計算。

測驗 4

欲匹配樣式

測驗中提到的「樣式」為「從第一個位元開始僅包含連續的 1」，即從 MSB 開始數第 0 個位元到第

$n$ 個位元 (

$n\le 15$) 皆為 1 且變為 0 後沒有其他為 1 的位元，即以下列出的數字。

0x8000 = [1000.0000|0000.0000]
0xc000 = [1100.0000|0000.0000]
0xe000 = [1110.0000|0000.0000]
0xf000 = [1111.0000|0000.0000]
0xf800 = [1111.1000|0000.0000]
0xfc00 = [1111.1100|0000.0000]
0xfe00 = [1111.1110|0000.0000]
0xff00 = [1111.1111|0000.0000]
0xff80 = [1111.1111|1000.0000]
0xffc0 = [1111.1111|1100.0000]
0xffe0 = [1111.1111|1110.0000]
0xfff0 = [1111.1111|1111.0000]
0xfff8 = [1111.1111|1111.1000]
0xfffc = [1111.1111|1111.1100]
0xfffe = [1111.1111|1111.1110]
0xffff = [1111.1111|1111.1111]

程式運作原理

對 x 取負號 (-x) 在位元表示方式中可以以 ~x + 1 代替，也就是「從 LSB 開始遇到的第一個 1 保留後剩餘所有位元進行反轉」，範例如下，標記有 ^ 符號的位置便是第一個遇到的 1。

|   x|00000001|00110000|11000010|11100000|
|  -x|11111111|11010000|00111110|00100000|
             ^    ^           ^    ^      

因此，若計算 -x ^ x 便會得到「x 從 LSB 開始遇到的第一個 1 改為 0 剩餘皆是 1 」的結果。

|   x|00000001|00110000|11000010|11100000|
|-x^x|11111110|11100000|11111100|11000000|
             ^    ^           ^    ^      

而在這樣的結果下，原先是符合前面提到的「樣式」的數字，經過 -x ^ x 得到的結果便是清掉最靠近 LSB 的一個 1，會得到比原本的值還要小的數值。而若是其他數值，由於在最靠近 LSB 的 1 以上仍有其他原為 0 的位元會被改變為 1，因此會得到比元數值較大的值。由此便可以通過此一規則判斷是否符合上述的「樣式」