2020q3 Homework4 (quiz4)

contribute by <hsiehong>

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

outline

2020q3 Homework4 (quiz4)
- - 題目
- 測驗 1
  - 原理
  - LeetCode 練習
- 測驗 2
- 測驗 3
- 測驗 4

題目

測驗 1



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

OP = ^

原理

要計算兩數 x, y 的 Hamming distance，先將兩數做 xor 運算，所得結果的數的二進制中 1 的個數即為所求

LeetCode 練習

477. Total Hamming Distance

作法一
最直覺的做法，用雙迴圈將所有結果加總起來，但會 TLE













class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        size_t numSize = nums.size();
        int ham = 0;
        for (int i = 0; i<numSize; ++i) {
            for (int j = i + 1; j<numSize; ++j) {
                ham += __builtin_popcount(nums[i] ^ nums[j]);
            }
        }
        return ham;
    }
};

作法二

參考解說



















class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        size_t numSize = nums.size();
        int bitCnt[32] = {0};
        for (int i = 0; i < numSize; i++) {
            for (int j = 0; j < 32; j++) {
                if (nums[i] & (1 << j)) {
                    bitCnt[j]++;
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < 32; i++) {
            sum += (numSize - bitCnt[i]) * bitCnt[i];
        }
        return sum;
    }
};

主要是利用 bit operation 每個 bit 都是各自獨立的特性，記錄每個位置 1 跟 0 出現的次數，每個 1 跟每個 0 會貢獻一次 Hamming distance，將兩數相乘就是那個 bit 總共會貢獻的 Hamming distance

測驗 2



















































#include <stdlib.h>

typedef struct {
    AAA;
    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 + BBB] == -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 & (CCC))
            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);
}

AAA = int **parent, BBB = (-1), CCC = 1 << i

在 func treeAncestorCreate() 內部，可以看到 line 11 先宣告一個一維空間給 parent ，在 line 15 在對每個單位空間宣告 max_level 大小的空間，可得知 parent 是一個二維陣列，所以 AAA = int **parent
line 24 的 for loop 是在對每個點建立祖先，假設要建立第 j 個祖先，要先檢查第 j-1 的祖先是否存在，有的話才將第
$2^{j - 1}$ 個 parent 的第
$2^{j - 1}$ parent 加入 (binary tree) 寫入第
$2^{j}$ 個祖先，所以 BBB = -1

測驗 3

FizzBuzz !!!

從 1 數到 n，如果是 3的倍數，印出 “Fizz”，如果是 5 的倍數，印出 “Buzz”，如果是 15 的倍數，印出 “FizzBuzz”，如果都不是，就印出數字本身，觀察下列 offset，可以透過 offset 來控制期望的輸出

 string literal: "fizzbuzz%u"
         offset:  0   4   8
























#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 >> KK1) >> (KK2 << KK3)], length);
        fmt[length] = '\0';

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

KK1 = div5, KK2 = div3, KK3 = 2

div3, div5 分別代表 n 是否可以被 3, 5 整除，並決定好要複製的起點和長度。觀察 length
- 若只可被 3 整除 (2 << 1 << 0) = 4
- 只可被 5 整除 (2 << 0 << 1) = 4
- 若同時可被 3 跟 5 整除 (2 << 1 << 1) = 8
- 否則其他狀況 = 2
觀察每個狀態的起始位置

 string literal: "fizzbuzz%u"
         offset:  0   4   8

div3	div5	start(MSG_LEN)
1	0	0
0	1	4
1	1	0
0	0	8

可以推得 (MSG_LEN >> KK1) >> (KK2 << KK3)，其中 KK1 = div5, KK2 = div3, KK3 = 2

測驗 4

TODO