# 2023q1 Homework3 (quiz3)
contributed by<[WeiHongWi](https://github.com/WeiHongWi/quiz3)>
## 測驗3
### 程式碼運作原理

### 找到 $log$ 的相關實作

### 解釋 [lab0-c/log2_lshift16.h](https://github.com/sysprog21/lab0-c/blob/master/log2_lshift16.h)

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