2020q3 Homework3 (quiz3)

contributed by < JimmyLiu530 ＞

tags: 進階電腦系統理論與實作

題目

測驗1: Arithmetic right shift for signed integers

在 C 語言中，對有號型態的物件進行算術右移(簡稱 ASR)歸屬於 unspecified behavior。考慮到程式碼的相容性，我們想實作一套可跨越平台的 ASR，假設在二補數系統，無論標的環境的 shift 究竟輸出為何，我們的 ASR 總可做到:

$-5>{>}^{arith}1$

$=-3$
上述

$-3$ 即為

${\displaystyle \frac{-5}{2}}$ 向

$-\mathrm{\infty }$ 進位的輸出

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

程式說明

算術右移一個正數其最左邊的 bit 必定是補 0 ，而算術右移一個負數有可能是補 0 或是補 1，而根據題目的意思，顯然是後者，因此需要知道 compiler 是補 0 還是 1。若是補 1，則符合我們的要求不需修補；否則需要修補。而這個修補會在 line 6 的| (fix ^ (fix >> n))。

line 3 的用意就是在看此 compiler 對一個負數算術右移後會補 0 還是 1，若補 1，則右移後的結果為負 (<0)，因此 logical 為 0；否則 logical 為 1。所以 OP1 = >> 1。

接著，考慮算術右移一個負數補 0 的情況，因為 line 6 的修補項是要用來修補的，所以 (fix ^ (fix >> n)) 的最高的 n 個位數一定要是 1，也就代表 fix 會是 0xffffffff，最後可推得 OP2 = m < 0。

此結果也符合一開始說的條件: 除了原本 compiler 右移負數補 1 不用修補之外，正數也不需要 (即只有右移補 0 且 為負數才需要修補)。

已解問題:
int fix = *(int *) &fixu; 這樣寫的用意?
int fix = (int) fixu; 以及可以改成這樣嗎?

雖然此程式看似可互換，但這兩行程式碼的意義不太相同，前者為 interpret，後者為 cast。看下面的例子:

float a = 0.5;
int b = (int)a;
int c = *(int*)&a;
printf("%f 0x%08x 0x%08x\n", a, b, c);

會得到:

0.500000 0x00000000 0x3f000000

也就是說前者以 整數 的角度去詮釋(interpret) 浮點數，好讓我們去對其中的某幾個位元做操作。

而後者是直接把 浮點數 強制轉型(cast)成 整數。

延伸問題

1. 數學證明和 Graphviz 製作的圖解

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

---

測驗2: Leetcode 342. Power of Four

GCC extension 其中包含兩個函式: ctz 和 clz:

Built-in Function: int __builtin_ctz (unsigned int x)

• Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.

Built-in Function: int __builtin_clz (unsigned int x)

• Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

我們可用 __builtin_ctz 來實作 LeetCode 342. Power of Four，假設 int 為 32 位元寬度。實作程式碼如下:

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

程式說明

line 3 的第二個條件 (num & (num - 1))==0 其實就區分出 2 的冪次方的數了，像是

$2^3={1000}_{(2)}$ 減1後，

$7={0111}_{(2)}$，因此接下來只要排除掉 2 的冪次方(

$2^n$)中，n 為奇數的數即可。一樣可以透過觀察:

decimal	binary	# of trailing zero
2	10	1
4 = $4^1$	100	2
8	1000	3
16 = $4^2$	10000	4
32	100000	5
64 = $4^3$	1000000	6
發現 n 為奇數的數，其 trailing zero 也會是奇數個，因此 OPQ = & 0x1。

延伸問題

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

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

將原本的 (num & (num - 1))==0 改成 __builtin_popcount(num) == 1，兩者都可以過濾掉非 2 的冪次方的數。

又或是可以改寫成:

bool isPowerOfFour(int num)
{
    return num > 0 && !(__builtin_popcount(num) ^ 0x1) &&
           __builtin_ffs(num) & 0x1);  
}

__builtin_popcount(num) == 1 等價於 !(__builtin_popcount(num) ^ 0x1)，且
4 的冪次方的數其 first set bit 的位置會是奇數。

Built-in Function: int __builtin_ffs (int x)

• Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

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

Complement of Base 10 Integer:

int bitwiseComplement(int N){
    if (N == 0)
        return 1;
    uint32_t mask = 0xffffffff >> __builtin_clz(N);
    return N ^ mask;
}

• 位元反轉 -> 想到 ^ 1111...1111
• 只需要反轉最低 32 - (N 的 leading zero) 個位元

First Missing Positive:

// TODO

---

測驗3: LeetCode 1342. Number of Steps to Reduce a Number to Zero

給定一個非負整數 num，回傳將此數依照下面的規則變成 0 需要幾步。而規則就是:

當目前的數為偶數，則將它除以 2；否則將它減 1。

我們可運用 gcc 內建函式實作，假設 int 寬度為 32 位元，程式碼列表如下:

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

程式說明

因為在正整數中，除以 2 即為右移 1 位元，所以總共要除幾次就等於 MSB 移到最低位需要移幾次，MSB 移至最低位需 31 - __builtin_clz(num) 步，因此也需要除那麼多次。

再者，當 num 的二進位表示法中有 k 個 1 時，代表總共需要做 k 次的減 1，因為這些 1 總會被移到最低位元的位置，而最低位元為 1 代表是奇數需要減 1 ，所以共需 __builtin_popcount(num) 次減 1

因此最後答案就會是 AAA = __builtin_popcount(num) 及 BBB = __builtin_clz(num)

延伸問題

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

// TODO

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

// TODO

---

測驗4: 64-bit GCD

考慮以下 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;
}

程式說明

此改寫後的程式與最原本單純利用輾轉相除法不同的點在於，做輾轉相除法之前，先做了以下的步驟:

• 先將兩數中所有 2 的因數都提出來，最後再將結果左移對應的位數即可
• 當其中一數不存在 2 因數時，代表 2 就不會是他們的公因數，因此將另一個仍含有 2 因數的數除以 2 直到變成奇數, e.g. gcd(24,9) = gcd(6,9)

line 5-6 其實就是在做上述的第一點，總共提出shift 個 2。line 8-9 及 11-12就是做上述的第二點。而程式中的 do-while 其實就是輾轉相除法，只是是用減法去實現，因此 XXX = v。最後，再將原本的結果 u 左移 shift 個 bit(即 x

$2^{shift}$)，所以 BBB = u << shift。

延伸問題

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

uint64_t gcd64(uint64_t u, uint64_t v) {
    if (!u || !v) return u | v;
    int shift;
    int ctz_u = __builtin_ctz(u);
    int ctz_v = __builtin_ctz(v);

    if (ctz_u < ctz_v)
        shift = ctz_u;
    else
        shift = ctz_v;
    
    u = u >> ctz_u;
    v = v >> ctz_v; 
    do {
        while (!(v & 1))
            v /= 2;
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (v);
    return u << shift;
}

// TODO分析

---

測驗5: Positions of set bits in bit array

在影像處理中，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;
}

程式說明

第一個程式的作用在於看 bitmap 中哪些 bit 為 1，並將其位置記錄在 out 中。第一與第二個程式只有 line 8 的那個 while 的不同而已，因此聚焦在此。

透過觀察第一個程式碼，可知其脈絡為一個位元一個位元地去檢查 bitset 是否為 1，即 若要檢查第 k 個位元，需將 bitset 右移 k 位元，再與 1 比較。

而第二個程式也是 follow 這個脈絡，只是在 line 10 計算了 bitset 的 trailing zero，可以減少傻傻地去檢查為 0 的位元的時間，來提升效率。最後，line 12 需將把檢查過的位元變成 0，因此 KKK = bitset & -bitset，這是因為 x & -x = x & (~x + 1) = 保留其 LSB，其餘設為 0，所以 x ^ (x & -x) 會將原本 x 的 LSB 變成 0。

延伸問題

1. 舉出這樣的程式碼用在哪些真實案例中

• 在 linux kernel 中有使用這種資料結構 - 第 k 位被設成 1 若且唯若 k 在佇列裡時，可提升從硬體中找到「首位 0」操作的效率
• 也會用在記憶體頁、inode、磁碟分割區等的分配上，去看哪些記憶體已被使用

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

3. 思考進一步的改進空間