2020q3 Homework3 (quiz3)

contributed by < chi-ming5566 >

測驗題

作業要求

重新回答第 3 周測驗題，連同附帶的「延伸問題」。
比照課前測驗參考解答: Q1的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及進行相關實驗。

`測驗一`







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

ars 在右移後，會依照原本首位的 bit 補回值，也就是正數補 0，負數補 1。

一開始的 logical 判斷環境是不是 logical right shift (一律補 0)，所以對 -1 右移 1(OP1 = >> 1)，如果是 logical right shift，會變成 0b011…111 > 0 = true = 1，反之則是 0b111…111 < 0 = false = 0。

而fixu 用來判斷被除數 m 是不是負數(OP2 = m < 0)，當 logical = 1 與 m < 0 時，fixu = -(1 & 1) = 0b111…111，否則 fixu = 0b000…000。

return 的結果，如果在 logical = 1 以及 m < 0 都成立時，fix ^ (fix >> n) 會是前 n 個 bits 為 1，其餘為 0。所以和 (fix ^ (fix >> n)) 做 OR 運算就可以把 logical right shift 吃掉的 1 補回來。

Example :

m = 0b11100110, n = 4, system = logical

`測驗二`

我們可用 __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 的二進位表示是 0100，也就是說 4 的次方是 1 後面接著偶數個 0 (每次乘以 4， 1 就會向左位移 2 位元)。

一開始 num > 0 判斷是否為正整數，(num & (num - 1)) == 0 判斷是否為 2 的次方
(

1 \overset{n 個}{\overset{⏞}{000. . .000}}

0 \overset{n 個}{\overset{⏞}{111. . .111}} = 0

) ，所以可以知道 !(__builtin_ctz(num) OPQ 是在判斷後面的 0 的個數是否為偶數。而任一偶數 & 1 = 0 (偶數最後一項 bit 為 0)，所以 OPQ = & 0x1。

`測驗三`

popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 1，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 0 元素個數、計算兩個字串的 Hamming distance。Intel 在 2008 年 11 月 Nehalem 架構的處理器 Core i7 引入 SSE4.2 指令集，其中就有 CRC32 和 POPCNT 指令，POPCNT 可處理 16-bit, 32-bit, 64-bit 整數。




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

這題計算一個數經過多少次計算可以變為零，而計算有分兩種 : >> 1 (當前是偶數)以及 - 1 (當前是奇數)。

int 寬度為 32 bits，因此將最左邊的 bit 移到最右邊要做 31 次 >> 1，有一個 1 就需要做一次 - 1，而起始 1 的位置每往右一個位元就能少做一次 >> 1。

所以 AAA = __builtin_popcount(num), BBB = __builtin_clz(num) 。

`測驗四`

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

`測驗五`

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

兩段程式碼互相比對後，用 int r = __builtin_ctzll 取代 if ((bitset >> i) & 0x1) 的功能，但改寫後的程式碼對 out[pos++] 賦值後還必須 clear bitset 的 LSB 以確保下個 Loop 的正確運行。

根據題三提到
$- n =\sim n + 1$

利用 bitset & -bitset 留下 LSB 再於 bitset ^= t 清除 LSB
因此 KKK = (e) bitset & -bitset。