Try   HackMD

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 ),-10xFFFFFFFF
    • 如果編譯器會自動補齊 sign bit,則 -1 右移後還是 0xFFFFFFFF,會小於0,logical 為0,代表我們不用幫右移後的數補齊1
    • 如果編譯器不會自動補齊 sign bit,則 -1 右移後會是 0x7FFFFFFF,會大於0, logical 為1,代表我們幫右移後的數補齊1
  • 第四行:只有在沒有 Sign Extension 且 m 為負數時,才需要自己補齊 sign bit,所以只有在此情況 unsigned int fixu0xFFFFFFFF,其他情況都是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
    0
    的情況不會是 power of four,所以 num 如果不大於 0 就可以直接 return false
  • (num & (num - 1))==0:這段是在判斷 num 是否為 2 的 n 次方
    • 如果 num 不是
      2n
      ,那絕不可能是 power of four
  • !(__builtin_ctz(num) & 0x1):如果 num 為 power of four,則它的 trailing 0-bits 一定是偶數個(0, 2, 4,),__builtin_ctz(num) 的結果最後一個 bit 絕對不是 1,以此區分
    2n
    4n
    • __builtin_ctz(num) Binary
      0
      00000000
      2
      00000010
      4
      00000100

延伸問題 2

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

延伸問題 3

練習 LeetCode 1009. Complement of Base 10 Integer41. 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) 這個判斷式是在 uv 皆為偶數的情況 ( 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(u2,v)
  • 第 10 ~ 21 行:
    • 這裡用
      gcd(u,v)=gcd(uv,v),u>v
      ,不停讓 u 與 v 越變越小,直到 v 變為 0,
      gcd(u,0)=u
      ;經過前面的 for and while loop,u 為奇數,而 v 在一開始及將減去 u 後 ( or
      uv
      ) 可能為偶數,所以在 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

思考進一步的改進空間;