2023q1 第二週 quiz

第一題

完整程式碼

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

本來看到一連串的

    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;

不知道其用途，舉實際上的例子來搭配，才不會"舉燭"
取 x = 65 (010001)

x |= x >> 1;// x = 01100001
x |= x >> 1;// x = 01110001
x |= x >> 1;// x = 01111001
x |= x >> 1;// x = 01111101
x |= x >> 1;// x = 01111111
x |= x >> 1;// x = 01111111

可以發現一連串的操作就是從 most significant bit 開始逐漸填滿 1 ，而後面的

x |= x >> 8;
x |= x >> 16;
x |= x >> 32;

取 x = 140737488355328(2^47)
經過前面的 7 次 x |= x>>1 會變成

111111110000000000000000000000000000000000000000

做

x |= x >> 8;

變成

111111111111111100000000000000000000000000000000

得到 16 個 bit 都是 1 以此類推經過

x |= x >> 16;

變成

111111111111111111111111111111110000000000000000

再用

x |= x >> 32;

變成

111111111111111111111111111111111111111111111111

這樣只要最後的 x + 1 就是大於原先 x 的 2 的最小的冪次方，很適合用於來找分配 memory best fit 要多大

用 __builtin_clzl 改寫

clz 就是 count leading zero 的意思，__builtin_clz(8)的返回值就是29，因為8的二進位制表示为0000 0000 0000 0000 0000 0000 0000 1000，其中前導0有2個9。

如果可以算前面有幾個 0 也可以很快地知道， most significant 的 1 在哪邊，可改寫成

uint64_t next_pow2_clz(uint64_t x)
{
    return 1<<(64 - __builtin_clzl(x));
}

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

運用

gcc -O2 -std=c99 -S next_pow2.c

編譯，可以看到以下 machine code

next_pow2_clz:
.LFB23:
    .cfi_startproc
    endbr64
    bsrq    %rdi, %rdi
    movl    $64, %ecx
    movl    $1, %eax
    xorq    $63, %rdi
    subl    %edi, %ecx
    sall    %cl, %eax
    cltq
    ret
    .cfi_endproc
.LFE23:

可以發現，編譯出來的 machine code 並沒有多做額外的 function call，還可以看到 brsq 這個指令

好奇 ctz 的其他類似指令， ctz , ffs 會給哪些 x86指令呢

ctz

bsfq

第二題

解釋 leet code 1680. Concatenation of Consecutive Binary Numbers

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 - 1)&i))
            len++;
        ans = (i | (ans << len)) % M;
    }
    return ans;
}

其中

if (!((i - 1)&i))
    len++;

是用來判斷是否為 2 的冪次方的判斷是，舉 16 為例
16 的 2 進位
10000
16 - 1 = 15 的 2 進位
01111
不難發現， 2 的冪次方與其 -1 的值完全沒有重複的 bit ，故其做 and operation 後必等於 0。
而

ans = (i | (ans << len)) % M;

表示每次要補上新的數字於 ans 後面時， ans 需要向左 shift len 的長度，騰出空間給新的數字

嘗試使用 __ builtin_{clz,ctz,ffs} 改寫

如果一個數字為 2 的冪次方，表示其寫成 2 進位必定為

00…001..00，只有一個1，只是不確定 1 座落在哪個 bit
可以用 clz (count leading zero) 跟 ctz (count trailing zero) ，加起來後的值判斷其是不是等於 bit length - 1， 如果是就代表 1 只有出現一次，為 2 的冪次方。

if((__builtin_clz(x) +  __builtin_ctz(x)) == 31)
    len++;

同理也可以用類似的概念 ffs (find first set) 來找到第一個 set (從右邊 lsb 數)的 1 ，搭配 clz 看兩者加起來是否等於 bit length 也會代表它就是 2 的冪次方

if((__builtin_clz(x) +  __builtin_ffs(x)) == 32)
    len++;