Try   HackMD

2020q3 Homework3 (quiz3)

contributed by < chewei3 >

測驗 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));
}

答案

  • OP1 = >> 1
  • OP2 = m < 0
  • logical 用來判斷 >> 是 logical right shift 還是 arithmetic right shift ,如果 m < 0 且是 logical right shift ,則 fixu 為 -1ufix ^ (fix >> n)用來將 m shift 後的左邊 n bits 補 1

延伸問題:

  1. 解釋上述程式運作原理,應提供數學證明和 Graphviz 製作的圖解;
  2. 練習實作其他資料寬度的 ASR,可參照 C 語言:前置處理器應用篇 撰寫通用的巨集以強化程式碼的共用程度;

測驗 2

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

答案

  • OPQ = 0x1
  • __builtin_ctz 回傳從 LSB 到第 1 個 1 之前有幾個 0,!(__builtin_ctz(num) 0x1) 判斷是不是偶數個, 所以 0x1、0x4、0x16 ,都會return 1, num & (num - 1) 用來判斷 num 是不是偶數,也就是判斷 LSB 是不是 1,所以可以去掉 0x1

延伸問題:

  1. 改寫上述程式碼,提供等價功能的不同實作,儘量降低 branch 的數量;
  2. 練習 LeetCode 1009. Complement of Base 10 Integer41. First Missing Positive,應善用 clz;
  3. 研讀 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; }

答案

  • AAA = __builtin_popcount(num)
  • BBB = __builtin_clz(num)
  • 一個 step 包含
    * divide by 2
    * subtract 1, if LSB is 1
  • 因此 numberOfSteps 計算最高位有效位的 bit position( 31 - __builtin_clz(num) ),加上 1 的個數( subtract 次數)

延伸問題:

  1. 解釋上述程式運作原理;
  2. 改寫上述程式碼,提供等價功能的不同實作並解說;

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

  1. 避免用到編譯器的擴充功能,只用 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; }

答案

  • XXX = v
  • YYY = u << shift

延伸問題:

  1. 解釋上述程式運作原理;
  2. 在 x86_64 上透過 __builtin_ctz 改寫 GCD,分析對效能的提升;

用 __builtin_ctz 改寫 GCD

#ifndef min #define min(x, y) ((x) < (y) ? (x) : (y)) #endif uint64_t gcd64(uint64_t u, uint64_t v){ if (!u || !v) return u | v; int shift = min(__builtin_ctz(u), __builtin_ctz(v)); u >>= shift; v>>= shift; while (!(u & 1)) u >>= 1; do { while (!(v & 1)) v >>= 1; if (u < v) { v -= u; } else { uint64_t t = u - v; u = v; v = t; } } while (v); return u << shift; }

測驗 5

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

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

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

答案

  • KKK = bitset & -bitset
  • naive 的做法是一次只檢查 bitset 的某 1 bit 是不是 1,並且把bit position 放到 out[pos] ,每一個 bitmap 都要做 64 次效率不夠好
  • improved 用 ctz 找出 bit position ,並且用 bitset & -bitset 將 bitset 的最低有效位的 1 設為 t ,用 xor 將之設為 0

延伸問題:

  1. 解釋上述程式運作原理,並舉出這樣的程式碼用在哪些真實案例中;
  2. 設計實驗,檢驗 clz 改寫的程式碼相較原本的實作有多少改進?應考慮到不同的 bitmap density;
  3. 思考進一步的改進空間;