---
tags: sysprog2020
---
# [2020q3](http://wiki.csie.ncku.edu.tw/sysprog/schedule) Homework4 (quiz4)
contributed by < `nickchenchj` >
> related links: [2020q3 第 4 週測驗題](https://hackmd.io/@sysprog/2020-quiz4)

## Problem 1
### Task
* Given two integers `x` and `y`, calculate the [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance).

Below is the implementation of the function that calculates the Hamming distance:

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

#### OP = ?
* `(a)` `|`
* `(b)` `&`
* `(c)` `^`
* `(d)` `+`
* `(e)` `-`

### Solution
According to [GCC Built-in Functions](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html), the description of `__builtin_popcount` is as follows:
> Built-in Function: int __builtin_popcount (unsigned int x)
> * Returns the number of 1-bits in x.

* From the return value `_builtin_popcount(x OP y)`, we can deduce that only pairs of bits in `x` and `y` with the same index but different values will become `1` after `x OP y`. For example, if the LSB in `x` is `0` and the LSB in `y` is `1`, the result of `0 OP 1` will become `1`.

| `x` | `y` | `x OP y` |
|:-----------------:|:-----------------:|:---------:|
| ==10==01 01==10== | ==01==01 01==01== | 1100 0011 |

###### Note: 8-bit integer is used for demonstration

* Clearly, OP must be `^`, so the answer to this problem is `(c)` `^`.

:::success
**Answer**
* OP: `^`
:::

---

## Problem 2
### Task
From LeetCode [1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/):
> You are given a tree with n nodes numbered from 0 to n-1 in the form of a parent array where parent[i] is the parent of node i. The root of the tree is node 0.
>
> Implement the function getKthAncestor(int node, int k) to return the k-th ancestor of the given node. If there is no such ancestor, return -1.
>
> The k-th ancestor of a tree node is the k-th node in the path from that node to the root.

#### Example:
* Input:

["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

* Output:

[null,1,0,-1]

:::info
:information_source: **Explanation**
* `7`: there are `7` nodes in a tree
* `[-1, 0, 0, 1, 1, 2, 2]`: indicates the parents of each node
* `[3, 1]`: gets the `1st` ancestor of node `3` (expected ancestor: `1`)
* `[5, 2]`: gets the `2nd` ancestor of node `5` (expected ancestor: `0`)
* `[6, 3]`: gets the `3rd` ancestor of node `6` (expected ancestor: `-1`)
:::

* Below is the implementation of this problem:

#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 = ?
* `(a)` `int ***parent`
* `(b)` `int **parent`
* `(c)` `int *parent`

#### BBB = ?
* `(a)` `(-2)`
* `(b)` `(-1)`
* `(c)` `0`
* `(d)` `1`
* `(e)` `2`

#### CCC = ?
* `(a)` `1`
* `(b)` `i`
* `(c)` `i >> 1`
* `(d)` `i >> k`
* `(e)` `k << i`
* `(f)` `1 << i`

### Solution
#### AAA
* By observing `obj->parent = malloc(n * sizeof(int *));` in `treeAncestorCreate`, it is obvious that `parent` is a pointer that points to an array of integer pointers.
* As a result, `AAA` must be `int **parent`.

#### BBB
* To figure out what `BBB` is, we need to know how `treeAncestorCreate` works.
* First, `treeAncestorCreate` creates `obj` and initializes it (`n = 7`):

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

* `obj` after initialization:

digraph add_entry{
    graph [pad="0.5", nodesep="0.4", ranksep="0.8"];
    rankdir=LR
    splines=polyline
    node [shape=record]

    parent [
        label="obj->parent"
        shape=plaintext
    ]
    nodes [
        label="{ <n0>n0 }|{ <n1>n1 }|{ <n2>n2 }|{ <n3>n3 }|{ <n4>n4 }|{ <n5>n5 }|{ <n6>n6 }"
    ]
    ancestors_0 [
        xlabel="ancestors of n0"
        label="{ <head>-1 | -1 | -1 | -1 }"
    ]
    ancestors_1 [
        xlabel="ancestors of n1"
        label="{ <head>-1 | -1 | -1 | -1 }"
    ]
    ancestors_2 [
        xlabel="ancestors of n2"
        label="{ <head>-1 | -1 | -1 | -1 }"
    ]
    ancestors_3 [
        xlabel="ancestors of n3"
        label="{ <head>-1 | -1 | -1 | -1}"
    ]
    ancestors_4 [
        xlabel="ancestors of n4"
        label="{ <head>-1 | -1 | -1 | -1}"
    ]
    ancestors_5 [
        xlabel="ancestors of n5"
        label="{ <head>-1 | -1 | -1 | -1}"
    ]
    ancestors_6 [
        xlabel="ancestors of n6"
        label="{ <head>-1 | -1 | -1 | -1}"
    ]
    
    parent -> nodes:n0:w
    nodes:n0:e -> ancestors_0:head:w
    nodes:n1:e -> ancestors_1:head:w
    nodes:n2:e -> ancestors_2:head:w
    nodes:n3:e -> ancestors_3:head:w
    nodes:n4:e -> ancestors_4:head:w
    nodes:n5:e -> ancestors_5:head:w
    nodes:n6:e -> ancestors_6:head:w
} 

* Next, `treeAncestorCreate` stores the parents of each node in `obj->parent[i][0]` (`parentSize = 7`):

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

* `obj` after storing parents of each node:

digraph add_entry{
    graph [pad="0.5", nodesep="0.4", ranksep="0.8"];
    rankdir=LR
    splines=polyline
    node [shape=record]

    parent [
        label="obj->parent"
        shape=plaintext
    ]
    nodes [
        label="{ <n0>n0 }|{ <n1>n1 }|{ <n2>n2 }|{ <n3>n3 }|{ <n4>n4 }|{ <n5>n5 }|{ <n6>n6 }"
    ]
    ancestors_0 [
        xlabel="ancestors of n0"
        label="{ <head>-1 | -1 | -1 | -1 }"
    ]
    ancestors_1 [
        xlabel="ancestors of n1"
        label="{ <head>0 | -1 | -1 | -1 }"
    ]
    ancestors_2 [
        xlabel="ancestors of n2"
        label="{ <head>0 | -1 | -1 | -1 }"
    ]
    ancestors_3 [
        xlabel="ancestors of n3"
        label="{ <head>1 | -1 | -1 | -1}"
    ]
    ancestors_4 [
        xlabel="ancestors of n4"
        label="{ <head>1 | -1 | -1 | -1}"
    ]
    ancestors_5 [
        xlabel="ancestors of n5"
        label="{ <head>2 | -1 | -1 | -1}"
    ]
    ancestors_6 [
        xlabel="ancestors of n6"
        label="{ <head>2 | -1 | -1 | -1}"
    ]
    
    parent -> nodes:n0:w
    nodes:n0:e -> ancestors_0:head:w
    nodes:n1:e -> ancestors_1:head:w
    nodes:n2:e -> ancestors_2:head:w
    nodes:n3:e -> ancestors_3:head:w
    nodes:n4:e -> ancestors_4:head:w
    nodes:n5:e -> ancestors_5:head:w
    nodes:n6:e -> ancestors_6:head:w
} 

* Then, update grandparents of each node, great-grandparents of each node and so on:

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

* To find the grandparent of a node, simply find the parent's parent.
* Take ancestors of `n3` for example, say we want to find its grandparent:
* ancestors of `n3` (original): `{1, -1, -1, -1}`
* parent of `n3` is `n1` (at `index = 0`)
* ancestors of `n1`: `{0, -1, -1, -1}`
* we know that the grandparent of `n3` is the parent of `n1`, which is `n0` (at `index = 0`) in this case
* update grandparent of `n3` (at `index = 1`) from `-1` to `0`
* ancestors of `n3` (updated): `{1, 0, -1, -1}`
* From the example above, we can see that the system needs to check if the parent of a node exists before the system carries on finding grandparent of the node.
* Note that the parent node is stored in the element **before** (`current_index - 1`) the element which stores the grandparent node (index of parent: `0`, index of grandparent: `1`).
* Therefore, `BBB` is `(-1)`.
* `obj` (complete):

digraph add_entry{
    graph [pad="0.5", nodesep="0.4", ranksep="0.8"];
    rankdir=LR
    splines=polyline
    node [shape=record]

    parent [
        label="obj->parent"
        shape=plaintext
    ]
    nodes [
        label="{ <n0>n0 }|{ <n1>n1 }|{ <n2>n2 }|{ <n3>n3 }|{ <n4>n4 }|{ <n5>n5 }|{ <n6>n6 }"
    ]
    ancestors_0 [
        xlabel="ancestors of n0"
        label="{ <head>-1 | -1 | -1 | -1 }"
    ]
    ancestors_1 [
        xlabel="ancestors of n1"
        label="{ <head>0 | -1 | -1 | -1 }"
    ]
    ancestors_2 [
        xlabel="ancestors of n2"
        label="{ <head>0 | -1 | -1 | -1 }"
    ]
    ancestors_3 [
        xlabel="ancestors of n3"
        label="{ <head>1 | 0 | -1 | -1}"
    ]
    ancestors_4 [
        xlabel="ancestors of n4"
        label="{ <head>1 | 0 | -1 | -1}"
    ]
    ancestors_5 [
        xlabel="ancestors of n5"
        label="{ <head>2 | 1 | -1 | -1}"
    ]
    ancestors_6 [
        xlabel="ancestors of n6"
        label="{ <head>2 | 1 | -1 | -1}"
    ]
    
    parent -> nodes:n0:w
    nodes:n0:e -> ancestors_0:head:w
    nodes:n1:e -> ancestors_1:head:w
    nodes:n2:e -> ancestors_2:head:w
    nodes:n3:e -> ancestors_3:head:w
    nodes:n4:e -> ancestors_4:head:w
    nodes:n5:e -> ancestors_5:head:w
    nodes:n6:e -> ancestors_6:head:w
} 

#### CCC
* code snippet of `treeAncestorGetKthAncestor`:

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

:::success
**Answers**
* AAA: `int **parent`
* BBB: `(-1)`
* CCC: `1 << i`
:::

---

## Problem 3
### Task
* Given a number `n`, write a function that counts from `1` to `n`.
* if the current number is a multiple of 3, print out `Fizz`
* if the number is a multiple of 5, print out `Buzz`
* if the number is a multiple of 15, print out `FizzBuzz`
* else, print out the number

* Below is the implementation of the [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz) problem:

#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 = ?
* `(a)` `div5`
* `(b)` `div3`
* `(c)` `2`
* `(d)` `1`

#### KK2 = ?
* `(a)` `0`
* `(b)` `1`
* `(c)` `2`
* `(d)` `div3`
* `(e)` `div5`

#### KK3 = ?
* `(a)` `0`
* `(b)` `1`
* `(c)` `2`
* `(d)` `div3`
* `(e)` `div5`

### Solution
* We create a format string `"FizzBuzz%u"`, and find a way to set the starting index and the string length to get the desired output:

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

| Condition | Starting Index | Length |
|:-----------------:|:--------------:|:------:|
| `n % 3 == 0` | 0 | 4 |
| `n % 5 == 0` | 4 | 4 |
| `n % 15 == 0` | 0 | 8 |
| none of the above | 8 | 2 |

* The `length` is already determined by `length = (2 << div3) << div5`, so let's focus on the starting index.
* Note that the starting index is `(MSG_LEN >> KK1) >> (KK2 << KK3)`.

#### KK1
* If the current number is neither a multiple of 3 nor a multiple of 5, the starting index must be `MSG_LEN`. We can deduce that `KK1` must be `0` and `KK2 << KK3` must be `0` too. Therefore, the only possible choices for `KK1` are `div5` and `div3`.
* However, `KK1` can't be `div3`. If `KK1` is `div3`, one of `KK2` or `KK3` must be `div5`. If the current number is a multiple of 5 but not a multiple of 3, then `KK2 << KK3` will be greater than `1`, which will make the starting index become lesser than `4`. Hence, `KK1` must be `div5`.

#### KK2
* We already know that `KK1` is `div5`, therefore, one of `KK2` or `KK3` must be `div3`. If `KK3` is `div3` and `KK2` is a non-zero constant, then the result won't match the desired output (where `n % 3 != 0` and `n % 5 != 0`), because `KK2 << KK3` will be greater than `1`, which results in a wrong starting index. As a result, `KK2` must be `div3`.

#### KK3
* After replacing `KK1` and `KK2` with their values, the starting index becomes `(MSG_LEN >> div5) >> (div3 << KK3)`. Then, we take specific conditions into consideration:
* If `n % 3 == 0` but `n % 5 != 0`, then `MSG_LEN` needs to be right-shifted by `4` to become `0`, therefore, `KK3` must be no less than `2`.
* As a result, `KK3` is `2`.

:::success
**Answers**
* KK1: `div5`
* KK2: `div3`
* KK3: `2`
:::

---

## Problem 4
### Task
* Given two numbers `PAGE_QUEUES` and `offset`, observe the code snippet and choose the possible choices for `CASES`:
* possible values of `PAGE_QUEUES`:
* (1 or 2 or 3 or 4)
* (5 or 6 or 7 or 8) × (2^n^), where $1 \leq n \leq 14$
* code snippet:

#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) {
    CASES
}

From [GCC Built-in Functions](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html):
> Built-in Function: int __builtin_ffs (int x)
> * Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

#### CASES = ? (multiple answers)
* `(a)` `2`
* `(b)` `3`
* `(c)` `4`
* `(d)` `5`
* `(e)` `6`
* `(f)` `7`
* `(g)` `8`
* `(i)` `9`
* `(j)` `10`

### Solution
* We know that `ffs32` returns the index of the least significant 1-bit of a number, which is the same result as `__builtin_ctz`.

According to [GCC Built-in Functions](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html):
> Built-in Function: int __builtin_ctz (unsigned int x)
> * Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.

* Therefore, `divident >>= ffs32(divident)` eliminates all zeros before the least significant 1-bit of the number, so the new `divident` must be odd (`LSB = 1`).
* We know that `PAGE_QUEUES` is assigned to `divendent` previously, and the possible values of `PAGE_QUEUES` are:
* (1 or 2 or 3 or 4)
* (5 or 6 or 7 or 8) × (2^n^), where $1 \leq n \leq 14$
* As a result, the possible choices must be `3`, `5` and `7`.

:::success
**Answer**
* CASES: `3`, `5` and `7`
:::