2023q1 Homework2 (quiz2)

contributed by < koty6069 >

2023q1 第 2 週測驗題

測驗 1

程式碼解析

原文有提到我們可改動原本數值 x ，從其原本有數值的最高位元至最低位元皆設成 1 。

最初 x 是 0010000000000000，經過一系列操作後，成為 0011111111111111，亦即設定 (set，即指派為 1) 自原本最高位元到最低位元中，所有的位元。

因此程式碼除了 return CCCC 以外，皆是在做設定為 1 的動作。
我們可以上面引文之數值 0010000000000000 進行操作，觀察其結果。

x |= x >> 1;    //0011000000000000
x |= x >> 1;    //0011100000000000
x |= x >> 1;    //0011110000000000
x |= x >> 1;    //0011111000000000
x |= x >> 1;    //0011111100000000
x |= x >> 1;    //0011111110000000
x |= x >> 1;    //0011111111000000

以上進行了七次 x |= x >> 1，將最高位的 1 其右方七個位元都設成 1 ，也就是目前從原先的最高位 1 開始有連續 8 個位元為 1 ，接下來可直接 shift 8 個位元，再將右方 8 個位元皆設成 1 ，後續再 shift 16 及 32 個位元，即可將全部 64 個位元皆覆蓋到，因此 AAAA 為 8 ， BBBB 為 32。

x |= x >> 8;
x |= x >> 16;
x |= x >> 32;

只要將上述連續的 1 再加上 1 即可得到 「最接近且大於等於的 2 的冪的值」，因此最後的 CCCC 為 x + 1 。

return x + 1;

使用 __builtin_clzl 改寫

__builtin_clzl 會回傳最高位的 1 之前 0 的數量，使用 64 減去此值會得到最高位的 1 所在位置，因此將 1 向左移動此數值（64 - shift）就能得到「最接近且大於等於的 2 的冪的值」。

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

當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？

可確認到 bsrq 指令。

next_pow2:
.LFB13:
    .cfi_startproc
    endbr64
    bsrq    %rdi, %rdi
    movl    $64, %ecx
    movl    $1, %eax
    xorq    $63, %rdi
    subl    %edi, %ecx
    salq    %cl, %rax
    ret 
    .cfi_endproc

測驗 2

程式碼解析

根據註解，每次迴圈會將最右方的 1 移除，若移除後數值為 0 ，代表此數為 2 的冪，此時需要將長度增加，原因是二進位制在遇到 2 的冪時會使得紀錄需要的位元數增加。

舉例來說，3 的二進位為 11 ，需要兩個位元作紀錄， 4 的二進位則為 100 需要三個位元。

因此 if 需要在移除 1 後數值為 0 的情況下將 len 增加，DDDD 為 i & (i - 1)，將 i 減一時會與最右方的 1 做借位，接著進行 & 操作會將剛剛操作後產生的 1 和原本最右方的 1 都消除，此時若數值為 0 則代表此數為 2 的冪。

if (!(i & (i - 1)))
    len++;

答案需要我們將二進制全部串接，每次迴圈需要將二進制的 i 串接到目前的答案尾端，因此我們需要將目前的答案向左 shift ，再透過 & 操作將 i 串接上去， EEEE 為 ans << len 。

ans = (i | (ans << len)) % M;

測驗 3

程式碼解析

由於後續使用迴圈一次處理 8 bytes （一個位元組），所以一開始先透過 len >> 3 （也就是 len / 8）來計算總共有多少位元組。

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

迴圈即是使用 SWAR 一次檢測一個位元組，也就是原文有解釋過的 not bit6 and bit7 操作，並使用 count 紀錄有幾個 byte 符合 10xx.xxxx 的形式（也就是有多少 continuation byte）。

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

得到 continuation byte 的數量後，根據原文說明，需要將此數量從總字串長度中減去。

若輸入的字串是一個有效的 UTF-8 序列，則計算其中的後續位元組數量，並將此數字從總字串長度中減去，即可確定字元數量。

這邊先計算整除 8 的部分長度為何，透過 (1 << 3) * (len / 8) 將最低位 3 bits 設為 0 ，得到長度後將其減去 count ，因此 AAAA 為 3。

count = (1 << 3) * (len / 8)  - count;

最後計算未滿 8 bytes 的部分中有多少 continuation byte ，並將其補上。

count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;

len & 7 可得知未滿 8 bytes 的長度為何，將此長度的字元使用 count_utf8 逐字元檢查是否為 continuation byte 並加回 count，因此 BBBB 和 CCCC 皆為 7 ，若剩餘的長度為 0 ，代表不須多做檢測，將 count 加上 0 即可，因此 DDDD 為 0 。

測驗 4

程式碼解析

原始程式碼中，每次會將 x 向左 shift 一位元，再與 0x8000 做 & ，用意是檢測當前的 MSB 是否為 1 ，若非 1 則不符合樣式，再對照下方提供的範例樣式，可得知要尋找的樣式為從 MSB 開始有連續位元為 1 的數。

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

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) => 1111 1000 0000 0000
pattern: fc00 (64512) => 1111 1100 0000 0000

後續的改進中，首先可以先觀察將 x 取 -x 也就是二補數後的結果，我們使用上面的範例來觀察。

 c000: 1100 0000 0000 0000
-c000: 0100 0000 0000 0000
==========================
 f800: 1111 1000 0000 0000
-f800: 0000 1000 0000 0000

可發現取 -x 後只會保留最右方的 1 ，這時與原數做 XOR 操作，會將原數值中最右的的 1 消除，因此符合樣式的值在 XOR 後應會比原數值小。

     1100 0000 0000 0000
^    0100 0000 0000 0000
-------------------------
     1000 0000 0000 0000

     1111 1000 0000 0000
^    0000 1000 0000 0000
-------------------------
     1111 0000 0000 0000

因此可推測答案 EEEE 為 -x ， FFFF 為 x 。

const uint16_t n = -x;
return (n ^ x) < x;

我們可再取一不符合樣式的值做檢測，會發現不符合樣式的值在 XOR 後會比原數大，因此會返回 false 符合上述推測。

 d000: 1101 0000 0000 0000
-d000: 0010 0000 0000 0001

     1101 0000 0000 0000
^    0010 0000 0000 0001
-------------------------
     1111 0000 0000 0001