2020q3 Homework3 (quiz3)

contributed by < haoyu0970624763 >

測驗 1

跨平台的 ASR (arithmetic right shift) 實作

#include <stdio.h>   
int asr_i(signed int m, unsigned int n)
{
    const int logical = (((int) -1) >> 1) > 0;
    unsigned int fixu = -(logical & (m < 0));
    int fix = *(int *) &fixu;
    return (m >> n) | (fix ^ (fix >> n));
} 

當 m > 0 時， 直接return (m >> n) 即可

但重點是當m < 0時，要進行處理。

要先看系統在處理有號數補的是0 還是 1

如果系統補 1 的話，直接return (m >> n) 即為答案

補 0 則需要處理

說明

const int logical = (((int) -1) >> 1) > 0

這是看系統對於有號數的右移，補進來的數字是 0 還是 1 ， 如果是0的話 logical=1

如果是1的話，logical=0

unsigned int fixu = -(logical & (m < 0));
int fix = *(int *) &fixu;

如果系統補的是1，則無論如何 fixu=0

系統補的是0的話，當 m < 0 則 fix=0xffffffff 若 m > 0 則fix=0x00000000

我跟RinHizakura也有一樣的問題，對於為什麼不用int fix = -(logical & (m < 0))也有相同的疑慮

當 m > 0 以及 m < 0 且 系統補1時 會 return (m >> n)|(0 ^ 0)

當 m < 0 且 系統補0時 需要把原本前面補的0全部換成1
這就是(m >> n) | (fix ^ (fix >> n))做的東西。

測驗 2

確認是不是4的冪次

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

• 冪次方必 > 0
• 4的冪次方換成 binary 形式必定只有1個 bit 為1
• 4的冪次方 binary 形式必定是第n個 bit 為1 n為偶數

(num & (num - 1))==0 是用來判斷，這個數字是不是只有1個bit為1

__builtin_ctz(num) 是輸出第一個 bit 為1的值，從第0個 bit 開始

而!(__builtin_ctz(num) & 0x1)是把n為奇數的刪掉

測驗 3

Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

給定一個數，只能透過 -1 和 >>1 讓該數變成 0，並計算操作次數

1. 最低右移次數 :

先看最低位 bit = 1 是在哪個位置，至少需要右移 31-__builtin_clz(num) 次

2. 有多少個 1 (需要幾次減1):

__builtin_popcount(num)

以上兩個為總動作數

int numberOfSteps (int num)
{
    return num ? __builtin_popcount(num) + 31 - __builtin_clz(num) : 0;
}

測驗 4

64-bit GCD (greatest common divisor, 最大公因數) 求值函式 by 輾轉相除法

#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 (v);
    return u << shift;
}

第二個演算法把％的運算用其他方式取代掉，因為取餘數的運算比較複雜。

在 2 進位表示法中可以簡單快速的判斷數字是

$2^n$ 的倍數，所以先把

$2^n$ 先行提出再做輾轉相除法

再把 n 紀錄再 shift 中，之後可以透過 shift 對結果直接進行左移操作

再透過類似於輾轉相除法的求 GCD 方法：更相減損法
主要分成 3 種 case , 我們會先把 2 的公因數提出 , 所以不會有皆為偶數的情況

• x 為偶數，y 為奇數

  $gcd(x,y)=gcd(x/2,y)$

• x 為奇數，y 為偶數

  $gcd(x,y)=gcd(x,y/2)$

• x 為奇數，y 為奇數

  $gcd(x,y)=gcd((x-y)/2),y)$

    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 (v);
    
    return u << shift;
    

最後再把結果乘上當初提出來的公因數

$2^n$ ，也就是 u << shift

兩個程式的效能我用不同的測資去測，發現差異不大，那為什麼要寫一個可讀性較低的code？

也有可能是我輸入的測試資料剛好不是特別顯著

你不能假設所有硬體都有整數除法指令，就算有整數除法指令，也不能預設都能夠在每種情況快速執行。另外，上述演算法很適合用電路實作
jserv

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

輸入為一個 unit64_t 的 Array

pos 為 bitmap 中有多少個 1

out 為一個陣列，紀錄 bitmap 陣列中第幾個位置為 1

優化版

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

其實在觀察改寫前的程式碼中我們可以發現他是對於每一個 bit 都進行觀察

改寫後的版本是透過 t = bitset & -bitset 把 bitset 中 bit=1 的最右邊保存起來

並利用r = __builtin_ctzll(bitset)去看是哪個位置

最後對 bitset 做 Xor 會把 剛剛保存的 1 變成 0 而其餘跟原本的 bitset 不變

可以減少迴圈的次數。