---
tags: linux2023
---

# 2023q1 Homework2 (quiz2)
contributed by < `paul90317` >

[題目連結](https://hackmd.io/@sysprog/H143OpNCo)

### 測驗 `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`](https://hackmd.io/@Hongweii/quiz2)

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