2020q3 Homework4(quiz4)

contributed by < Uduru0522 >

tags: `perspective and application of computer systems 2020`

測驗一：計算 Hamming Distance



int hammingDistance(int x, int y) {
    return __builtin_popcount(x ^ y);
}

程式說明

Hamming Distance 可以透過計算兩個 string 的相異處數量而得。
由於題目之 x 及 y 長度相同，且

L = {0, 1}

，
於是我們可以利用 XOR 逕直計算滿足

X [I] \neq Y [I]

的

I

的數量。

延伸問題

不使用 gcc extension 的 C99 實做










int hammingDistance(int x, int y){
    uint32_t mask = 0x01, temp = x ^ y;
    int h_distance = 0;
    for(int i = 0;i < 32;++i){
        h_distance += (mask & temp);
        temp >>= 1;
    }

    return 
}

計算 x ^ y 之後再透過 mask 以及右移得出 Set Bit, 即為兩數的 Hamming Distance。

LeetCode 477. Total Hamming Distance

Input 為一長度為 numsSize 的 int array,
求陣列中所有 pair 的 Hamming Distance 總和。

程式碼














int totalHammingDistance(int* nums, int numsSize){
    char mask = 0x01;
    int count_ones, total_distance = 0;
    
    for(int i = 0; i < 32; ++i){
        count_ones = 0;
        for(int j = 0; j < numsSize; ++j){
            count_ones += (nums[j] >> i & mask);
        }
        total_distance += (count_ones * (numsSize - count_ones));
    }
    
    return total_distance;
}

說明

測驗一之中我們可以看出來，計算 Hamming Distance 時，可以每個位元分開計算。
因此，可以將問題簡化為 對 numsSize 個 bit 來說，Hamming Distance 為何？，
並進行 32 次 (int 的長度) 這個運算。

接著，由於 Hamming Distance 即是算 (0, 1) 及 (1, 0) 的組數，
當每個 input 只有一個位元時便很好計算：

num of 1's \times num of 0's

因此，我們只要對 array 中每個數的每個 bit 都掃過一次即可計算出 Hamming Distance 的總和。
時間複雜度為

O (n)

。

錯誤更正碼簡介及抽象代數的實務應用

TODO

Linux 核心中的 Reed–Solomon Error Correction

測驗二：計算 Tree 之中 Node 的第 K 個父節點

LeetCode 1483. Kth Ancestor of a Tree Node



















































#include <stdlib.h>

typedef struct {
    int **parent;
    int max_level;
} TreeAncestor;

TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
    TreeAncestor *obj = malloc(sizeof(TreeAncestor));
    obj->parent = malloc(n * sizeof(int *));

    int max_level = 32 - __builtin_clz(n) + 1;
    for (int i = 0; i < n; i++) {
        obj->parent[i] = malloc(max_level * sizeof(int));
        for (int j = 0; j < max_level; j++)
            obj->parent[i][j] = -1;
    }
    for (int i = 0; i < parentSize; i++)
        obj->parent[i][0] = parent[i];

    for (int j = 1;; j++) {
        int quit = 1;
        for (int i = 0; i < parentSize; i++) {
            obj->parent[i][j] = obj->parent[i][j + (-2)] == -1
                                    ? -1
                                    : obj->parent[obj->parent[i][j - 1]][j - 1];
            if (obj->parent[i][j] != -1) quit = 0;
        }
        if (quit) break;
    }
    obj->max_level = max_level - 1;
    return obj;
}

int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
    int max_level = obj->max_level;
    for (int i = 0; i < max_level && node != -1; ++i)
        if (k & (1))
            node = obj->parent[node][i];
    return node;
}

void treeAncestorFree(TreeAncestor *obj)
{
    for (int i = 0; i < obj->n; i++)
        free(obj->parent[i]);
    free(obj->parent);
    free(obj);
}

程式說明

延伸問題

記憶體浪費檢測

Top 25% 實做

測驗三：FizzBuzz 問題之解答優化
























#define MSG_LEN 8

static inline bool is_divisible(uint32_t n, uint64_t M) {
    return n * M <= M - 1;
}

static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1;

int main(int argc, char *argv[]) {
    for (size_t i = 1; i <= 100; i++) {
        uint8_t div3 = is_divisible(i, M3);
        uint8_t div5 = is_divisible(i, M5);
        unsigned int length = (2 << div3) << div5;

        char fmt[MSG_LEN + 1];
        strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> div5) >> (div3 << 2)], length);
        fmt[length] = '\0';

        printf(fmt, i);
        printf("\n");
    }
    return 0;
}

程式說明

檢測可被 3 / 5 整除 (無求餘運算)

觀察程式碼，
可以注意到以下的不等式用來得知一 32-bit 整數是否能被 d(

$d \in {3, 5}$ ) 整除：

$Assume S_{i, 64} = 0xiiiiiiiiiiiiiiii, i \in [0_{16}, F_{16}]$

n \times (S_{F, 64} \div 3 + 1) \leq S_{F, 64} \div 3

經過化簡，可得

n \times S_{5, 64} + n \leq S_{5, 64}

接著，考慮三個不同 n 的值：整除、除三餘一、除三於二：

$n \equiv$	0 (mod 3)	1 (mod 3)	2 (mod 3)
LHS ( $n \times S_{F, 64} + n$ )	$\overset{overflow}{\to} n$	$\overset{overflow}{\to} S_{5, 64} + n$	$\overset{overflow}{\to} S_{A, 64} + n$
利用 overflow 來取代除法運算中重複減去的過程，節省時間，
其中只有 $n \equiv 0 (mod 3)$ 時，等式才成立。

此等式可以應用於檢測所有

S_{F, 64}

之因數

M

且

S_{F, 64} \div M > L, L =

檢測範圍 bit 長度 的
整數的因數上，舉例來說，
若要檢測是否可被 15 整除，M15 即可設成

S_{1, 64} + 1

。

優點：

$M_{k}$ 可提前計算，大幅減少除法運算的次數(僅一次)

字串輸出優化

程式中字串輸出以『同個字串，不同起點和終點』來輸出，如以下表格：

字串內容	F	i	z	z	B	u	z	z	%u	\0
起始點 (included)	$0 (m o d 3)$ $0 (m o d 15)$				$0 (m o d 5)$				Others
終點 (excluded)					$0 (m o d 3)$				$0 (m o d 5)$ $0 (m o d 15)$	Others

目標

由 div5 以及 div3 兩個值計算出起點以及字串長，div5

,

div3

\in {0, 1}

將上方表格轉換成數值：

`div3`	`div5`	起點	`length`
0	0	8	$\geq$ 1
0	1	4	4
1	0	0	4
1	1	0	8

起點方程式
透過觀察，可以發現滿足以下方條件的方程式可以為解：

$start_point (0, 0) = 8$
只要 !div3 便為0
div5 會造成除以 2 的效果

可得 start_point(div3, div5) = !div3 & (8 >> div5)。(我的算法)
與題目中解答的相異之處為條件ㄅ的處理，題目使用的方式為
『若 div3，向右移 4-bit』，
無論運算值為何 (8 或 4) 皆會被消除。

`length` 方程式

透過觀察，可以發現滿足以下方條件的方程式可以為解：

$length (0, 0) \geq 1$
div3 和 div5 任一為 1，結果為 4
div3 和 div5 同時成立會造成額外乘以 2 的效果

可得 length = 2 << div3 << div5。

延伸問題

更換 bitmask 減少指令維持 branchless

測驗四：

考慮到整數 PAGE_QUEUES 可能有以下數值:

(1 or 2 or 3 or 4)
(5 or 6 or 7 or 8)
$\times$ (2n), n from 1 to 14

給定 size_t offset，計算 blockidx = offset / PAGE_QUEUES
















#include <stdint.h>
#define ffs32(x)  ((__builtin_ffs(x)) - 1)

size_t blockidx;
size_t divident = PAGE_QUEUES;
blockidx = offset >> ffs32(divident);
divident >>= ffs32(divident);

switch (divident) {
    case 3: blockidx /= 3; 
        break;
    case 5: blockidx /= 5; 
        break;
    case 7: blockidx /= 7; 
        break;
}

程式說明

`ffs32(n)`

根據 Gcc Online Documentation, 6.59 Other Built-in Functions Provided by GCC:

int __builtin_fss(int x)
Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

此 Macro 與 __builtin__ctz(x) 有類似作用(計算末尾 0 的數量)，然而後者對 x == 0 時之應對為 Undefined.

消除公因數
$2^{n}$ 及計算

將 offset 以及 divient 皆右移 ffs32(divient)，消除末尾所有的 0，也就是公因數

2^{n}

。
觀察 PAGE_QUEUES 範圍，看得出可以以

2^{n} \times 3^{a} \times 5^{b} \times 5^{c}

來表示，因此 switch block 僅需處理 3、5、7 三個質因數。

延伸問題

LeetCode 51. N-Queens ，使用 `__builtin_ffs()`

TODO

2020q3 Homework4(quiz4)

tags: perspective and application of computer systems 2020

測驗一：計算 Hamming Distance

程式說明

延伸問題

不使用 gcc extension 的 C99 實做

LeetCode 477. Total Hamming Distance

程式碼

說明

錯誤更正碼簡介及抽象代數的實務應用

Linux 核心中的 Reed–Solomon Error Correction

測驗二：計算 Tree 之中 Node 的第 K 個父節點

程式說明

延伸問題

記憶體浪費檢測

Top 25% 實做

測驗三：FizzBuzz 問題之解答優化

程式說明

檢測可被 3 / 5 整除 (無求餘運算)

字串輸出優化

目標

length 方程式

延伸問題

更換 bitmask 減少指令維持 branchless

測驗四：

程式說明

ffs32(n)

消除公因數 2n 及計算

延伸問題

LeetCode 51. N-Queens ，使用 __builtin_ffs()

tags: `perspective and application of computer systems 2020`

`length` 方程式

`ffs32(n)`

消除公因數
$2^{n}$ 及計算

LeetCode 51. N-Queens ，使用 `__builtin_ffs()`