# 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

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 的數值

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 減去

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 的數值

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$ 取整結果

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 所在索引

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 時未定義

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

#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

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)$

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]` 算出答案

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)$

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)$