---
tags: quiz2, linux2023
---

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

## [測驗 `1`](https://hackmd.io/@sysprog/linux2023-quiz2#%E6%B8%AC%E9%A9%97-1)

題目: 針對給定無號 64 位元數值 `x` 找出最接近且大於等於 2 的冪的值,例如:

next_pow2(6) = 8
next_pow2(15) = 16
next_pow2(64) = 64

`x |= x >> 1` 因為 `>>` precedence 比 `|` 高，所以執行順序是 `x = x | (x >> 1)`

因為每做一次 `x |= x >> 1` 會向 LSB 多擴展 1 個 1

`AAAA` 之前會有 8 個 1, 而 `AAAA` 之後需要 16 個 1, 所以 `AAAA = 8`

同理 `BBBB = 32`

最後使 `x` 中 MSB 的 1 擴展到 LSB
然後 `CCCC = x + 1` 剛好進位到下一個 2 的冪的值。
但如果 $x = 2^{n}$ || $x = 2^{64}$ 答案會 +1 或 integer overflow, 所以要 `x - 1`

### 配合 `__builtin_clzl` 改寫

uint64_t next_pow2(uint64_t x)
{
    /* If x is 0, the result is undefined. */
    /* avoid x - 1 is 0 or -1 if x is 1 or 0 */
    if (x <= 1)
        return 1;
    
    uint64_t carry = 64 - __builtin_clzl(x - 1);
    return 1UL << (carry);
}   

### 在 Linux 核心原始程式碼找出類似的使用案例並解釋
從 [C 語言：數值系統的roundup_pow_of_two()](https://hackmd.io/@RinHizakura/HJ0rPhxyD#__rounddown_pow_of_two--__roundup_pow_of_two) 得知類似操作,

[unsigned long __roundup_pow_of_two(unsigned long n)](https://docs.kernel.org/core-api/kernel-api.html?highlight=roundup_pow_of_two#c.rounddown_pow_of_two)

Description

*round the given value up to the nearest power of two - the result is undefined when n == 0 - this can be used to initialise global variables from constant data*

從`grep -r "rounddown_pow_of_two\|roundup_pow_of_two" linux-6.2.2/kernel/` 找到 `hashtab.c` 的 [`htab_map_alloc`](https://github.com/torvalds/linux/blob/master/kernel/bpf/hashtab.c#L456)有類似的使用案例

htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);

在 [line 493](https://github.com/torvalds/linux/blob/master/kernel/bpf/hashtab.c#L493) 利用 `roundup_pow_of_two` 確保 `n_buckets` 的大小是2的冪的值

### 編譯器能否產生對應的 x86 指令
在Compiler Explorer [x86-64 gcc 11.3](https://godbolt.org/z/TcooKce7W) 執行, 結果有 `bsrq` 指令

## [測驗 `2`](https://hackmd.io/@sysprog/linux2023-quiz2#%E6%B8%AC%E9%A9%97-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 | ans << len) % M;
    }
    return ans;
}

`len` 是 int 在記錄 bit 的有效長度,只有
`len` 的長度可以用 bitwise 操作 `!(i & i-1)` 判定 `i` 的bit長度是否需要 `len++`

最後的 `ans` 是先把 `ans` 向左移動(`ans << len`), 之後用 bitwise or 去把兩個值的 bit 接在一起再 mod M

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

for (int i = 1; i <= n; i++)
        ans = (i | (ans << (32 - __builtin_clz(i)))) % M;

return ans;

利用 `32 - __builtin_clz(i)` 算出位移量,可以減少決定 `len`的值的 if statement 和 `len` 參數

## [測驗 `3`](https://hackmd.io/@sysprog/linux2023-quiz2#%E6%B8%AC%E9%A9%97-3)

## [測驗 `4`](https://hackmd.io/@sysprog/linux2023-quiz2#%E6%B8%AC%E9%A9%97-4)