# 2024q1 Homework4 (quiz3+4)
contributed by < [ Daniel-0224 ](https://github.com/Daniel-0224) >
## 第三周測驗
### 測驗三
**版本一**
使用右移操作來計算 `msb` 在第幾位，以此當作 `log` 值，而計算 `msb` 也可以藉由計算 `i` 的 `counting leading zero` 來達成。

**版本二**
先判斷 `i` 是否大於 $2 ^ {16}$ ，若是則繼續往 `i` 是否大於 $2 ^ {24}$ 判斷，若不是則判斷 `i` 是否大於 $2 ^ {8}$ ，以此類推，原理其實就是二分搜尋，在32位元中找到 `msb` 。

### 測驗四

### 測驗五
測驗五原理與測驗三大致相同，也是利用二分搜法找出 `msb` ，`x--` 是為了正確運算2的冪，像是 `x = 0x80` 需要先減一在 `return` 時加一取的正確的 $\lceil {\log(x)} \rceil$ ，而 這裡的`r` 等於測驗三的 `result` ，`r ｜＝ shift` 等於 `r + shift` 因為 `r` 與 `shift` 都是2的冪，可以 `｜` 代替 `＋`。

**改進程式碼：**
將 `x--` 改成以下寫法可以使處理 `x = 0` 的狀況，並仍是 `branchless`。
這是在 `linux kernel` `likely` 巨集中學會的，使的 `x` 一定是 `0` 或 `1` 。

但程式碼還是有以下問題，當輸入為 `0` 或 `1` 時，輸出都是`1`，但根據數學定義，$\log(1) = 0$，而 $\log0$ 是未定義的，這部分還不知道怎麼改進。

#define likely(x)    __builtin_expect(!!(x), 1)

int ceil_ilog2(uint32_t x)
{
-    x--;
+    x -= !!x;
}

後來想到了方法解決上述的問題，若是將原本測驗題程式碼中 `x--` 及 `return (r | shift | x > 1) + 1;` 改成 `return (r | shift | x > 1);` ，就會變成 `floor_ilog2` ，除了2的冪是正確的其他都比正確值少1，因此先判斷 `x` 是否為2的冪，若是則 `return` 不加1，不是則加1，解決了前面的問題而且還維持得以處理 `x = 0` 的狀況，並仍是 `branchless`。

int ceil_ilog2(uint32_t x)
{
-   uint32_t r, shift;
+   uint32_t r, shift, p;
    
-   x -= !!x; 
+   p =  (((x & (x - 1)) == 0));
    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; 
+   return (r | shift | x > 1) + (!p & 1);

}

In linux kernel:

這是我在 `include/linux/sched.h` 中找到與 `log` 相關的程式碼，但不太了解程式碼在做甚麼。 但我想 `1 + ilog2(TASK_REPORT_MAX)` 是 `ceil` 與 `log` 的組合。

static inline char task_index_to_char(unsigned int state)
{
	static const char state_char[] = "RSDTtXZPI";

	BUILD_BUG_ON(1 + ilog2(TASK_REPORT_MAX) != sizeof(state_char) - 1);

	return state_char[state];
}

## 第四周測驗
### 測驗一
函式 `popcount_naive()` 不斷清除 `LSB` 直到輸入的數值 `v` 為 0，而 `n = -(~n)` 等同 `n++` ，因為在二補數系統中，$-n = \sim n+1$ ，$- (\sim n) = n + 1$ 。

`popcount` 可以寫成以下公式：
$popcount(x) = x - \lfloor \dfrac{x}{2} \rfloor - \lfloor \dfrac{x}{4} \rfloor - \lfloor \dfrac{x}{8} \rfloor - ... - \lfloor \dfrac{x}{2^{31}} \rfloor = \sum\limits_{n=0}^{31}(2^n - \sum\limits_{i=0}^{n-1}2^i)b_n = \sum\limits_{n=0}^{31}b_n$

**程式碼：**
1. `n = (v >> 1) & 0x77777777` 將輸入 `v` 除以2，得 $\lfloor \dfrac{v}{2} \rfloor$ ，`& 0x77777777` 以每 4 個位元 (nibble) 為一個單位計算 1 的個數。
2. `v = (v + (v >> 4)) & 0x0F0F0F0F` ，將每 4 個位元中 set bit 的個數加到 byte 中。

假設 $Bn$ 代表第 n 個 nibble (4 位元) 中的數值

// v
B7 B6 B5 B4 B3 B2 B1 B0  

// (v + (v >> 4))
B7 (B7+B6) (B6+B5) (B5+B4) (B4+B3) (B3+B2) (B2+B1) (B1+B0)

// (v + (v >> 4)) & 0x0F0F0F0F
0 (B7+B6) 0 (B5+B4) 0 (B3+B2) 0 (B1+B0)

透過 `v *= 0x01010101` 將各個 `nibble` 相加

A6 = B7+B6, A4 = B5+B4, A2 = B3+B2, A0 = B1+B0

                         0 A6  0 A4  0 A2  0 A0
                      x  0  1  0  1  0  1  0  1
---------------------------------------------------
                         0 A6  0 A4  0 A2  0 A0
                   0 A6  0 A4  0 A2  0 A0  0
             0 A6  0 A4  0 A2  0 A0  0
       0 A6  0 A4  0 A2  0 A0  0
---------------------------------------------------
                            ↑_______________________A6+A4+A2+A0

`return v >> 24` : 最後得到的結果會放在 Most significant byte 中，因此向右位移 24 位元，即為所求的 popcount 值。

**改善程式碼：**

int totalHammingDistance(int8 nums, int numsSize){
    int total = 0;
    for(int i = 0; i < 32; i++){
        int ones = 0, zeros = 0;
        for(int n = 0; n < numsSize; n++){
            if((nums[n] >> i) & 1){
                ones++;
            } else {
                zeros++;
            }
        }
        total += ones*zeros;
    }
    return total;
}

| n'th bit | 3 | 2 | 1 | 0 |
|:--------:| --- | --- | --- | --- |
| 4 | 0 | 1 | 0 | 0 |
| 14 | 1 | 1 | 1 | 0 |
| 2 | 0 | 0 | 1 | 0 |

第 0 bit :
zeros = 3; ones = 0; total = 0;
第 1 bit :
zeros = 1; ones = 2; total = 2;
第 2 bit :
zeros = 1; ones = 2; total = 2;
第 3 bit :
zeros = 2; ones = 1; total = 2;
total HammingDistance = 6.

### 測驗二