# 2023q1 Homework2 (quiz2)
contributed by < [WeiHongWi](https://github.com/WeiHongWi/quiz2/tree/master) >
## 測驗1
```c
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
```c
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
```c
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}` 改寫
```c
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
```c
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
### 程式碼運作原理
```c=
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
```c=
int last_position = __builtin_ctz(x)+1;
uint32_t mask = 0xffffffff;
mask = mask << (32 - last_position);
mask >>= (32 - last_position);
x ^= mask;
```