# 2023q1 Homework2 (quiz2)
contributed by < siwon0619 >

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

### 解釋程式碼
目標為找到最接近且大於等於2的冪的值,因此這邊將所有最高位元下的所有位元都將其設為1最後透過將`x`加一使其進位便會獲得最接近2的冪的值

如同`x`為(0001 0100)~2~-->(0010 0000)~2~
可以觀察到最接近於2的冪的值為原最高位元左移一位且後面位元皆為0所組成,因此可以透過`++x`來達到進位

### 用 __builtin_clzl 改寫
* Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
--> 其功能為回傳最高位元以前0的個數,因此可以用來計算需要左移多少位元
將程式改寫為:

uint64_t next_pow2(uint64_t x)
{
    if(!x)
        return 1;
    int count = __builtin_clzl(x);
    return 1 << (64-count);
}

## 測驗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 | (i << len)) % M;
    }
    return ans;
}

### 解釋程式碼
給定一整數n，回傳將 1 到 n的二進位表示法依序串接在一起所得到的二進位字串，其所代表的十進位數字 mod $10^9 + 7$ 之值。
* 可以觀察到 `i & (i - 1)`為判斷是否為2的冪次,若成立`len++`,若不成立len長度不變
* 將`ans << len`移出空間使 `i`可與其進行合併

### 用 __builtin_{clz,ctz,ffs} 改寫

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
         */
        int len = 32 - __builtin_clz(x);
        ans = (i | (i << len)) % M;
    }
    return ans;
}

使用__builtin_clz計算leading zeros,可直接計算需要位移的長度

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

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

### 解釋程式碼
我們可以觀察到` x & 0x8000(MSB) `為 0則不符合特定pattern會return false,符合上述程式碼的樣式，如下:

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)

可以知道上述以二進位表示為

1000 0000 0000 0000~2~
1100 0000 0000 0000~2~
1110 0000 0000 0000~2~
.
.
.
.
1111 1111 1111 1111~2~

#### 改寫上述程式碼

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

以`x`=(1110 0000 0000 0000~2~)為例,`n`為`x`之補數,因此可以得知`n`=(0010 0000 0000 0000~2~),便將兩者取 $xor$ 可以得到 (1100 0000 0000 0000~2~),而此值比當前`x`小,便會return true,為符合pattern