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

## 測驗 `1`
### 解釋程式碼原理
此題關鍵在於找出最高位元的 1 ，並將從此位元到最低位元的所有位元 set 為 1 ，再透過對 `x + 1` 來使其進位成 2 的冪的值。
舉例來說 `x` 如果是 $(0010$ $1010)_2$ ，需要先 set 成 $(0011$ $1111)_2$ ，再透過 `x + 1` 成為
$(0100$ $0000)_2$
而因 `x` 為 64 位元的 `uint64_t` ，故最多需要右移 63 個位元。
因此程式碼為:

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

並可進一步精簡為:

uint64_t next_pow2(uint64_t x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return x + 1;
}

### 用 `__builtin_clzl` 改寫

uint64_t my_next_pow2(uint64_t x) {
  int shift = 64 - __builtin_clzl(x);
  return 1UL << shift;
}

`__builtin_clzl` 的功能為找出最高位的 1 前面總共有幾個 0
而透過 `shift = 64 - __builtin_clzl(x)` 可以算出 x 在二進位下的 bits 長度，那只要對 1 左移 shift 個位元，即可得到答案。
舉例來說， `x` = $(0010$ $1010)_2$ ，則 `shift` = 64 - 58 = 6 ，因此我們對 1 左移 6 個位元，即可得到答案 $(0100$ $0000)_2$

### 對應的 x86 指令

my_next_pow2:
.LFB16:
        .cfi_startproc
        endbr64
        bsrq    %rdi, %rdi
        movl    $64, %ecx
        movl    $1, %eax
        xorq    $63, %rdi
        subl    %edi, %ecx
        salq    %cl, %rax
        ret
        .cfi_endproc

產生對應的 x86 指令，可以看到 `bsrq` 指令。

---

## 測驗 `2`
### 解釋程式碼原理
此題關鍵在於 `len` 這個變數，代表的是當前 `i` 值在二進制表示下的 bits 長度，也影響到了 `ans` 每次需要左移幾個位元，以 `ans = 1 , i = 2` 為例，由於 `i` 的二進位表示為 $(10)_2$ ，也就是 `len` 為2，因此需先將`ans` 左移 2 位成 $(100)_2$ ，再將 `i` 的值 $(10)_2$ set 上去成 $(110)_2$ 。

而以下的 if 判斷影響到了 `len` 的值。

if (!(DDDD))
    len++;

可以發現在 `i` 在增加為 2 的冪次時，長度也會增加，例如 `i` 從 `111` 變為 `1000` 時，因此這邊需要判斷 `i` 是否為 2 的冪次，正確程式碼應如下:

if (!(i & i - 1))
    len++;

如果 `i` 為 2 的冪次， `(i & i - 1)` 將為 0 ，即 `!(i & i - 1)` 為 1 。
接著則是將 `ans` 左移 `len` 個，並 set 上 `i` 的值。

ans = (i | (ans << len)) % M;

### 嘗試使用 `__builtin_{clz,ctz,ffs}` 改寫

int myConcatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    int len = 0; 
    long ans = 0;
    for (int i = 1; i <= n; i++) {
        len = 32 - __builtin_clz(i);
        ans = (i | (ans << len)) % M;
    }
    return ans;
}

`__builtin_clz` 的功能為找出最高位的 1 前面總共有幾個 0
透過 `shift = 32 - __builtin_clz(x)` 可以算出 x 在二進位下的 bits 長度，也就是變數 `len` 的值，即可用其來算出 `ans`

---

## 測驗 `3`

const uint64_t *end = qword + len >> 3;

這邊將 `len` 右移了 3 個位元，也就是等同於除以八，因為我們為了增加執行速度，需要一次處理 8 bytes ，這樣做可以算出能完整放入 64 bits 的共有幾組，至於不足 8 bytes 的則之後處理。

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

`(1 << 3) * (len / 8)` 用來計算出總長度中能完整放入 64 bits 的 8 bytes 組共有幾個 bytes ，然後再減去 `count` (即 continuation bytes 的數量)。

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

最後再透過 `len & 7` 檢查是否有不足 8 bytes 的部份需要處理，如果有則透過 `count_utf8` 來計算出扣除 continuation bytes 的字元數量，然後再相加以得到結果。

---

## 測驗 `4`
### 解釋程式碼原理

bool is_pattern(uint16_t x)
{
    if (!x)
        return 0;

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

    return true;
}

上述程式碼一開始會先檢查 `x` 是否為 0 ，如果是則直接 `return 0;` ，之後迴圈內會將 `x` 左移一個位元，如果 `x` 為 0 則跳出迴圈，可發現如果 `x` 不為 0 且最高位不為 1 則會 `return false;` ，因此我們可看出 `x` 只有在以下形式會 `return true;`

1000 0000 0000 0000
1100 0000 0000 0000
1110 0000 0000 0000
.
.
.
1111 1111 1111 1111

根據此性質，可以做以下的改寫

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

將 `~x + 1` (即 `-x`) 和 `x` 做 `xor` 並判斷是否會小於 `x`
這邊以 8 bits 情況下的 $(1110$ $0000)_2$ 和 $(1110$ $1010)_2$ 來當例子:
$(1110$ $0000)_2$ `xor` $(0010$ $0000)_2$ = $(1100$ $0000)_2$
這邊會將原先最低位的 1 給改成 0 ，所以會小於原本的 `x`

$(1110$ $1010)_2$ `xor` $(0001$ $0110)_2$ = $(1111$ $1100)_2$
這邊會將原先中間的 0 給改成 1 ，所以會大於原本的 `x`