2020q3 Homework3 (quiz3)

tags: sysprog2020 homework

contributed by < JKChun >

第 3 週測驗題

測驗 1

int asr_i(signed int m, unsigned int n)
{
    const int logical = (((int) -1) OP1) > 0;
    unsigned int fixu = -(logical & (OP2));
    int fix = *(int *) &fixu;
    return (m >> n) | (fix ^ (fix >> n));
}

延伸問題 1

解釋上述程式運作原理，應提供數學證明和 Graphviz 製作的圖解;

• answer：
  • OP1 : >> 1
  • OP2 : m < 0
• 第 3 行：這段是為了確認編譯器在對負數實作右移時，會不會自動補齊 sign bit( Sign Extension )，-1 為 0xFFFFFFFF
  • 如果編譯器會自動補齊 sign bit，則 -1 右移後還是 0xFFFFFFFF，會小於0，logical 為0，代表我們不用幫右移後的數補齊1
  • 如果編譯器不會自動補齊 sign bit，則 -1 右移後會是 0x7FFFFFFF，會大於0， logical 為1，代表我們要幫右移後的數補齊1
• 第四行：只有在沒有 Sign Extension 且 m 為負數時，才需要自己補齊 sign bit，所以只有在此情況 unsigned int fixu 為 0xFFFFFFFF，其他情況都是0
• 第五行：還不知道
• 第六行：在不需要自己補齊 sign bit 的情況就 return (m >> n) 就行，如果需要自己補齊 sign bit ，就需要補齊從 MSB ( Most Significant Bit ) 開始往後數的 n 個 bit 為1， (fix ^ (fix >> n)) 就可以滿足這樣的結果，假如 n 等於 6，則 (fix ^ (fix >> n)) 為 0xFC000000，就是 11111100000000000000000000000000，再讓 (m >> n) 跟 (fix ^ (fix >> n)) 做 OR 運算 就可以補齊

延伸問題2

2.練習實作其他資料寬度的 ASR，可參照 C 語言：前置處理器應用篇 撰寫通用的巨集以強化程式碼的共用程度;

---

測驗 2

bool isPowerOfFour(int num)
{
    return num > 0 && (num & (num - 1))==0 &&
           !(__builtin_ctz(num) OPQ);  
}

延伸問題 1

解釋上述程式運作原理;

• answer：
  • OPQ ： & 0x1
• num > 0：放這段的原因在於 num 在
  $\le 0$ 的情況不會是 power of four，所以 num 如果不大於 0 就可以直接 return false
• (num & (num - 1))==0：這段是在判斷 num 是否為 2 的 n 次方
  • 如果 num 不是
    $2^n$，那絕不可能是 power of four
• !(__builtin_ctz(num) & 0x1)：如果 num 為 power of four，則它的 trailing 0-bits 一定是偶數個(0, 2, 4,…)，__builtin_ctz(num) 的結果最後一個 bit 絕對不是 1，以此區分
  $2^n$ 和
  $4^n$

  • __builtin_ctz(num)	Binary
    $0$	00000000
    $2$	00000010
    $4$	00000100

延伸問題 2

改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量;

延伸問題 3

練習 LeetCode 1009. Complement of Base 10 Integer 和 41. First Missing Positive，應善用 clz;

延伸問題 4

研讀 2017 年修課學生報告，理解 clz 的實作方式，並舉出 Exponential Golomb coding 的案例說明，需要有對應的 C 原始程式碼和測試報告;

x-compressor 是個以 Golomb-Rice coding 為基礎的資料壓縮器，實作中也用到 clz/ctz 指令，可參見 Selecting the Golomb Parameter in Rice Coding。

---

測驗 3

int numberOfSteps (int num)
{
    return num ? AAA + 31 - BBB : 0;
}

延伸問題 1

解釋上述程式運作原理;

• answer：

  • AAA ： __builtin_popcount(num)
  • BBB ： __builtin_clz(num)

• 根據題目給的 example 可以發現整個運算就是：

  • 遇到奇數就減 1 變偶數
  • 遇到偶數就除以 2，就是向右 shift 1 位

• 以題目的 14 (1110) 為例：

  1. 1110 為偶數，shift 1位，變 111 (7)
  2. 111 為奇數，先減 1 變 110 (6)
  3. 110 為偶數，shift 1位，變 11 (3)
  4. 11 為奇數，先減 1 變 10 (2)
  5. 10 為偶數，shift 1位，變 1 (1)
  6. 1 為奇數，先減 1 變 0 (0)
  • 總共 six step

• 以上面的例子可以發現：

  • 計算 shift step：
    • 在考慮 32 位元且是正數的情況，從最靠近 MSB 的 1 開始算到 LSB，看有幾個 bit，再減 1 就是幾個 shift step，以上面的例子：0x0000000E (1110) 中，最左側的 1 到 0 有 4 個 bit ( 32 - __builtin_clz(num) )，所以有 3 個 shift step，因為最左側的 1 不 shift 只減 1
  • 計算 減 1 step：
    • 有幾個 1 bit 就要減幾次 1，以上面的例子：0x0000000E (1110) 中有3個 1 所以有 3 個減 1 step

• 總結：

  • 32 - __builtin_clz(num) - 1 計算 shift step
  • __builtin_popcount(num) 計算 減 1 的 step

延伸問題 2

改寫上述程式碼，提供等價功能的不同實作並解說;

提示: Bit Twiddling Hacks 中提及許多 bitwise operation 的使用，如 bit inverse、abs 等等，是極好的參考材料。

延伸問題 3

避免用到編譯器的擴充功能，只用 C99 特徵及 bitwise 運算改寫 LeetCode 1342. Number of Steps to Reduce a Number to Zero，實作出 branchless 解法，儘量縮減程式碼行數和分支數量;

---

測驗 4

考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式:

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
    if (!u || !v) return u | v;
    while (v) {                               
        uint64_t t = v;
        v = u % v;
        u = t;
    }
    return u;
}

改寫為以下等價實作:

#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 (XXX);
    return YYY;
}

延伸問題 1

解釋上述程式運作原理;

• GCD性質：Greatest Common Divisor 特性和實作考量
• GCD演算法：Binary GCD Algorithm
• answer：
  • XXX：v
  • YYY：u << shift
• 第 3 行：考慮了 gcd(x, 0) = x 和 gcd(0, y) = y 以及 gcd(0, 0) = 0 這三種情況
• 第 4 ~ 7 行：
  • !((u | v) & 1) 這個判斷式是在 u 與 v 皆為偶數的情況 ( LSB 為 0 ) 才會成立 ( 0 與 1 AND 等於 0，再 NOT 則為 1 )
  • 此迴圈就是計算兩個數字有幾個 2 的共同因數，用 shift 存數量，用在最後 shift ( 左移、乘以 2 ) 結果
• 第 8 ~ 9 行：
  • 在經過前面的 for 迴圈後，只會有三種情況：
    1. u 為偶數，v 為奇數
    2. v 為偶數，u 為奇數
    3. u 為奇數，v 為奇數
  • 在上述三種情況中，2 並不是共同因數，所以對 GCD 的結果沒有影響，因此在 while 迴圈裡把 u 的因數 2 拿掉，GCD 的性質：
    $gcd(u,v)=gcd(\frac{u}{2},v)$
• 第 10 ~ 21 行：
  • 這裡用
    $gcd(u,v)=gcd(u-v,v),u>v$，不停讓 u 與 v 越變越小，直到 v 變為 0，
    $gcd(u,0)=u$；經過前面的 for and while loop，u 為奇數，而 v 在一開始及將減去 u 後 ( or
    $u-v$ ) 可能為偶數，所以在 11 ~ 12 行會把 v 除以 2 變成奇數，確保 u 為奇數且 u > v
  • 最後 u << shift 將 u 乘上之前除掉的共同因數並 return 結束

延伸問題 2

在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;

---

測驗 5

在影像處理中，bit array (也稱 bitset) 廣泛使用，考慮以下程式碼:

#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;
}

可用 clz 改寫為效率更高且等價的程式碼:

#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 = KKK;
            int r = __builtin_ctzll(bitset);
            out[pos++] = k * 64 + r;
            bitset ^= t;                           
        }
    }
    return pos;
}

延伸問題 1

解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中;

延伸問題 2

設計實驗，檢驗 clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 bitmap density;

延伸問題 3

思考進一步的改進空間;

---