# 2024q1 Homework4 (quiz3+4)
contributed by < [Ackerman666](https://github.com/Ackerman666) >
## 第三週測驗題
### [測驗 `2`](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-2)
#### 解釋運作原理
參考 [Hacker's Delight](https://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf)，採用 bitwise operation 來實作，可比用 division operator 來得有效率
考慮到 $\frac{n}{10}$，可以找到一組算式來逼近結果 : $n \times \frac{a}{2^{N}}$，而題目在此挑選 a = 13, N = 7
```c
void divmod_10(uint32_t n, uint32_t *div, uint32_t *mod)
{
unsigned d0 = n & 0b1;
unsigned d1 = n & 0b11;
unsigned d2 = n & 0b111;
*div = ((((n >> 3) + (n >> 1) + n) << 3) + d0 + d1 + d2) >> 7;
*mod = n - (((*div << 2) + *div) << 1);
}
```
$n \times \frac{13}{2^{7}}$ 可改寫成 $n \times 13 \div 8 \div 16$，而 $n \times 13 \div 8$ 可用下面式子求得
((n >> 3) + (n >> 1) + n) << 3
但除法位移過程中，會遺失後面三個位元的數值，所以用三個變數來保留該資訊
d0 = n & 0b1;
d1 = n & 0b11;
d2 = n & 0b111;
將遺失的數值加回去，再除以16
q = ((((n >> 3) + (n >> 1) + n) << 3) + d0 + d1 + d2) >> 7;
最後再由餘數定理來求得餘數
r = n - (((q << 2) + q) << 1);
#### 不依賴任何除法指令的 modulo 5
觀察以下規律，可以看出底數為2時，指數每 4 個數在 mod 5 的情況下會完成一次循環
> $2^0$ mod 5 = 1
> $2^1$ mod 5 = 2
> $2^2$ mod 5 = 4
> $2^3$ mod 5 = 3
> $2^4$ mod 5 = 1
> $2^5$ mod 5 = 2
> ...
因此可以建 `table[32]` 紀錄$2^i$ mod 5 的數值
```c
int table[32] = {1,2,4,3,
1,2,4,3,
1,2,4,3,
1,2,4,3,
1,2,4,3,
1,2,4,3,
1,2,4,3,
1,2,4,3,};
```
對於每個整數 n，皆可以用 2 的冪次相加來代表
因此可以逐一檢查 n 的每個位元，如果為 1 就查表並將數值加進 `mod`
`!!((5 - mod - 1) & 0x80000000)` 用來判斷當前 `mod` 有沒有 >= 5，如有，則將 5 減去
```c
int mod = 0, index = 0;
while(n){
mod += (n & 0b1) * table[index];
mod -= !!((5 - mod - 1) & 0x80000000) * 5;
n = n >> 1;
++index;
}
```
#### 不依賴任何除法指令的 modulo 9
同 modulo 5 觀察規律
> $2^0$ mod 9 = 1
> $2^1$ mod 9 = 2
> $2^2$ mod 9 = 4
> $2^3$ mod 9 = 8
> $2^4$ mod 9 = 7
> $2^5$ mod 9 = 5
> $2^6$ mod 9 = 1
> ...
建 `table[36]` 紀錄$2^i$ mod 9 的數值
```c
int table[36] = {1,2,4,8,7,5,
1,2,4,8,7,5,
1,2,4,8,7,5,
1,2,4,8,7,5,
1,2,4,8,7,5,
1,2,4,8,7,5};
```
後續求餘過程和 modulo 5 類似
> 完整程式碼 : [2b59e70](https://github.com/Ackerman666/quiz3-4/commit/2b59e7062c9c32628e2243df9a2716499af3be35)
#### 實驗
我將自定義的 `mod5` 和 `mod9` 分別執行 1000000 次，並用 perf 進行分析
166.60 msec task-clock # 0.998 CPUs utilized
2 context-switches # 12.005 /sec
0 cpu-migrations # 0.000 /sec
50 page-faults # 300.118 /sec
7,6166,0412 cycles # 4.572 GHz
8,8298,9060 instructions # 1.16 insn per cycle
9573,2445 branches # 574.620 M/sec
813,6217 branch-misses # 8.50% of all branches
`i % 5` 和 `i % 9` 分別執行 1000000 次
2.15 msec task-clock # 0.842 CPUs utilized
0 context-switches # 0.000 /sec
0 cpu-migrations # 0.000 /sec
50 page-faults # 23.296 K/sec
662,0116 cycles # 3.084 GHz
398,7849 instructions # 0.60 insn per cycle
117,7528 branches # 548.642 M/sec
5953 branch-misses # 0.51% of all branches
可看出自定義函式執行速度最慢，原因是函式有用到 while 迴圈，導致 branches 數量大增 (待改進)
### [測驗 `3`](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-3)
#### 解釋運作原理
透過將 `i` 不斷往右 shift，可以得到 `i` 最高 set bit 為 1 的索引
該索引即是$\log_2 i$ 取整結果
```c
int ilog2(int i)
{
int log = -1;
while (i) {
i >>= 1;
log++;
}
return log;
}
```
透過 binary search 的方式，來加速尋找最高 set bit 的過程
> 設 i = fx00FFFFFF
> i >= 65536，代表最高 set bit 的索引 >= 16
> 將 result + 16，並對 i 往右位移 16 位元，並往下進行後續判斷，來找到最高 set bit 所在索引
```c
static size_t ilog2(size_t i)
{
size_t result = 0;
while (i >=65536) {
result += 16;
i >>= 16;
}
while (i >= 256) {
result += 8;
i >>= 8;
}
while (i >= 16) {
result += 4;
i >>= 4;
}
while (i >= 2) {
result += 1;
i >>= 1;
}
return result;
}
```
透過 gcc 內建 `__builtin_clz(unsigned int x)` 實作
>Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
>
>計算 leading 0-bits 個數，x = 0 時未定義
```c
int ilog32(uint32_t v)
{
return (31 - __builtin_clz(v | 1));
}
```
`__builtin_clz(v | 1)` 讓傳遞進的參數值至少為1，來避免未定義情況。而 v | 1 並不會影響正確性
因 `__builtin_clz(v)` 和 `__builtin_clz(v | 1)` 在 v 不等於 0 時結果都一樣
> v = 0010$_2$ leading 0-bits 數量為 2
> v|1 = 0011$_2$ leading 0-bits 數量也為 2
透過 `31 - __builtin_clz(v | 1)` 可得左邊數來第一個位元為 1 的索引，索引即是 $\log_2 v$ 取整結果
#### 在 linux 核心相關實作
在 [linux/log2.h](https://github.com/torvalds/linux/blob/master/include/linux/log2.h) 中可看到相關程式碼
#### `__ilog2_u32` 與 `__ilog2_u64`
> non-constant log of base 2 calculators
`fls` 定義在 [linux/include/asm-generic/bitops/fls.h](https://github.com/torvalds/linux/blob/master/include/asm-generic/bitops/fls.h) 為 `generic_fls` 的巨集
以下是 `generic_fls` 註解，可以看到返回的 most-significant bit set 位置是由 1 開始作計算
/**
* generic_fls - find last (most-significant) bit set
* @x: the word to search
*
* This is defined the same way as ffs.
* Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
*/
而因為對數取底是由 0 開始，因此求得的 `fls(n)` 要減去 1
```c
#ifndef CONFIG_ARCH_HAS_ILOG2_U32
static __always_inline __attribute__((const))
int __ilog2_u32(u32 n)
{
return fls(n) - 1;
}
#endif
```
**疑惑**
:::info
generic_fls 為何不要直接用 fls 來命名就好 ?
:::
#### `const_ilog2` :
常數版本的 `ilog2`
**疑惑**
:::success
原始碼是直接列出所有可能情況來找到最高 set bit
我認為是有特殊理由才會這樣處理，但我目前尚未找到解釋
最後看到老師提供的[解釋](https://www.facebook.com/groups/system.software2024/permalink/1575264409918118/)，主要是編譯器可透過 CSE 一類的最佳化手法來消除該複雜敘述
:::
#### 應用案例
[linux/lib/math/div64.c](https://github.com/torvalds/linux/blob/486291a0e6246364936df1ecd64c90affef4b9c5/lib/math/div64.c#L193) 中的 `mul_u64_u64_div_u64`
該函式有三個 u64 型別的變數 (a, b, c)，函數功能即計算 a * b / c
>u64 根據 [linux/arch/powerpc/boot/types.h](https://github.com/torvalds/linux/blob/master/arch/powerpc/boot/types.h#L12) 實際上為 unsigned long long
因為 a * b 有可能會溢位，函式有作對應的處理，條件判斷就有用到 `ilog2`
/* can a * b overflow ? */
if (ilog2(a) + ilog2(b) > 62)
> ilog2(a) = 60 $\rightarrow$ a 數值可用 61 個位元表示
> ilog2(b) = 3 $\rightarrow$ b 數值可用 4 個位元表示
> a * b 最多會需要 65 位元來表示
> 因此上述程式碼才會用大於 62 當作是否會溢位的標準
### [測驗 `5`](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-5)
#### 解釋運作原理
`r |= shift` 的功用與 `ilog2` 的 `result` 一樣，都是去紀錄最高 set bit 所在索引
過程中 `r` 與 `shift` 皆為２的冪次，因此兩者相加可用 `|` 實現
回傳值 `x > 1` 是為了應對 x 是否等於 0x2 的情況，是則必須將原先得到的結果 `r |= shift` 再加 1
`x--` 則是用來應對 x 為２的冪次情況，與回傳值後面的加 1 相抵銷，來使結果是正確的
#### 改進程式碼
對 0 取對數沒有定義，因此我讓函式遇到 0 時會回傳 -1
對 1 取對數要是為 0 ，但原先程式碼會回傳 1 , 因此我進行改寫來作正確的處理
增加兩個變數
* `is_zero` : 判斷 `x` 是否為 0
* `gt_one` : 判斷 `x` 是否大於 1
將 `x--`，修正成 `x -= !!x`，避免 x = 0 時的溢位狀況
`(r | shift | x > 1)` 在 x = 0 ， x = 1 時為 0，加入兩個表達式 : `(1 & gt_one)` 與 `(1 & gt_one)`
前者會確保當 `x` = 1 時，回傳為 0，後者確保當 `x` = 0 時，回傳為 -1
```diff
int ceil_ilog2(uint32_t x)
{
uint32_t r, shift;
+ bool is_zero, gt_one;
+ is_zero = !x;
+ gt_one = x > 0b1;
- x--;
+ x -= !!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 > GGG) + 1;
+ return (r | shift | x > 1) + (-is_zero) + (1 & gt_one);
}
```
## 第四週測驗題
### [測驗 `1`](https://hackmd.io/@sysprog/linux2024-quiz4#%E6%B8%AC%E9%A9%97-1)
#### 針對 [LeetCode 477. Total Hamming Distance][(https://](https://leetcode.com/problems/total-hamming-distance/description/)) 撰寫出高效程式碼
用 `totalHammingDistance` 來解這題的話，需兩兩配對計算 hamming distance，複雜度為 $\mathcal{O}(n^2)$
```graphviz
digraph G {
node [shape=plaintext];
rankdir=LR;
Table [
label=<
<table border="1" cellborder="1" cellspacing="0">
<tr><td colspan="7">Sample Table</td></tr>
<tr>
<td>n'th bits</td>
<td>3</td>
<td>2</td>
<td>1</td>
<td>0</td>
</tr>
<tr><td>input 7</td><td>0</td><td>1</td><td>1</td><td>1</td></tr>
<tr><td>input 5</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><td>input 10</td><td>1</td><td>0</td><td>1</td><td>0</td></tr>
<tr><td>input 15</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
</table>
>,
];
}
```
以上面表格而言，共有 4 個輸入 (7, 5, 10, 15)
考慮所有輸入的第三個位元
>位元為 1 的有 3 個，為 0 的有 1 個，那麼該位置的 Hamming Distance 加總就為 3 * 1 = 3
考慮所有輸入的第二個位元
>位元為 1 的有 2 個，為 0 的有 2 個，那麼該位置的 Hamming Distance 加總就為 2 * 2 = 4
由此規律先計算每個位元 0 和 1 的個數，再進行相乘，再把結果紀錄在Total Hamming Distance
#### 實作 (版本1)
透過 `ones` 陣列儲存對所有輸入，在第 i 個位元為 1 的加總
最後跑過整個 `ones` ，透過 `ans += (numsSize - ones[i]) * ones[i]` 算出答案
```c
int totalHammingDistance(int* nums, int numsSize) {
int ans = 0, ones[32] = {0};
for(int i=0 ; i<numsSize ; i++){
int num = nums[i], index = 0;
while(num){
ones[index] += num & 0b1;
num = num >> 1;
++index;
}
}
for(int i=0 ; i<32 ; i++)
// ((numsSize - zero[i])) the count of "0"
ans += (numsSize - ones[i]) * ones[i];
return ans;
}
```
#### (版本2)
用兩層迴圈從第一個位元開始檢查，一累加完個數就更新 `ans`
此作法不用額外空間，空間複雜度為 $\mathcal{O}(1)$
```c
int totalHammingDistance(int* nums, int numsSize) {
int ans = 0;
for(int i=0 ; i<32 ; i++){
int ones = 0;
for(int j=0 ; j<numsSize ; j++)
ones += nums[j] >> i & 0b1;
// (numsSize - ones) the count of "0"
ans += (numsSize - ones) * ones;
}
return ans;
}
```
兩種做法皆會對每個輸入的所有位元跑過一次，而 int 為 32 bits
假設 n 為輸入筆數，因此迴圈執行次數最多是 32 * n，複雜度為 $\mathcal{O}(n)$
Sign in with Wallet
Connect another wallet