2023q1 Homework2 (quiz2)

contributed by < PlusThousand0107 >

實驗環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         4100.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4399.99

測驗 1

解釋程式碼原理

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

目的 :

找出最接近且大於等於2的冪的值

作法 :

利用 bitwise 的技巧，讓 x 和右移後的 x 做 or 操作，此操作能將最高位的 1 之後的所有bit都設成 1 ，這樣最後只要再做 x + 1 即可得到最接近且大於等於2的冪的值

例子 :

以 next_pow2(19) = 32 為例

1. 首先，x = 19₍₁₀₎ = 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 0011₍₂₎
2. 進行 x >> 1 的操作後會得到 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1001₍₂₎
3. 將兩數做 or 可得 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1011₍₂₎，在這能觀察到在最高位的 1 後面中有本來是 0 的bit被設成 1 了
4. 再做一輪能發現到 x 變成 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111₍₂₎，這時最高位的 1 後面已經全設成 1 了，只要再做 x + 1 就可得到 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0010 0000₍₂₎ = 32₍₁₀₎

用 __builtin_clzl 進行改寫

__builtin_clzl 可以返回從最高位到第一個 1 之前有幾個 0 ，所以用 64 減去此值可知道需位移的量，最後再用 1 向左移此位移量的距離即可得到最接近且大於等於2的冪的值，程式碼如下

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

例子 :

以 next_pow2(35) = 64 為例

1. 首先，x = 35₍₁₀₎ = 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0010 0011₍₂₎
2. 對 x 做 __builtin_clzl 會得到 58 ，再用 64 減去 58 得到 6 並將此值設給 shift
3. 讓 (uint64_t)1 往左移 shift 個單位後即可得到 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0100 0000₍₂₎ = 64₍₁₀₎

測驗 2

解釋程式碼原理

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

目的 :

給定一個整數n，將1到n的二進位表示串在一起合成一個二進位字串，將其轉乘十進位數後再 mod

${10}^9$ + 7

作法 :

1. 先將 M 設為 1e9 + 7 以表示
   ${10}^9$ + 7
2. 在 for 迴圈中會經過 1 到 n ，透過 len 紀錄整數 i 以二進位表示後的位元長度，在迴圈中還有一個判斷是用 (i & (i - 1) 的方式確認 i 是否為2的冪的值，如果是的話就 len++
   • EX : x = 8₍₁₀₎ = 1000₍₂₎ ， x - 1 = 7₍₁₀₎ = 0111₍₂₎ ， x & (x - 1) = 1000 & 0111 = 0000
3. 最後，因為要把 i 串到 ans 後面，所以藉由之前以 len 記錄下的長度進行 ans << len 的位移，並將 mod 完 M 後的值傳給 ans

例子 :

以 n = 5 為例

1. 從 1 開始，由於 1 是 2 的冪的值，所以 1 和 (1 - 1 = 0) 做 and 會得到 0 ，所以 len 會從 0 增加到 1 ，最後得到的 ans 為 1
2. 由於 2 也是 2 的冪的值，所以 len 會從 1 增加到 2 ，這代表目前的這個數的二進位表示法需用到的長度為 2 ，所以用 ans << len 將 1 位移成 100 後，再做 or 並 mod
   ${10}^9$ + 7 會得到 110 ，所以 ans 現在是 110
3. 而 3 不是 2 的冪的值，所以 len 不會增加，做 ans << len 後可得 11000 ，做完 or 再 mod
   ${10}^9$ + 7 會得到 11011
4. 因為 4 是 2 的冪的值，所以 len 會再從 2 增加到 3 ，做 ans << len 後會得到 11011000 ，最後的運算結果為 ans 是 11011100
5. 最後是 5 ，它不是 2 的冪的值，所以 len 維持不變，做 ans << len 後可得 11011100000 ，經過 or 和 mod
   ${10}^9$ + 7 的運算後得到 11011100101 ，再將這個結果回傳

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

這裡參考到了 Ahsen-lab 同學的講解

目的 :

用 SWAR 的技巧，計算所給定的 UTF-8 字串中 Unicode的字元數量

作法 :

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

• 首先先將 UTF-8 字串的 buf 用 uint64_t 型態的指標 qword 紀錄
• end 為 qword 的中止條件，這裡從 qword 開始算，後面還須加上 len >> 3 ，意思為 len / 8

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 紀錄位元組數量，並用迴圈的方式進行累加
• 在迴圈中會先用 t0 取得位元組， 再用 t1 紀錄做完反向運算的結果，之後會讓 t1 和 0x4040404040404040 做 and ，目的為隔離反向的第 6 個位元， t3 = t2 + t2 則是為了左移 1 位元，從第 6 位元移動到第 7 位元，之後的 t4 = t0 & t3 相當於在做 not bit6 and bit7 ，最後再用 __builtin_popcountll 計算，並將結果累加給 count

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

return count;

• 從迴圈跳脫出來後，會讓 len 除 8 ，再用 bitwise 的方式乘 8 ，減去後續位元組的數量後即可得到 UTF-8 字元的數量
• 因為總位元組數不一定是 8 的倍數，所以這裡用 len & 7 的方式來做判斷，如果餘數大於 0 就用 count_utf8 處理剩餘的位元組，並將結果加到 count ，若餘數等於 0 則是將 0 加到 count

測驗 4

解釋程式碼原理

bool is_pattern(uint16_t x)
{
    const uint16_t n = ~x + 1;
    return (n ^ x) < x;
}

目的 :

判定16位元無號整數是否符合特定樣式，根據給定的範例可發現樣式規定為「最高位必須為 1 ，且到最低位的 1 之間的bit也必須都是 1 」，例子如下

• f000₍₁₆₎ = 1111 0000 0000 0000₍₂₎ => True
• f300₍₁₆₎ = 1111 0011 0000 0000₍₂₎ => False
• f800₍₁₆₎ = 1111 1000 0000 0000₍₂₎ => True

作法 :

做 ~x + 1 的目的是對 x 取二補數，而做 (~x + 1) ^ x 則是想去掉最右邊的 1 ，最後再做 ((~x + 1) ^ x) < x 以判別 x 是否符合樣式

例子 :

1. 以 f800₍₁₆₎ 為例

• x = f800₍₁₆₎ = 1111 1000 0000 0000₍₂₎ ， ~x + 1 = 0000 1000 0000 0000₍₂₎ ， (~x + 1) ^ x = 1111 0000 0000 0000₍₂₎ ， 又 1111 0000 0000 0000₍₂₎ < 1111 1000 0000 0000₍₂₎ ，故回傳 True

2. 以 f300₍₁₆₎ 為例

• x = f300₍₁₆₎ = 1111 0011 0000 0000₍₂₎ ， ~x + 1 = 0000 1101 0000 0000₍₂₎ ， (~x + 1) ^ x = 1111 1110 0000 0000₍₂₎ ， 而 1111 1110 0000 0000₍₂₎ > 1111 0011 0000 0000₍₂₎ ，所以回傳 False ，表示不符合樣式