2023q1 Homework2 (quiz2)

contributed by < paul90317 >

題目連結

測驗 1

該程式碼的原理是把最高位的 1 填滿較低位的所有位元。

• AAAA 應是 8
• BBBB 應是 32
• CCCC 應是 x

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

觀察程式碼, i 是目前要串接的數字, 而 len 是指要串接的位元數, 所以每當程式碼來到新的位元數時就要增加，故條件是 i >> len，但題目是要 !(DDDD)，所以 DDDD 應該要是 i >> len == 0。
而 EEEE 那行程式碼是用來串接的，所以是 ans << len

測驗 3

觀察 ASCII 編碼方式

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

只要是後續位元組，第 7 個 bit 為 1 且第 6 個 bit 為 0（以 LSB 為第 0 個 bit），當然因為要一次處裡 8 個位元組，所以不能使用分支（if else）。

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 << AAAA) * (len / 8)  - count;
    count += (len & BBBB) ? count_utf8((const char *) end, len & CCCC) : DDDD;

    return count;
}

可以看出為了不要記憶體溢出，所以 end 是取 qword 向後位移 \(\lfloor len/8\rfloor\) 個 uint64_t 的長度。
所以 AAAA 那行應是要將 qword 與 end 區間內的字元個數計算完畢，故是 3 。
而 BBBB 那行有個分支，如果 len 為 8 的倍數的話，就會回傳前一行的結果，所以 BBBB 是 8，DDDD 是 count。
而剩下的 bytes 是用沒有 swar 的版本跑，所以 CCCC 應是 8。

測驗 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 都在高位，且至少要有一個 1 。

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

以下答案參考自 Hongweii

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

雖然沒想出答案，但我還是可以提出自己的證明，~x + 1 其實就是 -x，只是 x 是無號整數所以只能這樣做，為了方便，以下我會當 x 是有號數來證明。
有一種快速做負號的方式是，將 x 最右邊的 1 以及其右邊的 0 保留，左邊的位元全部倒數，而這題就是巧妙運用這個性質。
該性質並非經驗法則，將 x 的倒數 +1 理解為從 LSB 而左不斷進位（設成 0），直到遇到第一個 0 ，並將其設成 1 。相當於是將 ~x 右邊位元全部倒數，而在 x 的行為就是左邊的位元全部倒數。
n ^ x 的值根據上面的性質，會等同於將 x 最右邊的 1 與其左邊的位元歸零，剩下都變成 1 。
所以當 x 符合型態，n ^ x 就會是將 x 最右邊的 1 拿掉，當然會小於 x。反之，x 最右邊 1 仍會變成 0，但其左邊一定存在較高位的 0 會變成 1 ，如此便會讓不等式不成立。
0 是該證明的特殊情況，代數字進程式碼會使其回傳 0。又因為 0 不符合情態，所以程式碼是對的。

---

真正的答案應該是

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