---
tags: Linux核心設計/實作
---

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

> [題目](https://hackmd.io/@sysprog/linux2023-quiz2)

### 測驗 `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 >> AAAA;
    x |= x >> 16;
    x |= x >> BBBB;
    return CCCC;
}

#### 延伸問題:
 1. 解釋上述程式碼原理，並用[__builtin_clzl](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 改寫

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

 2. 在 Linux 核心原始程式碼找出類似的使用案例並解釋
 3. 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？
### 測驗 `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. 解釋上述程式碼運作原理
2. 嘗試使用__builtin_{clz,ctz,ffs}改寫，並改進運算
### 測驗 `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 << AAAA) * (len / 8) - count;
count += (len & BBBB) ? count_utf8((const char *) end, len & CCCC) : DDDD;

return count;
}

#### 延伸問題:
### 測驗 `4`
補完下列程式碼：

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

#### 延伸問題: