changed 4 years ago  
Linked with GitHub

2020q3 Homework3 (quiz3)

contributed by < Sisker1111 >

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

測驗題

1. ASR

考慮到程式碼的相容性，目的是實作一套可跨越平台的 ASR，假設在二補數系統，無論標的環境的 shift 究竟輸出為何，我們的 ASR 總可做到:
-3 是 (-5) / 2 的輸出，並往負無限大的方向前進








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));
}
  • logical 是用來判斷 compiler 的 >> 是 logical shift 還是 arithmetic shift.
  • 若是 arithmetic shift ， logical 會是 0 且 fixu = 0，第 6 行的fix ^ (fix >> n)會變成2b'000.....0 ^ 2b'000.....0 = 2b'000.....0(不影響結果)
  • 若是 logical shift ， logical 會是 1 且 fixu = 111…1( 32 個 1)，第 6 行的fix ^ (fix >> n)會變成2b'111.....1 ^ 2b'000.....1 = 2b'111.....0( 1 的數量等同 n)

2. int __builtin_ctz & int __builtin_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);  
}

此題是要確認該數字是否為 4 的冪次方，若該數為 4 的冪次方 32bits 中只會有 1 個 bit 為 1 且該 bit 右邊的 bits 數量應該偶數個，num > 0 && num & (num-1)首先確認該數是否為正數且只有 1 個 bit 為 1，!(__builtin_ctz(num) & 0x1)則是在判斷右邊0的數量是否為偶數個.

不同的實作

(num & (num - 1))==0的部分可以使用!(__builtin_popcount(num) ^ 1)來代替，原本想用 __builtin_clz(num) 來代替num > 0，但會因為 undefined behavior 噴 compiler error.

避免說「噴 compiler error」這樣不精準的話，因為

  1. 閱讀者無法區分是 internal compiler error (ICE，在 gcc 開發過程中常見)，抑或是你遇到編譯器拋出的一般錯誤訊息;
  2. 漢語的「噴」意義和上述的編譯器行為無涉;

你可額外加上 num > 0 的檢查條件，置於 clz 呼叫之前

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

練習 LeetCode 1009. Complement of Base 10 Integer







int bitwiseComplement(int N) {
        if(!N)
            return 1;
        int offset = (1 << (32-__builtin_clz(N)) ) - 1; 
        return N ^ offset ; 
}
  • Runtime : 0 ms, faster than 100.00% of C++ online submissions.
    Memory Usage : 6.1 MB, less than 40.99% of …

練習 LeetCode 41. First Missing Positive

























 int firstMissingPositive(vector<int>& nums) {
        
       if(nums.size()==0) return 1;
        
        for(int i=0; i<nums.size(); i++){
            if(nums[i] > 0 && nums[i] <= nums.size()){
                int pos = nums[i]-1;
                if( nums[pos] != nums[i]){
                    nums[pos] ^= nums[i];
                    nums[i] ^= nums[pos];
                    nums[pos] ^= nums[i];
                    i--;
                }
               
            }
        }
        
        for(int i=0; i<nums.size(); i++){
            if(nums[i]!=(i+1))
                return i+1;
        }
        
        return nums.size()+1;
    }
  • Runtime : 4 ms, faster than 79.63% of C++ online submissions.
    Memory Usage : 9.9 MB, less than 49.44% of …

3. __builtin_popcount

針對 LeetCode 1342. Number of Steps to Reduce a Number to Zero，我們可運用 gcc 內建函式實作，假設 int 寬度為 32 位元，程式碼列表如下:





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

32 bits 內的 bit = 1 的數量等同要執行 subtract 的次數，因此可以很容易之道AAA的答案應為__builtin_popcount(num)，執行完__builtin_popcount(num)後我們還需要向右移動 1 個 bit，透過__builtin_clz(num)我們可以找到最左邊的 1 在哪個位置，找到後用
31-__builtin_clz(num)就可以知道應該向右 shift 幾次，所以 BBB為__builtin_clz(num).

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;
}
  1. 5~7 行檢查 u、v 是否皆為偶數(或是講是否能一起除以2)，因為gcd(u,v) = 2*gcd(u/2,v/2)
  2. 8~10 行檢查 u 是否為偶數，如果 u 為偶數則 v 為奇數，所以gcd(u,v) = gcd(u/2,v)
  3. 11~12 行檢查 v 是否為偶數，如果 v 為偶數則 u 為奇數，所以gcd(u,v) = gcd(u,v/2)
  4. 然後剩下的其實就是輾轉相除法，並且會確保進入下一個迴圈的 v 是比較小的那個值，重複直到進入這次輾轉相除時的 u 和 v 相同，因此 XXX = v
  5. 最後 return 要把 gcd 往左邊 shift 最開始除以2的次數，才能得到正確的值，固YYY = u << shift.

透過 __builtin_ctz 改寫

注意到下面的實驗中會將 quiz3 中題目的作法命名為 fast gcd，使用 __builtin_ctz 調整後的版本則稱為 faster gcd 以方便解釋。

前面的 for (shift = 0; !((u | v) & 1); shift++) 迴圈可以使用 __builtin_ctz 來改寫為如下:



























#ifndef min
#define min(x, y) ((x) < (y) ? (x) : (y))
#endif

uint64_t faster_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. 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;
}

看向原 Code 第 9 行，目的是要從最右邊的 bit 開始 check 是否為 1，下面改寫的版本把 for 改成 while，bitset & -bitset是把 bitset 與 -bitset 的 2 的補數做 & ，這樣即可得到最右邊 bit 數為 1 且其他 bits　皆為 0 的 bitmap，最後第 12 行是用來將最右邊 1 改為 0，這樣下次__builtin_ctzll(bitset)就不會找到錯誤的 bit .

Select a repo