###### tags: `Linux`
# 2023q1 Homework2 (quiz2)
contributed by < [`shhung`](https://github.com/shhung) >

## 測驗`1`
補完程式碼，找出最接近且大於等於 2 的冪的值。
- `AAAA` 和 `BBBB` 皆為數值，且 `AAAA` 小於 `BBBB`
- `CCCC` 為表示式

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 >> AAAA; // AAAA = 8
    x |= x >> 16;
    x |= x >> BBBB; // BBBB = 16
    return CCCC; // CCCC = x + 1
}

### 思路
2 的冪以二進位表示只會有一個 `1` ，因此只要找到最左邊為 `1` 的位元，回傳他的下一位元為 `1` ，其他位元為 `0` 的值。
依照題目的提示，設定 (set，即指派為 `1`) 自原本最高位元到最低位元中，所有的位元。

### 答案
- `AAAA` 為 8
- `BBBB` 為 16
- `CCCC` 為 `x + 1`

### 說明

每一次的 `|=` 操作都會透過最高位元往低位元做設定的操作，到了 `AAAA` 的那一行已經設定了 8 個位元，可以一次設定 8 個位元，所以 `AAAA`為 8 ，如此就設定了 16 個位元，下一行也因此可以設定 16 個位元，到了 `BBBB`這一行時就可以設定 32 個位元，如此就將最高位元到最低位元設定為 `1` ，而 `CCCC` 為 `x + 1` 就能夠得到 2 的冪且大於 `x`

### 用`__builtin_clzl`改寫

uint64_t next_pow2(uint64_t x)
{
    int leadZero = __builtin_clzl(x);
    int leadOne = 64 - leadZero;
    return (uint64_t)1 << leadOne;
}

透過 `__builtin_clzl` 找到 `x` 的 leading 0-bits 的數量，就可以反向算出 `x` 最高位元為 `1` 的位置。

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

此程式碼用於將 1~n 的十進位數值轉為二進位，並且將個別對應的二進位做串接，求出二進位字串 mod $10^9+7$ 的值

### 答案

for (int i = 1; i <= n; i++) {
    if (!(i & (i - 1)))
        len++;
    ans = (i | (ans<<len)) % M; 
}

> 參考 [hankTrao](https://hackmd.io/@hankTaro/quiz2) 所提到判斷 2 的冪的方法
- `x & (x - 1)` 的數學意義為
- power of 2
- signed v.s. unsigned

如果 `i` 為 2 的冪， `len` 就增加到符合 `i` 的位元數，透過 shift 來將已串聯的值空出可以放下 `i` 的位元數，再將 `ans` 和 `i` or 就可以連接。

### 使用 `__builtin_{clz,ctz,ffs}` 改寫，並改進 mod $10^9+7$ 的運算

for (int i = 1; i <= n; i++) {
    if ((__builtin_ffs(i) + __builtin_clz(i)) == 32)
        len++;
    ans = (i | (ans<<len)) % M; 
}

- `__builtin_clz`
- 回傳左起第一個 1 之前 0 的個數
- `__builtin_ctz`
- 回傳右起第一個 1 之後 0 的個數
- `__builtin_ffs`
- 回傳右起第一個 1 的位置

使用 `__builtin_clz` 和 `__builtin_ffs` 來判斷 `i` 是否為 2 的冪，若兩者相加為資料結構對應的位元數，則為 2 的冪。

## 測驗`3`
## 測驗`4`

以下程式碼可判定 16 位元無號整數是否符合特定樣式 (pattern):

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

符合上述程式碼的樣式，如下:

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 = EEEE;
    return (n ^ x) < FFFF;
}

### 答案

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

### 說明
> 參考 [ItisCaleb](https://hackmd.io/@ItisCaleb/HyTEU5j0i) 的說明

從原本的程式碼可以看出符合條件的 pattern 必須是從 msb 開始連續任意個 1

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

`EEEE` 的部分為 `~x + 1`，如果是符合 pattern 的值經過這個操作後，會獲得 rightmost set bit ，這個值和原本的值做 xor 後，會清除 rightmost set bit 且小於原本的值，所以 `FFFF` 為 `x`。而非 pattern 的值在經過 `~x + 1` 後在較高位的 `0` 的位置會是 `1`，而這個值和原本的值 xor 會導致結果比原本的值大，和 pattern 的結果相反。