# 2023q1 Homework2 (quiz2)
contributed by < [WeiHongWi](https://github.com/WeiHongWi/quiz2/tree/master) >

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

</s>

:::warning
不用列出填空的標示，只要列出值得討論的程式碼。
:notes: jserv
> 已修改
:::
> [name=HongWei][time=Tue,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.
:::info
粗體字的部份我會在想想怎麼表達
> ChatGPT 可幫助你
> :notes: 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 都變成 1~~binary 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

以此類推.

> [name=HongWei][time=Tue,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 :+1: 0xfff1:-1:

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.

> [name=HongWei][time=Mon,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)~is ~undefined$, 所以我定義當輸入 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~16~ , __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;