# 2023q1 Homework2 (quiz2)
ontributed by < `OWaitsInTime` >

## 測驗 1

uint64_t next_pow2(uint64_t x)
{
    x |= x >> 1;    //1
    x |= x >> 1;    //2
    x |= x >> 1;    //3
    x |= x >> 1;    //4
    x |= x >> 1;    //5
    x |= x >> 1;    //6
    x |= x >> 1;    //7
    x |= x >> 8;    //8
    x |= x >> 16;   //9
    x |= x >> 32;   //10
    return x + 1;   //11
}

假定 x = 0010000000000000 根據上述程式得下列結果
(用半形空格隔開方便閱讀)

x = 0010 0000 0000 0000
x = 0011 0000 0000 0000    //1
x = 0011 1000 0000 0000    //2
x = 0011 1100 0000 0000    //3
x = 0011 1110 0000 0000    //4
x = 0011 1111 0000 0000    //5
x = 0011 1111 1000 0000    //6
x = 0011 1111 1100 0000    //7
x = 0011 1111 1111 1111    //8
x = 0011 1111 1111 1111    //9
x = 0011 1111 1111 1111    //10
x = 0100 0000 0000 0000    //11

可以發現到程式目標是將最高位 ```1``` 右側所有位元變更為 ```1```

考慮此效果可以將程式修改為

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

### 用 ```__builtin_clzl``` 改寫

uint64_t next_pow2(uint64_t x)
{
int shift = 64 - __builtin_clzl(uint64_t x);
return 1 << shift;
}

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

從二進位表示觀察，確實發現在 2 的冪次方時 len 會增加 1 ， ```i & (i - 1)```可以用來判斷 i 是否為 2 的冪次方

0 = 0
1 = 1
2 = 10
3 = 11
4 = 100
5 = 101
6 = 110
7 = 111
8 = 1000

:::info
為何是 $mod 10^9+7$ ？
1.  $10^9+7$ 是一個質數
2.  int32 的最大值是 $2^{31} - 1$ ，所以對於 int32 來說 $10^9+7$ 足夠大
3.  int64 的最大值是 $2^{63} - 1$ ， $10^9+7$ 的平方不會在 int64 中溢出
4.  因為 ```(a∗b)%c=((a%c)∗(b%c))%c``` ， $mod 10^9+7$ 不會在  int64 中溢出
:::
### 用 ```__builtin_{clz,ctz,ffs} ``` 改寫
:::info
clz : Counting Leading Zero
ctz : Counting Trailing Zero
ffs : Find First Set
:::

int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    long ans = 0;
    
    for (int i = 1; i <= n; i++) {
        ans = (i | (ans << __builtin_ffsl(i))) % M;
    }
    return ans;
}

## 測驗 3

## 測驗 4

#include <stdint.h>
#include <stdbool.h>

bool is_pattern(uint16_t x)
{
    if (!x)
        return 0;

    for (; x > 0; x <<= 1) {
        if (!(x & 0x8000))
            return false;
    }

    return true;
}

for迴圈可以看出 pattern 為連續的 1 ，所給程式碼樣式可以明顯觀察到此結果(用半形空格隔開方便閱讀)

pattern: 8000 (1000 0000 0000 0000)
pattern: c000 (1100 0000 0000 0000)
pattern: e000 (1110 0000 0000 0000)
pattern: f000 (1111 0000 0000 0000)
pattern: f800 (1111 1000 0000 0000)
pattern: fc00 (1111 1100 0000 0000)
pattern: fe00 (1111 1110 0000 0000)
pattern: ff00 (1111 1111 0000 0000)
pattern: ff80 (1111 1111 1000 0000)
pattern: ffc0 (1111 1111 1100 0000)
pattern: ffe0 (1111 1111 1110 0000)
pattern: fff0 (1111 1111 1111 0000)
pattern: fff8 (1111 1111 1111 1000)
pattern: fffc (1111 1111 1111 1100)
pattern: fffe (1111 1111 1111 1110)
pattern: ffff (1111 1111 1111 1111)

### 可精簡成下方程式碼

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

以 ```1111 1111 0000 0000```為例，先取其 2 的補數

 x = 1111 1111 0000 0000
-x = 0000 0001 0000 0000

接著進行XOR運算

    x = 1111 1111 0000 0000
    n = 0000 0001 0000 0000
 -------------------------------
n ^ x = 1111 1110 0000 0000

在這種 pattern 下 ```(n ^ x)``` 一定會小於 ```x```

假設不是此種 pattern ，```(n ^ x)``` 就不會小於 ```x```

    x = 1111 1110 0001 0000
    n = 0000 0001 1111 0000
 -------------------------------
n ^ x = 1111 1111 1110 0000