2023q1 Homework2 (quiz2)

contributed by < YSRossi >

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

• 目標找出 x 最接近且大於等於 2 的冪的值，x 最高位的 1 的下一個高位位元即是答案。
• 想法是找出 x 最高位的 1 ，將比這個位元低位的位元都設成 1 ，最後加一進位後，得到答案。
• 前面做了 7 次 x |= x >> 1，代表最高位的 1 右側的 7 個位元都設成 1，後續分別右移 8 、 16 、 32 個位元，且每次都要與 x 做 OR 存到 x 當中，使 64 個位元都處理過，最後加一進位後，得到 x 最接近且大於等於 2 的冪的值。

---

測驗 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 (!(i & i - 1))
            len++;
        ans = (i | (ans << len)) % M;
    }
    return ans;
}

• 迴圈中會將 i 接在 ans 的最低位。
• 作法是將 ans 往左位移，將低位元清出足夠多的 0，與 i 做 OR ，完成合併。
• 要位移多少取決於 i 最高位的 1 的位置，藉由判斷是否為 2 的冪 if (!(i & i - 1)) ，若是的話 i & i - 1 == 0，將 len 累加，得到最高位的 1 的位置。

---

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

• 從函式 count_utf8 的 for (size_t i = 0; i < len; i++) 得知， len 代表的是字串總長度，單位為 byte。
• 從第七行 for 迴圈 for (; qword != end; qword++) 得知，一次會處理一個 qword 的大小，而一個 qword 為 64 位元，所以第四行的 len >> 3 將 len 除以 8 個 bytes，計算總共要處理幾個完整的 8 bytes。
• for 迴圈中使用 not bit6 and bit7 的 bitmask，找出 10xx.xxxx 形式的 byte，使該 byte 經過 bitmask 的處理後的輸出為 1000.0000。搭配函式 __builtin_popcountll 計算 64 位元中有多少位元為 1 ，即可求得 continuation bytes 數。

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

• 原先題目應該是 count = (len >> 3) << 3 - count ，作用是將 len 的最右側 3 個位元設為 0 ，得到整除部分的 byte 數，再減去 continuation bytes 數。
• count = (1 << 3) * (len / 8) - count 中的乘以 8 與除以 8 也有相似的移位效果，能將 len 的最右側 3 個位元設為 0 ，再減去 continuation bytes 數。
• len & 7 相當於取 8 的餘數，處理剩餘無法被整除的部分，使用函式 count_utf8 求出 continuation bytes 數，最後將其加上 count 得到最後結果。

---

測驗 4

判定 16 位元無號整數 x 是否符合以下特定樣式 (pattern)

pattern: 8000 (32768)
pattern: c000 (49152)
pattern: e000 (57344)
pattern: f000 (61440)
pattern: f800 (63488)
pattern: fc00 (64512)
pattern: fe00 (65024)
pattern: ff00 (65280)
pattern: ff80 (65408)
pattern: ffc0 (65472)
pattern: ffe0 (65504)
pattern: fff0 (65520)
pattern: fff8 (65528)
pattern: fffc (65532)
pattern: fffe (65534)
pattern: ffff (65535)

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

• 觀察題目所要求的 pattern ，可以發現所有符合要求的數字都是一個最高位為 1 的 16 位元無號整數，且最低位的1與最高位之間的位元皆為1。
• -x 與 x 做 XOR 後，會有以下兩種功能 :
  1. x 最低位的 1 變成 0。
  2. x 最低位的 1 與最高位之間為 0 的位元變成 1。

  • 符合題目要求的 pattern ，最低位的 1 與最高位之間皆為 1 ，只會將 x 最低位的 1 變成 0 ，因此 XOR 後的結果會小於 x。

  • 不符合題目要求的 pattern 最低位的 1 與最高位之間存在 0，不只會將 x 最低位的 1 變成 0 ，還會將 x 最低位的 1 與最高位之間為 0 的位元變成 1，因此 XOR 後的結果會大於 x。

    x	(1111 1100)2	(1111 1010)2
    n = -x	(0000 0100)2	(0000 0110)2
    n ^ x	(1111 1000)2	(1111 1100)2