2022q1 Homework2 (quiz2)

contributed by <HScallop>

tags: linux2022

2022q1 quiz2

測驗 1

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

EXP1 = ?

a & b & 1

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

EXP2 = ?

a & b

EXP3 = ?

a ^ b

延伸問題

1. 當初這兩題在上課有回答出來。思考這兩題的時候，覺得很類似於以前上邏輯設計的時候 full-adder 的作法。
   在 EXP1 的程式碼因為先各自 >> 1 /2 ，所以除了最小位數外，不需要再考慮 propagation ，而 EXP2, EXP3 就像是經典的 full-adder 加法後，再 >> 1 /2 的結果。
   

   
   從上圖可以看出 sum 就是 a ^ b propagation 則是 a & b 。

---

測驗 2

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

EXP4 = ?

a ^ b

EXP5 = ?

a < b

延伸問題

1. 可以參考 解讀計算機編碼 - 不需要分支的設計想法上是利用 diff = a - b 還有 (diff >> 31) 判斷 diff < 0 ，如果 diff < 0 b 就會被加上 (a - b) 轉換成 a 。
   回到測驗本測驗的問題，還是一樣要在 b > a 時，把 a 轉換成 b 。跟前面不一樣的地方是這邊想用 XOR 來實作。
   所以推測在 b > a 時，會用 a ^ a ^ b 把 a 變成 b 。

---

測驗 3

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int shift;
    for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }
    while (!(u & 1))
        u /= 2;
    do {
        while (!(v & 1))
            v /= 2;
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (COND);
    return RET;
}

COND = ?

v

RET = ?

u << shift

延伸問題

1. 程式碼實現了題目給定的簡化規則，再用輾轉相除法找到 GCD，以下按照敘述來對應程式碼行數

• If both x and y are 0, gcd is zero
  $gcd(0,0)$.
• $gcd(x,0)=x$ and
  $gcd(0,y)=y$ because everything divides 0.

line 4
u 或 v 會有一個是 0 所以 u | v 會是非 0 的另外一個數。

• If both x and y are even,
  $gcd(x,y)=2\ast gcd({\displaystyle \frac{x}{2}},{\displaystyle \frac{y}{2}})$ because 2 is a common divisor.
  Multiplication with
  $2$ can be done with bitwise shift operator.

line 6-8
!((u | v) & 1) 這邊的 AND 1 就是最小一位數的 mask 只要 u 或 v 有一個是奇數，就會跳出迴圈。

• If x is even and y is odd,
  $gcd(x,y)=gcd({\displaystyle \frac{x}{2}},y)$, vice versa.

line 9-21
while loop on line 9: u is even and v is odd.
while loop on line 12: u is odd and v is even.
line 11 開始的 do while 迴圈是輾轉相除法的實作，比較特別的是他會把相減之後的數留在 v ，繼續用 u is odd and v is even 的規則簡化。
所以這邊 COND 是輾轉相除法的終止條件。
而RET 是最後結果，需要注意剛剛照著規則提出的 2 要乘回來。

---

測驗 4

#include <stddef.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
    size_t pos = 0;
    for (size_t k = 0; k < bitmapsize; ++k) {
        uint64_t bitset = bitmap[k];
        size_t p = k * 64;
        for (int i = 0; i < 64; i++) {
            if ((bitset >> i) & 0x1)
                out[pos++] = p + i;
        }
    }
    return pos;
}

改寫的程式碼:

#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
    size_t pos = 0;
    uint64_t bitset;
    for (size_t k = 0; k < bitmapsize; ++k) {
        bitset = bitmap[k];
        while (bitset != 0) {
            uint64_t t = EXP6;
            int r = __builtin_ctzll(bitset);
            out[pos++] = k * 64 + r;
            bitset ^= t;                           
        }
    }
    return pos;
}

EXP6 = ?

bitset & -bitset

延伸問題

1. 其實在原本的題目中就有說明第 9 行的作用是找出最小的位數的 1 ，這邊利用了 2's complement 的特性。
   e.g.
   

   $010001\underset{\text{n}}{\underbrace{0...0}}$
   2's complement:
   1. invert bits
      $101110\underset{\text{n}}{\underbrace{1...1}}$
   2. add 1
      $101111\underset{\text{n}}{\underbrace{0...0}}$

   比較可以發現，只會有最小一位的 1 和更小位數的 0 會一樣，其他位置都已經被反轉。
   第一段程式碼第 8 行的迴圈被取代了，運用 __builtin_ctzll，不需要一位一位檢查。