---
tags: linux2022
---

# 2022q1 Homework2 (quiz2)
contributed by < `MicahDoo` >

# 測驗 1

## 第一部分

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (EXP1);
}

首先看到 `>> 1` 立刻想到 `/ 2`，所以很顯然這個實作是先對兩個數字作個別 `int` 除二的動作，加起來，再加上 `EXP1`。
關於整數型別除法，要切記的是：
* `int` 除法不只會造成資訊損失，「除越多次損失得可能越多」。
* 同理，右移 `>>` 的運算也是一樣。

從以上實作可以看到，從原本「先加起來，最後統一除二」，到「先各自除二，再加起來」，多了一次 `>> 1` / `/ 2` ，因此要考慮到多了這次右移 / 除法，多損失了什麼。

由於 右移一位 / 除二 只會造成最右一個位元的損失，所以可以對兩個數字的最小一位元直接做討論：

* 都是 `0`：對結果並不會有影響，因為加起來後最後一位仍然是零。不論先除後除都不會損失資訊。
* 只有一個 `1`：對結果仍然不會有影響，因為不管先除還後除都只會損失 1。
* 兩者都是 `1`：由於兩者加起來後會進位，最後一位會變成 `0` 。因此若先除會損失兩個 `1` ，後除不會損失資訊。

由以上推理可知，若兩者的最後一位都是 `1` ，則要加回 `(1 + 1) / 2` 也就是 `1` 的數值。其他則不用加任何東西，有就是「加零」：

| | 0 | 1 |
|:---:|:---:| --- |
| 0 | 0 | 0 |
| 1 | 0 | 1 |

...此為 AND 的真值表。

另外，跟 `1` 做 AND 可以將第一位以外的資訊全部歸零。畢竟第一位以外的資訊已經透過`(a >> 1) + (b >> 1)`取得。

答案為：

`EXP1`: `a & b & 1`

## 第二部分

uint32_t average(uint32_t a, uint32_t b)
{
    return (EXP2) + ((EXP3) >> 1);
}

由於題目說到，`EXP2` 和 `EXP3` 僅有 `a` 和 `b` 的邏輯運算（無移位），又觀察到 `EXP2` 並無移位， `EXP3` 卻有，馬上得到了以下的結論：
1. `EXP2` 應該和加法進位的部分有關聯：進位等於是影響到左邊那一位，但除二後又回到原本這個位元。
2. `EXP3` 則是沒進位的部分，其位置跟著除二的部分向右移了一位。

得出以上結論後，便對二進位相加的進位情況做了討論：

| | 0 | 1 |
|:---:|:---:| --- |
| 0 | 00 | 01 |
| 1 | 01 | 10 |

分開討論本位及高一位的情況：

本位（對應到 `EXP3`）：

| | 0 | 1 |
|:---:|:---:| --- |
| 0 | 0 | 1 |
| 1 | 1 | 0 |

此為 XOR

高一位（對應到 `EXP2`）：

| | 0 | 1 |
|:---:|:---:| --- |
| 0 | 0 | 0 |
| 1 | 0 | 1 |

此為 AND

因此答案：

`EXP2`: `a & b`
`EXP3`: `a ^ b`

:::success
延伸問題:

- [ ] 解釋上述程式碼運作的原理
- [ ] 比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 ([可研讀 CS:APP 第 3 章](https://hackmd.io/@sysprog/CSAPP-ch3))
- [ ] 研讀 Linux 核心原始程式碼 [include/linux/average.h](include/linux/average.h)，探討其 [Exponentially weighted moving average (EWMA)](https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average) 實作，以及在 Linux 核心的應用
>移動平均（Moving average)，又稱滾動平均值、滑動平均，在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數，來分析資料點的計算方法。
移動平均通常與時間序列資料一起使用，以消除短期波動，突出長期趨勢或周期。短期和長期之間的[閾值](https://terms.naer.edu.tw/detail/1085244/)取決於應用，移動平均的參數將相應地設置。例如，它通常用於對財務數據進行技術分析，如股票價格、收益率或交易量。它也用於經濟學中研究國內生產總值、就業或其他宏觀經濟時間序列。
:::
:::success
延伸閱讀：

- [ ] [Introduction to Low Level Bit Hacks](https://catonmat.net/low-level-bit-hacks)
:::

# 測驗 2

#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((EXP4) & -(EXP5));
}

首先觀察：本實作是以 `a` 為出發點，若 `a >= b` ， 跟 `(EXP4) & -(EXP5)` 做 XOR 後的結果就是 `a` 自己，若否，則結果會是 `b`。
若從位元的角度來看，若 `a >= b` ， 則 XOR 的結果必為自己， 若否，則 XOR 的結果不一定，要看 `b` 在該位元的值。

那就來看 XOR 的真值表：

| XOR | 0 | 1 |
|:---:|:---:| --- |
| 0 | 0 | 1 |
| 1 | 1 | 0 |

從上表可得出以下的結論：

* 若 `a >= b`，`(EXP4) & -(EXP5)` 一定要是 `0`， 否則 XOR 的結果不會跟原本相同（ `a` 本身）。

| XOR | 0 | 1 |
|:---:|:---:| --- |
| **0** | **0** | **1** |
| 1 | 1 | 0 |

* 若 `a < b`, 則為讓 XOR 的結果為 `b`， `(EXP4) & -(EXP5)` 中在 `a` 之位元為 `0` 的位置，其值與 `b` 同， 在 `a` 之位元為 `1` 的位置， 其值與 `b` 相反。如此是因為 `1` 在 XOR 中有翻轉 (flip) 位元的功能， `0` 則有維持原貌的功能。

討論 `a` 大的情況：

`(EXP4) & -(EXP5) == 0`。
由於 `EXP5` 是比較式，大膽猜測若 `a >= b` 或 `a > b`，會造成 `-(EXP5) == 0`，的結果，導致整個式子為零：
* 若 `-(EXP5) == 0`，`EXP5 == 0`，即 `EXP5` 之敘述為否，可知應為 `a < b` 或 `a <= b`。
* 另一方面，`EXP5` 之敘述為真， `EXP5 == 1`， `-(EXP5) == -1`， 其二補數表示為「全 1」。由於是全 1，其對任何數值做 AND 後並不會對結果有影響，因此 `EXP4` 的長相完全取決於另一個情況。

`b` 大的情況：

直接畫真值表來討論我們要的情況：

| a\b | 0 | 1 |
|:---:|:---:| --- |
| 0 | 0 | 1 |
| 1 | 1 | 0 |

`a` 之該位元為 0 時，`EXP4` 的該位元同 `b` ，反之則不同。
可以看到其結果為 `a` 和 `b` 做 XOR。

答案為：

`EXP4`: `a ^ b`
`EXP5`: `a < b`

:::warning
其實當中可以看到 XOR 的特性：
a XOR b XOR a = b
也就是做兩次 XOR 如果其中一個元素出現兩次，那他就會被抵消，留下沒有重複那個元素。
本題也用到了這個特性，先將 `a ^ b` 做出來，等到需要的時候再做 `a ^ (a ^ b) == b`，把 `b` 提取出來。
判斷奇數偶數、 XOR 串列、無分支程式碼也都是利用這個特性。倘若看到 XOR 能掌握這個特性，這題應該能秒解。

digraph G{
    node [fontname="Courier"]
    edge [fontname="Courier New" label = "^ b"]
    rankdir = LR
    a:n->"a ^ b":n
    "a ^ b":s->a:s 
}

:::

:::warning
改進處：

`EXP5` 的 `a < b`可以寫成 `(a - b) >> 31` 的形式？
若 a 大，則 `a - b` 的 sign bit 為 0，右移 31 位後便為 0。
若 a 小，則 `a - b` 的 sign bit 為 1，右移 31 位後便為 1。

:::

:::success
延伸問題:

- [ ] 解釋上述程式碼運作的原理
註：對 `BranchA ^ ((BranchA ^ BranchB) & -(BranchBCondition))` = `BranchBCondition ? BranchB : BranchA` 的 Branchless programming 多做描述。
- [ ] 針對 32 位元無號/有號整數，撰寫同樣 [branchless](https://en.wikipedia.org/wiki/Branch_(computer_science)) 的實作
- [ ] Linux 核心也有若干 branchless / branch-free 的實作，例如 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c):

    /*
     * Logically, we're doing "if (i & lsbit) i -= size;", but since the
     * branch is unpredictable, it's done with a bit of clever branch-free
     * code instead.
     */
    __attribute_const__ __always_inline
    static size_t parent(size_t i, unsigned int lsbit, size_t size)
    {
        i -= size;
        i -= size & -(i & lsbit);
        return i / 2;
    }

請在 Linux 核心原始程式碼中，找出更多類似的實作手法。請善用 `git log` 檢索。
:::

:::success
延伸閱讀：
- [ ] [That XOR Trick](https://florian.github.io/xor-trick/)
- [ ] [Branchless Programming: Why “If” is Sloowww… and what we can do about it!](https://youtu.be/bVJ-mWWL7cE)
- [ ] [Making Your Code Faster by Taming Branches](https://www.infoq.com/articles/making-code-faster-taming-branches/)

https://stackoverflow.com/questions/32107088/how-can-i-make-branchless-code

https://www.youtube.com/watch?v=g-WPhYREFjk

:::

# 測驗 3