# 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 1**1**00)~2~ | (1111 1**01**0)~2~ |
| -------- | -------- | -------- |
| n = -x | (0000 0100)~2~ | (0000 0110)~2~ |
| n ^ x | (1111 1**0**00)~2~ | (1111 1**10**0)~2~ |