2023q1 Homework2 (quiz2)

contributed by < WeiHongWi >

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

不用列出填空的標示，只要列出值得討論的程式碼。

jserv

已修改

HongWeiTue,Feb 28, 2023 8:35 PM

程式碼原理

將 number x 低於最靠近 most significant bit 且值為 1 的 bit 的所有 bit 都變成 1. 的binary representation 中最高位的「1」及其右側的所有位數都變成「1」, 此時可以得知 number x 為

$2^k-1$,

$k\in integer$ , 所以這時只要再加一就可以得到大於等於 number x 的最小 power of 2.

粗體字的部份我會在想想怎麼表達

ChatGPT 可幫助你

jserv

已修改

舉例來說：x = 01000…0000

x |= x >> 1 執行 7 次得到

x = 0x7f80000000000000,發現有 8 個 bits 值為1

x |= x >> 8 執行一次得到

x = 0x7fff800000000000,發現有16個 bits 值為1

x |= x >> 16 執行一次得到

x = 0x7fffffff80000000,發現有32個 bits 值為1

x |= x >> 32 執行一次得到

x = 0x7fffffffffffffff,發現此時目標達成 , 再 return x+1 則答案正確

利用 __builtin_clzl() 改寫

__builtin_clzl() : 回傳 binary representation 中最高位的「1」及其左側為零的位元數

想法為利用 unsigned 右移補值為0的性質, x | 0xfff…fff 得到全為1 , 並左移 __builtin_clzl(x)一次之後, 再右移一次 __builtint_clzl(x) 來得到低於最靠近 most significant bit 且值為1的 bit 的所有 bit 都變成 1binary representation 中最高位的「1」及其左側全為零

舉例來說 x = 000…0101 , __builtin_clzl(x) = 61

11111…111 << 61 = 111 … 000
111…000 >> 61 = 000 … 111

此時 ans = x+1 = 8

uint64_t next_pow2(uint64_t x)
{
   int number = __builtin_clzl(x);

   x |= 0xffffffffffffffff;
   x = x<<number;
   x = x>>number;

   return x+1;
}

和對應的 x86 指令

next_pow2:
.LFB23:
        .cfi_startproc
        endbr64
        bsrq    %rdi, %rcx
        movq    $-1, %rax
        xorq    $63, %rcx
        salq    %cl, %rax
        shrq    %cl, %rax
        addq    $1, %rax
        ret
        .cfi_endproc

---

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

程式碼原理

$mod$

$({10}^9+7)$ 還需要思考

1.DDDD = (i & (i-1)) ==0
i & (i-1) 可以用來判斷2種情況,是否為 2 的 power和 unsigner or signed number

2.EEEE = ans << len
舉例來說 x = 2

first loop
ans = (1 | (0)<<1) % M = 1

second loop
ans = (2 | 1 << 2) % M = 6

往左移動 len 個 bits 是為了裝下 i 的 binary representation

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

int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    int len = 0; /* the bit length to be shifted */

    long ans = 0;
    for (int i = 1; i <= n; i++) {
        // as all power of 2 only contains 1 set bit
        /*if (!(i^((i>>len)<<len)))
            len++;*/
        len = len + (__builtin_ffs(i)-1==len);
        ans = (i | (ans<<len)) % M;
    }
    return ans;
}

可以看到 len = len + (__ builtin_ffs(i)-1 == len) , __ builtin_ffs(i) 回傳 i 中最靠右且為1的 bit的位置. 假設為 x = 2,y=3 ,則 ___builtint_ffs(x) = 2, __builtint_ffs(y) = 1 , 可以發現除了 power of 2 以外的數的 __builtint_ffs() 都會小於 ___builtint_ffs(power of 2)，利用這個性質做到 i = power of 2 時才增加長度.

舉例來說,

i = 4 ,len = 2
__ builtin_ffs(4)-1 = 2 ==len
所以 len = len + 1 = 3

i = 5 , len = 3
則 __ builtin_ffs(5)-1 = -1 != len
所以 len = len + 0 = 3

.
.
.

i = 8 , len = 3
則 __ builtin_ffs(8)-1 = 3 == len
所以 len = len + 1 = 4

以此類推.

HongWeiTue,Feb 28, 2023 9:44 AM

---

測驗4

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

EEEE = ~(x)+1
FFFF = x

程式碼原理

is_pattern() 回傳此 uint16_t x 是否從 most significat bit 之後的 bits必須是連續的1.
舉例來說 0xfff0

0xfff1

x = 0xfff1 , n = 0x000f , n ^ x = 0xfffe , 則 n^x < x return false

還沒搞清楚為何要 +1 , 理解當中…

可以得知 n = ~(x)+1 為 x 的 negative number in 2's complement , 則 n ^ x 可以想成一個 bit mask, for example,使得能夠符合 pattern 的 number 可以遮住它 x 本身最靠右且為1的 bits.

HongWeiMon,Mar 6, 2023 3:04 PM

測驗5

測驗4

程式碼運作原理

int ceil_log2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;                 
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (KKKK) + 1;       
}

從 r = (x > 0xFFFF) << 4 , 可以知道看 x 是否大於 16 bits 最大的數 , 也就是說 x 是否需要 17 bits 以上來表示 , 若為true , 則此時

$log(x)$ 必定超過 16 , 也就是 r 現在的值 , 之後的 x >> r ,是要去考慮在 uint32_t x 中的前半的 16 個 bits.以此類推.

其中 x– 的設計 ， 使得剛好為 2 的次方數的 number 不會受到 return + 1 的影響

改進程式碼

首先可以發現當 x =1 , ceil_log2(x) = 1 , 這裡我認為以數學的定義來說,我認為是錯的,畢竟

$log(1)=0$ 且

$log(0)isundefined$, 所以我定義當輸入 x=0 和 x=1 時,答案變成 1.

將 x 代 0 進入 , x 變為

$2^{31}-1=4294967295$ , 所以答案變成 32.所以若要改善這個問題從 x– 這個 statement 下去考量.直觀的作法一定是用 if statement 去解決這個例外.

為了避免 x– 的寫法 , 我利用 __builtin_ctz() 來去計算最靠近尾端且 bit 值為1,我假設為第 y 個 bit,則為了做到 x- -, 則將 0~y-1 個 bits 都變成 1,而其餘的 bit 都變成 0, 這樣才能避免 overflow 的問題.

其中設計第 y-1 個 bit 也為 0 是因為利用 x ^= mask , 使得第 y 個 bit 因為 exclusive OR 而變成 0,舉例來說

x = 16 = 0x00000010₁₆ , __builtin_ctz(x) + 1 = 5
mask << 27 >> 27 = 0x0000001f
x ^= mask = 0x0000000f
來得到 x– 的效果且可以避免 overflow

int last_position = __builtin_ctz(x)+1;
uint32_t mask = 0xffffffff;
mask = mask << (32 - last_position);
mask >>= (32 - last_position);
x ^= mask;