2023q1 Homework1 (quiz2)

contributed by JoshuaLee032190

測驗一

• 根據題目的名稱next_pow2，我們可以知道這個題目要找出當前整數的下一個2 的冪整數。
• 題目如下：

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

• 要回答這個問題首先可以直接看 pattern，可以看到前面總共做了7次 x |= x >> 1，而且AAAA的下一行為 16，由此我們可以推測 AAAA 為 8
• BBBB 為 32
• CCCC 就要從前面想了，前面的意思為把這個整數的某一個位元往右全部填滿 1，那在全部都是1的狀況，我們只需要 + 1 即可得出最終的結果

我覺得前面右移做了七次有點多此一舉，而測試後，其實可以把code 改成以下的狀況達到同樣的結果

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

延伸問題

1. 解釋上述程式碼原理，並用 __builtin_clzl 改寫

int __builtin_clz (unsigned int x)
// Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
int __builtin_clzl (unsigned long)
// Similar to __builtin_clz, except the argument type is unsigned long.
// 利用 __builtin_clzl 改寫完成
uint64_t next_pow2_2(uint64_t x)
{
    int hi = __builtin_clzl(x >> 32);
    int lo = __builtin_clzl(x);
    uint64_t res = 1;
    return (hi == 31) ? res << 31 - lo + 1 : res << 64 - hi;
}

2. 在 Linux 核心原始程式碼找出類似的使用案例並解釋

• 我先使用 grep -r "roundup" * 找出了 pci.h

# /include/linux/pci.h

static inline int pci_rebar_bytes_to_size(u64 bytes)
{
        bytes = roundup_pow_of_two(bytes);

        /* Return BAR size as defined in the resizable BAR specification */
        return max(ilog2(bytes), 20) - 20;
}

• 這段程式碼主要是為了要初始化及配置空間，其中20的數字代表了 1mb 的大小所以先取 max
• 可以想像，回傳值是一個大於等於0的常數，如果回傳值為0，那就代表PCI只需要配置1MB的空間，反之，以回傳值來判斷需要多配置多少空間

3. 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？

提示: 可執行 gcc -O2 -std=c99 -S next_pow2.c 並觀察產生的 > next_pow2.s 檔案，確認 bsrq 指令 (表示 “Bit Scan Reverse”)

• 有產生bsrq

next_pow2_2:
.LFB14:
	.cfi_startproc
	endbr64
	shrq	$32, %rdi
	movl	$64, %ecx
	movl	$1, %eax
	bsrq	%rdi, %rdi
	xorq	$63, %rdi
	subl	%edi, %ecx
	salq	%cl, %rax
	ret
	.cfi_endproc

測驗二

解釋題目

• 由題目敘述得知，這個 function 會回傳1~輸入，的二進位連接起來的數字
• 題目如下

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

• 由題目內的參數名稱以及 ans = (i | (EEEE)) & M可知，len 為往左移動的距離
• 而只有在一種條件下 len 才會需要 + 1，此情況為：

# 考慮 1 - 10 的位元如下
1 : 0001
2 : 0010
3 : 0011
4 : 0100
5 : 0101
6 : 0110
7 : 0111
8 : 1000
9 : 1001
10: 1010

• 我們可以仔細觀察位元進位的時刻，狀況為前一個數字和當前的數字做 AND 運算得到 0 的狀況
• 所以 DDDD 很明顯就是 i & (i - 1)
• 而每次都需要更新當前的位元到 ans 中，可想而知 EEEE 為 ans << len，如此一來就可以把運算後的數字放入當前空下來的位元

使用__builtin 改寫

• __builtin_ffs : 用來找出 LSB 的位置 從右邊開始數的第一個bit
• __builtin_clz : 用來找出 MSB 的位置 從左邊開始數的第一個bit
• __builtin_ctz : 回傳從右邊開始數有幾個0

int concatenatedBinary(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;
}

測驗三

• 看不懂 待處理

測驗四

解釋程式碼

• is_pattern 主要是在看輸入的無號整數的編碼是否存在特定樣式
• 此特殊樣式為從MSB開始往LSB存在連續1
• 前面的function 可以看到在迴圈中x 總是跟 0x8000 也就是 1000000000000000 做and，當位元還沒有被清空時，只要中間的連續1斷開則回傳false

後面的function 則是找出這個pattern 會發生的事情

# 我們來看一下這個 pattern (這個假設在 bit數為5的狀況)
10000
11000
11100
11110
11111

首先，題目很明顯告訴你有一個 xor 跟比大小；也就是我們必須往比大小的方向思考
那要怎麼樣才可以利用這個 pattern 比大小呢？
我們只需要先取 x 的負數，如此一來可以得到
10000    ==> 10000
11000    ==> 01000
11100    ==> 00100
11110    ==> 00010
11111    ==> 00001
此時  x ^ -x 就會變成
00000
10000
11000
11100
11110
最後再與原本的狀況比大小，此時，如果符合這個 pattern 的話，結果一定會比原本的輸入還要小，此時只要比大小，回傳即可。

EEEE 為 -x
FFFF 為 x

在 linux kernel 中找此 bitmask

• 待處理