# 2024q1 Homework4 (quiz3+4)
contributed by < `ChengChaoChun` >
## 第 3 周測驗題

### 測驗 3
題目要設計一個計算以2為底數的對數函式，返回整數。
版本一的實現是求得最後一個為1的位元的位置。如果要計算的值比較大，則 while 要執行很多次。
版本二採用類似 Binary Search 的方法，可以減少 while 執行的次數。
因為只是要計算近似值，因此可以計算左起第一個1之前0的個數來求得對數的近似值。

### 測驗 5
觀察測驗三版本二的部分程式和測驗五的部分程式，可以發現計算方式不同但是邏輯是一樣的。

// 測驗三 版本二 部分程式
while (i >= AAAA) {
    result += 16;
    i >>= 16;
}
while (i >= BBBB) {
    result += 8;
    i >>= 8;
}
while (i >= CCCC) {
    result += 4;
    i >>= 4;
}
while (i >= 2) {
    result += 1;
    i >>= 1;
}

測驗五多計算了 x 是否大於 3，而測驗三沒有計算 i 是否大於等於 4。

// 測驗五部分程式
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 的 x > GGG (1) 的部分

修改程式，計算結果同測驗三。

int ceil_ilog2(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 (r | shift | x > 1); //+ 1;       
}

與測驗三不同的地方是上取整後的結果，一開始將 x 減一，最後補加一。假設第一個要計算的是 $2^n$，第二個要計算的是 $2^n+1$。在測驗三中，顯然兩個最終結果相等，而在測驗五中，第二個數的結果應該要比第一個多 1。因此一開始把 x 減一，最後加一，來區分 x = $2^n$ 與 $2^n$ < x < $2^{n+1}$ 這兩個數的結果。
#### 處理 x = 0 的狀況，並仍是 branchless
在32位元的非負整數中只有當 x = 0 時執行 `x--` 後MSB會由0變為1。設置一個檢測位來檢測MSB是否由0變為1。只有 x > 0x80000000 的數與 0 最終結果會是 32。如果檢測位為 1 且最後結果是 32就把結果返回 0。(x=1還無法在brachless的情況下解決)

int ceil_ilog2(uint32_t x)
{
    uint32_t r, shift;
    uint32_t test_bit = (x >> 31) ^ 1;
    x--;
    test_bit &= x >> 31;
    printf("testbit : %d\n", test_bit);
    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 ((r | shift | x > 1) + 1) ^ (test_bit << 5);       
}

## 第 4 周測驗題
### 測驗 1
`popcount_branchless` 將一個 32 位元無號整數分成四個位元為 1 組，共 8 組來計算 popcount。
根據題目的推導，可以證明 popcount 的計算可以用下面數學式表達。
因為 `popcount_branchless` 以四個位元為 1 組，所以`popcount_branchless`的數學式表達如下。


關鍵的程式碼，解釋

n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;

1. 將輸入數值 v 除以 2，得到 $\lfloor\cfrac{v}{2}\rfloor$，第一行程式執行後結果如下

b_31 b_30 b_29 b_28 ... b7 b6 b5 b4 b3 b2 b1 b0  // v
   0 b_31 b_30 b_29 ...  0 b7 b6 b5  0 b3 b2 b1  // (v >> 1) & 0x77777777

因為 `popcount_branchless` 以四個位元為 1 組所以 v 右移一位之後還要 `& 0x77777777`。若沒有`& 0x77777777`結果如下。

b_31 b_30 b_29 b_28 ... b7 b6 b5 b4 b3 b2 b1 b0  // v
   0 b_31 b_30 b_29 ... b8 b7 b6 b5 b4 b3 b2 b1  // (v >> 1)

顯然每一組的最高位元的下一位若為 1 會影響該組的計算結果，因此要將右移後每一組的最高位元清零。

最終就可以計算出每一組的 popcount 了，每一格表示 1 個位元，以 4 bit 為 1 組。