Try   HackMD

2020q3 Homework4 (quiz4)

contributed by < haoyu0970624763 >

測驗 1 - Hamming Distance

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

程式原理

Hamming Distance 是要計算兩串二進位字串不同的地方有幾個,也就是計算 XOR 之後 有幾個 1

不使用 gcc extension 的 C99 實作程式碼

int hammingDistance(int x, int y) { x=x^y; unsigned count=0; while(x){ count++; x=x&(x-1); } return count; }

參考資訊

測驗二-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-1] == -1 ? -1:obj->parent[obj->parent[i][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 << i)) 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); }

程式碼解析

obj->parent = malloc(n * sizeof(int *));

可以從這一行看出 parent 為 pointer to pointer 的 type

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

max_level是紀錄現在這個tree當中最大的level數為多少

obj->parent 做成二維陣列,obj->parent[n][max_level] 並將所有值初始化成 -1

( -1 表示 no ancestor 的意思)

for (int i = 0; i < parentSize; i++)
    obj->parent[i][0] = parent[i];

parent[i] 存放的是 nodei 父親的位置

並把obj->parent[i][0] 用來存放 nodei 的父親

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

目的: 設置 obj->parent 的 element

測驗3-FizzBuzz

從 1 數到 n

  • 如果是 3的倍數,印出 “Fizz”
  • 如果是 5 的倍數,印出 “Buzz”
  • 如果是 15 的倍數,印出 “FizzBuzz”
  • 如果都不是,就印出數字本身

可以觀察到:

  • 整數格式字串 "%d" : 長度為 2
  • "Fizz" 或 "Buzz" : 長度為 4
  • "FizzBuzz" : 長度為 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 >> div5) >> (div3 << 2)], length); fmt[length] = '\0'; printf(fmt, i); printf("\n"); } return 0; }

程式解說

div3div5 分別可知道 i 是否為 3 或 5 的倍數

  • 是,為 1
  • 否,則為 0

這個概念在quiz2有碰過

length則是根據我們觀察,判斷是不是3或5的倍數進行 operator 的平移

div3 div5 length ( 8 >> div5) >> (div3 << 2)
1 0 4 0
0 1 4 4
1 1 8 0
0 0 2 8