---
tags: sysprog2020
---

# 2020q3 Homework4 (quiz4)
contributed by < `mingjer` >

## 測驗 `1`
[LeetCode 461. Hamming Distance](https://leetcode.com/problems/hamming-distance/) 提及，兩個整數間的 Hamming distance 為其二進位的每個位元的差。請計算輸入參數兩整數 x 與 y 的 Hamming distance，例如整數 1 的二進位為 0 0 0 1，而整數 4 的二進位為 0 1 0 0，則 1 與 4 的 Hamming distance 為 2。

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

* `OP` = `^`
* 因為當兩個數有相異位元的時候， hamming distance 加 1，所以先將兩個數做 `^` 之後再利用 `__builtin_popcount` 來計算有幾個 1
## 測驗 `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`
* 觀察 `*treeAncestorCreate` 裡 `obj->parent = malloc(n * sizeof(int *));` 他是分配 n 個指標空間，所以 struct 裡面應該是一個指標指向那個空間
* `BBB` = `(-1)`
*

## 測驗 `3`