2023q1 Homework2 (quiz2)

contributed by < brianlin314 >

第2週測驗題

測驗一

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

該題是要找出最接近且大於等於 2 的冪的值

在此舉 next_pow2(15) 為例：

由於每一次的操作都會將 x 向右位移所設定之位元後，並且再與原本的 x 做 bitwise or 運算，該例子每一次操作的結果接會是以下：

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1111

最後再執行 ++x 即可得到最後的值，即為16。

使用 __builtin_clzl 改寫

__builtin_clzl 用於計算整數中最高位元位之前的零位元數量。因此，它的作用是返回這個整數值在二進制表示中從左邊開始數的零位元的個數。

因此我們可以使用 __builtin_clzl 幫助計算下一個 2 的冪次方。

改寫如下：

uint64_t next_pow2(uint64_t x) {
    if (x == 0) 
        return 1;
    uint64_t n = 64 - __builtin_clzl(x);
    return 1 << n;
}

測驗二

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

該題是要將給定的 1~n 的數值轉為二進制，並且串接起來，最後轉回十進制再 mod \(10^9 + 7\)，最後所得之值即為最終結果。

其中，這個 if 判斷式是要判斷 i 是否為2的冪次方，若為2的冪次方，代表二進制的長度增加了，所以進行 len++，其中 len 存放要左移的 bit 數。

接下來的每次 for 迴圈中，都會對 ans 先進行左移，用意是為了可以串接 i ，再 mod \(10^9 + 7\)。

嘗試使用 __builtin_{clz,ctz,ffs} 進行改寫

  • __builtin_clz(x) 這個函式可以用來求一個整數的二進制表示中，最高位為 1 的位數（也就是整數的二進制表示的位數減去 __builtin_clz(x) 的值）。
    • 例如，若 x 為 0b000011110000，則 __builtin_clz(x) 的結果為 4。
  • __builtin_ctz(x) 這個函式用於計算一個二進制整數末尾有幾個 0。
    • 例如，若 x 為 0b000011100000，則 __builtin_ctz(x) 的結果為 5。
  • __builtin_ffs(x) 用於查找整數 x 的最後一個二進制位（LSB，Least Significant Bit）的位置。它返回的是該位置的索引。
    • 例如，若 x 為 0b1011010 則 __builtin_ffs(x) 返回 2，因為最後一個二進制位是第 2 位。

改寫如下:

unsigned long long concatenatedBinary(int n)
{
    const unsigned int M = 1e9 + 7;
    int len = 0;
    long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!(i & (i - 1)))
            len = __builtin_ctz(i) + 1;
        ans = (i | (ans << len)) % M;
    }
    return ans;
}

將原本為 len++ 的部分，改為 len = __builtin_ctz(i) + 1。

測驗三

此程式碼是用來計算一個給定的 UTF-8 字串的字元數量，在 UTF-8 中，字元可由 1~4 個位元組組成，其中 110x.xxxx 、 1110.xxxx 、 1111.0xxx 是 leading byte，而後續的 10xx.xxxx 就是 continuation bytes

ASCII 0xxx.xxxx
2 bytes 110x.xxxx 10xx.xxxx
3 bytes 1110.xxxx 10xx.xxxx 10xx.xxxx
4 bytes 1111.0xxx 10xx.xxxx 10xx.xxxx 10xx.xxxx 
#include <stddef.h>
#include <stdint.h>

size_t count_utf8(const char *buf, size_t len)
{
    const int8_t *p = (const int8_t *) buf;
    size_t counter = 0;
    for (size_t i = 0; i < len; i++) {
        /* -65 is 0b10111111, anything larger in two-complement's should start
         * new code point.
         */
        if (p[i] > -65)
            counter++;
    }
    return counter;
}

首先先看到 -65 這個特別的數字，並從註解中得知 -65 的二補數是 0b10111111，進而得知只有大於 -65 的數才能使 counter++ ，也就是計算非 10 開頭的二進位，即計算 leading byte 的數量。

size_t swar_count_utf8(const char *buf, size_t len)

參數 buf 是一個指向 UTF-8 字串的指針，len 則是字串的長度。

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

qword 一次會存取 8 bytes，並且會計算能被 8 整除的 bytes 的最後一個的位址，將其存在 end。

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 bytes 的字元數量。

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

這段程式碼首先計算字串中能被 8 整除的 bytes 的數量，再將其減掉上面迴圈中算出的 continuation bytes 的數量。

也就是說，經過這段程式碼，可以算出能被8整除的 byte 中，leading byte 的數量。

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

最後，則是將無法被 8 整除的最後一部分，利用 count_utf8 算出他的 leading byte的數量，並加到 count 中。

測驗四

該題為判斷 16 位元無號整數是否符合特定樣式 (pattern)，其樣式為確認 MSB 是否為 1，且從 MSB 到最低位的 1 之見是否是包含連續的 1。合法樣式為下:

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)

if (!x)
    return 0;

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

return true;

首先判斷輸入值是否為 0，如果為 0，則不符合樣式，直接回傳 false。

接著從輸入值的最高位開始檢查到最低位的 1 之間，每個位元是否為 1，如果該位元不是 1，則代表不符合樣式，直接回傳 false。如果區間內的所有位元都為 1，則回傳 true。

改寫上述程式碼，使其達到等價行為

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

一開始，會對 x 取二補數，以原本最右邊為 1 的位元為基準，其右邊與自身保留原本位元，左邊則是所有位元進行反轉。如以下:

 x = 1111 0000 0000 0000
        ^ ------> 基準點
-x = 0001 0000 0000 0000

接者執行 -x ^ x，如以下:

    x = 1111 0000 0000 0000
   -x = 0001 0000 0000 0000
 --------------------------
 x^-x = 1110 0000 0000 0000

若為特定樣式，可保證執行 -x ^ x 運算後的值必定小於原本的 x。

若 x 不為特定樣式，必定會導致最後的運算結果大於原本的值，如以下:

    x = 1110 1000 0000 0000
   -x = 0001 1000 0000 0000
 --------------------------
 x^-x = 1111 0000 0000 0000
Select a repo