Try   HackMD

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

延伸問題:

  • 解釋上述程式碼運作的原理
  • 比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 (可研讀 CS:APP 第 3 章)
  • 研讀 Linux 核心原始程式碼 include/linux/average.h，探討其 Exponentially weighted moving average (EWMA) 實作，以及在 Linux 核心的應用

    移動平均（Moving average)，又稱滾動平均值、滑動平均，在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數，來分析資料點的計算方法。
    移動平均通常與時間序列資料一起使用，以消除短期波動，突出長期趨勢或周期。短期和長期之間的閾值取決於應用，移動平均的參數將相應地設置。例如，它通常用於對財務數據進行技術分析，如股票價格、收益率或交易量。它也用於經濟學中研究國內生產總值、就業或其他宏觀經濟時間序列。

延伸閱讀：

測驗 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

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







G



a

a



a ^ b

a ^ b



a:n->a ^ b:n


^ b



a ^ b:s->a:s


^ b

改進處：

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

延伸問題:

  • 解釋上述程式碼運作的原理
    註：對 BranchA ^ ((BranchA ^ BranchB) & -(BranchBCondition)) = BranchBCondition ? BranchB : BranchA 的 Branchless programming 多做描述。
  • 針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
  • Linux 核心也有若干 branchless / branch-free 的實作，例如 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 檢索。

延伸閱讀：

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

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

測驗 3

Last changed by 
 
MicahDoo
0
168
Published on HackMD