# 2020q3 Homework4 (quiz4)

contributed by < ```howish``` >

## 測驗１

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

gcc extension `__builtin_popcount` 計算了一個數字的二進位裡出現的 1 的個數，而兩個數字的XOR`x ^ y`正是將兩個數字的二進位中不同的地方計算成 1 ，相同的地方計算成 0 ，因此計算 x ^ y 的 1 的個數正是等於這兩個數字的 hamming distance

## 測驗２

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

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

    // Allocate parents
    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] = parents[i];

    // Get parent array for each element
    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]][j - 1];
            if (obj->parent[i][j] != -1) quit = 0;
        }
        if (quit) break;
    }
    obj->max_level = max_level - 1;
    return obj;
}

考慮範例給的樹

這段程式碼實際上是造了一個 parent table，儲存了所有2密次
|Relative dist|1|2|4|8|
|:-:|:-:|:-:|:-:|:-:|
|Ancestors of n0||||
|Ancestors of n1||||
|Ancestors of n2||||
|Ancestors of n3||||

## 測驗３

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

下表表示了`div3`與`div5`所有可能需要使用的index值，可知答案為 div5 → div3 → 2 時與所有
| `div3` | `div5` |`(8>>div5)>>(div3<<2)`|
|:------:|:------:|:--------------------:|
| 0 | 0 | 8 |
| 0 | 1 | 4 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |

## 測驗４

#define ffs32(x)  ((__builtin_ffs(x)) - 1)
size_t bitwise(size_t offset, size_t page_queues) {
    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;
    }
}

`__builtin_ffs` 這個函式計算了此數字的二進位表示法中第一個1出現在從右數來第幾個。`((__builtin_ffs(x)) - 1)` 就是計算了二進位表示法中最右邊有幾個0。

這意味著在此程式碼中5~6行直接去掉了除數與被除數的2冪次因數。故 `divident` 只可能是奇數，也就是 3, 5, 7 三種可能。