# 2024q1 Homework4 (quiz 3+4)
contributed by < `LULser0204` >

### 第三週測驗 1
### 第三週測驗 2
### 第三週測驗 3
版本一 : 線性遞減法
原理 : 從輸入的整數 i 開始，每次將 i 右移一位 (相當於除以2)，直到 i 變為 0 。每次右移都將紀錄的對數值 log +1。
缺點 : 如果 i 很大，這個方法需要較多的跌代次數。

版本二: 分段遞減法
原理:先判斷 i 是否大於或等於一些特定的值(如65536、256、16、4、2)，並根據這些值將 i 右移不同的位數(如16、8、4、2、1)，每次右移後相應增加 result 的值。
效果 : 對於大數值，這個方法比版本一更高校，因為通過較大的跳躍來減少循環次數。

版本三:利用內建函式
參考 [GCC](https://gcc.gnu.org/onlinedocs/gcc-4.3.2/gcc/Other-Builtins.html#Other-Builtins) 官方手冊中， __builtin_clz 的註解

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

回傳最高有效位 1 之前 0 的數量。

分別可用於 unsigned int ， unsigned long 以及 unsigned long long

以這題為例，如果 v 是 15，要用4個位元去表示它，由於傳入的是 uint32_t ，故會返回 28

原理 : 通過計算 31 - __builtin_clz(v|1) ，實質上計算了從最高位的 1 到最低位之間的 bit 數
特點 : 對於輸入 0 是未定義行為，需要通過 v|1 來保證輸入不為0

#### Linux 核心應用案例
在[linux/include/linux/log2.h](https://github.com/torvalds/linux/blob/master/include/linux/log2.h) 可以找到 log2 的相關程式碼

##### __ilog2_u32 和 __ilog2_u64 的程式碼和註解

這兩個函式計算一個無號整數(32 bits 和 64 bits)的對數。他們兩個使用到 fls() fls64() 可以在 [include/asm-generic/bitops](https://github.com/torvalds/linux/tree/master/include/asm-generic/bitops) 看到，分別找到最高位的 1 的位置，然後 -1 來取得對數值。
之所以 -1 可以從老師這篇文章 [Linux 核心專題: 回顧 bitops 並改進](https://hackmd.io/@sysprog/ByS9w_lHh#%E4%BB%BB%E5%8B%99%E7%B0%A1%E8%BF%B0) 得知：

__XXX 系列: 以 index 0 索引，範圍為 0 ~ {length of input type - 1}
XXX 系列: 以 index 1 索引，範圍為 1 ~ {length of input type}

應用場景:確定一個變數占用的 bit 數，從而決定最小的儲存單位。
在作業系統配置記憶體時，要確保 Alignment 。使用這兩個函式協助給定大小最接近的 2 的冪次，從而實現更有效的記憶體配置。

##### is_power_of_2

通過檢查 (n & (n - 1) 是否為 0 ，來看它是不是2的冪次。(由於2的冪次只會有一個位元是 1 )

2^0 : 0001    &     0001 - 1 = 0000
2^1 : 0010    &     0010 - 1 = 0001
2^3 : 1000    &     1000 - 1 = 0111

應用場景 : 通常記憶體配置時都是以 block 為單位，這些 block 大小是2的冪次。如此系統可以快速檢查記憶體大小是否為 2 的冪次，以決定是否可以直接滿足請求或需要調整。

##### __roundup_pow_of_two 和 __rounddown_pow_of_two

這兩個函式分別將給定的值向上或向下取整到最近的 2的冪次。通過尋找最高位的1的位置

應用場景:動態調整陣列大小，當陣列容量不足以容納更多元素時，需要進行擴充。(如 C++ 的 vector ) 動態調整 buffer 大小

##### const_ilog2

這個函式用於計算 32/64 bits 常數無號值的對數。主要用於陣列索引

##### ilog2

這個函式也是計算對數(以2為底)，可以根據 n 的大小選擇合適的優化版本。如(__ilog2_u32 或 __ilog2_u34 )
註解有提到用於初始化全局變數。相比於 const_ilog2 使用上更加靈活

const_ilog2 和 ilog2 使用上的選擇:
const_ilog2 :當確定需要處理的是 Complile-time Constant
ilog2 : 當需要處理來自不同來源的數據，每個數據大小在運行時才知道。想要根據每塊大小去做動態分配一個足夠的的 buffer

##### roundup_pow_of_two 和 rounddown_pow_of_two

兩者和 __roundup_pow_of_two 以及 __rounddown_pow_of_two相似，但它提供了用於 Complile-time Constant 的能力。當你不確定處理的值是 Complile-time Constant 或者是需要在編譯時優化的場景。

例如:靜態初始化需要對齊到 2 的冪次邊界的資料

##### __order_base_2 和 order_base_2

計算給定值的(向上取整數) 2的基數

這兩個函式差別類似於 " __roundup_pow_of_two "、" roundup_pow_of_two "，後者有針對 Complile-time Constant 的場景優化

例如:當你正在設計一個記憶體管理區塊，需要根據請求的記憶體大小動態分配記憶體空間，而分配的大小必須是 2 的冪次

##### __bits_per 和 bits_per

準確計算給定值所需的 bits 數。

應用場景 : 在檔案壓縮過程中， bits_per 可以用來確定儲存特定數值所需的最少位數，從而實現更有效的壓縮策略。例如：如果一個壓縮對象值範圍是　０～１０００，那麼可以使用 bits_per(1000)來計算

### 第三週測驗 4
### 第三週測驗 5

### 第四週測驗 1
### 第四週測驗 2
### 第四週測驗 3