2023q1 Homework2 (quiz2)

contributed by < zeddyuu >

測驗 1

解釋程式碼運作原理

給定一個值，要找下一個 2 的冪，要關注的只有最高位元的 1 在哪個位置，而他的下一高位位元就是答案，所以我們要把低於最高位元的 1 之後的位元都做 set 後加 1，會造成連續進位，最後將二進位轉為十進位即得到答案。

例如

$9_2$ 為

$0..01001$，要關注的位置就是最高位元的 1 出現在哪裡，即右邊數來第四位，而它的下一位元即是答案，對最高位元的 1 以下的位元做 set 操作得到

$0..01111$，再累加 1，得到

$0..10000$，轉成十進位即為答案 16。

所以將最高位元 1 以後的位元做 set 就是此題的重點，現在已知最高位元的 1，那將此值依序右移，最高位元的 1 就會跑到下個位元去，和右移前的值做 OR 就會將下個位元設為 1，直到之後的每個位元都跑過一次即完成操作，此題為 64 位元的 unsigned long long int，所以共要做最多 63 次位移能保證操作完成(最高位 1 在第 64 位元的時候)。

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

因為做完一次 OR 操作可以保證兩個位元變成 1，所以下一次就可以一次移動兩個位元，而下一次再做 OR 可以保證四個位元變成 1，所以下一次可以一次移動四個位元，以此類推，程式碼可以改寫成

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

故答案 `AAAA` : `8` `BBBB` : `32` `CCCC` : `++x`

不用列出作答用的標示及參考答案，你應該專注於程式碼及其原理。

jserv

好的，謝謝老師

但這題原來改寫前的程式碼若傳入參數本來就是 2 的冪，函式回傳的答案就是原本傳入的參數，改寫後的程式碼傳入參數原本就是 2 的冪的話就會是下一個 2 的冪，改寫後的原意和原來版本不同。

 

int main()
{
    uint64_t x;
    scanf("%ld", &x);
    printf("origin version : %ld\n", next_pow2_origin(x));
    printf("new version : %ld\n", next_pow2_origin(x));
}

結果

64
origin version : 64
new version : 128

文字訊息不要用螢幕截圖展現，尊重視覺障礙者閱讀的權益。

jserv

好的，已修正

這裡的 next_pow_origin 為改寫前有分支的程式碼。

使用 builtin_clzl 改寫

uint64_t next_pow2_origin(uint64_t x)
{
    int c = __builtin_clzl(x);
    return 1 << (64 - c);
}

__builtin_clzl 的功能是找出最高位的 1 以前有幾個 0，以此來算出最高位的 1 以下(含)有幾個位元，將 1 位移這些位元數就可以到下一個 2 的冪的位置，即為解答。

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


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

可以產生對應的 x86 指令，其中可以看到 bsrq 指令。

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

---

測驗 2

解釋程式碼運作原理

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

要達到合併的效果，就是用邏輯左移將低位位元清空為 0，之後跟下一個數字做 set bit，重點在於位移要位移多少，可以藉由觀察最高位元的 1 在哪個位置來決定要清出多少位置來做 set。
例如

$5_2$ 為

$0..0101$，若要合併則要將答案邏輯左移三個位置做 set bit，此例中這規則可以套用在

$2^3$ 到

$2^3-1$ ，故可以藉由 2 的冪來判斷當前合併要左移多少位置。

        if (!(i & (i - 1))
            len++;
        ans = (i | (ans << len)) % M;

參考到你所不知道的 C 語言：數值系統，判斷 2 的冪為 x & (x - 1) == 0，若判斷為 2 的冪即累加位移長度。
之後再將 ans 左移空出位元跟當前值做 bitwise-OR 運算即完成合併。

TODO:
嘗試使用 __builtin_{clz,ctz,ffs} 改寫，並改進 mod 的運算

---

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


qword 大小為 8 bytes 當成緩衝區

64 位元處理器架構一次處理能處理的最大資料量可以增加執行速度，故變數 qword 可以把它當成一個每次處理 8 個 bytes 的緩衝區，將 len >> 3 相當於除以 8，可算出共要處理多少組 8 bytes，剩下不足 8 bytes 就留到最後處理，開始用迴圈處理，方式和測驗中提到的方式相同，為 not bit6 and bit7，最後再用 popcount() 算出有多少位元組為 continuation bytes，累加 count。

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

最後就是要算出總字串 bytes 數量減掉 continuation bytes 數量就會得到字元總數，這裡 count 這個變數的意義就從 continuation bytes 數量變為字元總數，之後處理剩下不足 8 的 bytes，若 len & 7 (其實意義就是 len % 8) 有值代表有餘數，就用 count_utf8 處理，若為 0 代表沒有不足 8 的 bytes，即為 0。

---

測驗 4

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

程式碼原理

觀察給定整數可以發現出題目要檢查的樣式為

1 從高位元開始延伸，直到出現 0 以後只能出現 0

所以改寫前的程式碼原理就是每次迴圈將整數左移並檢查一次最高位元是否為 1，只要此整數尚未為 0 卻檢查到最高位元不為 1，代表中間出現過 0 但低位元尚有 1。

bool is_pattern(uint16_t x)
{
    const uint16_t n = -x;
    return (n ^ x) < x;
}

若符合樣式，可以觀察到取負號之後的 bit 會透過進位的方式取出最右邊的 1，且此最右邊的 1 必定是唯一的 1，且更高位元沒有夾雜 0，再和此整數做 XOR 操作等同於將此位元變為 0，且更高位元不會執行多餘的 XOR 操作，而算出來的值必定會小於此整數。

若不符合此樣式，取負號後一樣只會透過進位進位到最右邊的 1，但更高位元有出現 0，取負號後的高位位元已經變成反向，若做 XOR 操作會使得高位都被 set，運算後的值必定大於原來的值。

例如 
 x = 11010100
-x = 00101100
x ^ -x = 11111011
因更高位有 0 出現，取反向做 XOR 使得高位位元被 set，值必定大於 x