# 2020q3 Homework4 (quiz4)
contributed by < `shauming1020` >
###### tags: `homework`
## 測驗 1
```c=
int hammingDistance(int x, int y) {
return __builtin_popcount(x OP y);
}
```
> population count 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 1
###
- Hamming Distance 計算兩數之間相異 bit 個數，$x \oplus y$ 先將相異的 bit 位置設為 1 後再透過 __builtin_popcount 求出 1 的個數，即為 Hamming Distance
- 不使用 gcc extension 的 C99 實作程式碼
```c=
int hammingDistance(int x, int y) {
x ^= y;
y = 0;
while (x) {
y += (x & 1);
x >>= 1;
}
return y;
}
```
### LeetCode 477. Total Hamming Distance
- 暴力法
```c=
int totalHammingDistance(int* nums, int numsSize){
int sum = 0;
for(int i = 0; i < numsSize - 1; i++) {
for (int j = i + 1; j < numsSize; j++) {
sum += __builtin_popcount(nums[i] ^ nums[j]);
}
}
return sum;
}
```
先從較直覺的暴力法著手，numsSize 不斷增長的情況下，時間複雜度為 $O(n^2)$
- 觀察
| nums[i] | bit 3 | bit 2 | bit 1 | bit 0 |
| ------- | ------| ----- | ------| ----- |
| 4 | 0 | 0 | 0 | 1 |
| 14 | 1 | 1 | 1 | 0 |
| 2 | 0 | 0 | 1 | 0 |
| 1s | 1 | 2 | 2 | 0 |
| 0s | 2 | 1 | 1 | 3 |
| sum | 2 | 2 | 2 | 0 |
可以推得總和為所有資料中相對 bit 的 1 總數 * 0 總數，因此 $total sum = 1 \times 2 + 2 \times 1 + 2 \times 1 + 0 \times 3 = 6$
```c=
int* to_bit_array(int num) {
int *bit_array = (int *) malloc(sizeof(int) * 32);
memset(bit_array, 0, sizeof(int) * 32);
for (int i = 0; i < 32; i++, num >>= 1)
bit_array[i] += (num & 1);
return bit_array;
}
void add_bit_array(int *a, int *b) {
for (int i = 0; i < 32; i++)
a[i] += b[i];
}
int totalHammingDistance(int* nums, int numsSize) {
int sum = 0;
int *bit_array = to_bit_array(0);
for (int i = 0; i < numsSize; i++) {
int *tmp = to_bit_array(nums[i]);
add_bit_array(bit_array, tmp);
}
for (int i = 0; i < 32; i++)
sum += bit_array[i] * (numsSize - bit_array[i]);
return sum;
}
```
### 研讀錯誤更正碼簡介及抽象代數的實務應用
> 研讀錯誤更正碼簡介及抽象代數的實務應用，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說;
搭配閱讀 Hamming codes, Part I 及 Hamming codes, Part II，你可適度摘錄影片中的素材，但應當清楚標註來源
**Hamming Distance & Hamming Weight**
- 定義
- Hamming Distance : 兩向量有幾個相異的 bit
> e.g. $x = (0001011), x' = (1101010), d_H(x,x') = 3$
- Hamming Weight : 一個向量不是 0 的的地方有幾個
> e.g. $w_H(x) = 3, w_H(x') = 4$
- x 和 x' 的 Hamming Distance 只是 (x + x') 的 Hamming Weight
- minimum distance : 在這個碼中，任兩不同 codewords 的 Hamming distance，其當中最小值
- minimum weight : 所有不為 0 的 codewords，其 Hamming weight 的最小值
- 特性
- 由於兩個 codewords 的 Hamming distance 會等於相加後的 Hamming weight，所以對線性碼來說，$d_{min(C)} = w_{min(C)}$，也就是 minimum distance 會等於 minimum weight
- 要改 t 個錯，其 minimum distance 至少要 $2t + 1$
> 1. 球心 (x, x') 為一個 codeword，球包含所有跟此 codeword 的 Hamming distance <= t 的 binary vectors
> 2. 由於要改 t 個錯，兩球不能交疊在一起，否則交疊的 vectors 不知道要改成 x 還是 x'
> 3. 因此兩球距離至少為 1，即任兩 codewords 距離至少要 $2t + 1$
### 研讀 Reed–Solomon error correction
---
## 測驗 2
>給你一棵樹，樹上有 n 個節點，編號自 0 到 $n − 1$ 。樹以父節點陣列的形式提供，其中 parent[i] 是節點 i 的父節點。樹的根節點是編號為 0 的節點。
>請設計 treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k) 函式，回傳節點 node 的第 k 個祖先節點。若不存在這樣的祖先節點，回傳 -1。樹節點的第 k 個祖先節點是從該節點到根節點路徑上的第 k 個節點
```
Input:
["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]
Output:
[null,1,0,-1]
```
```c=
#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);
}
```
###
```graphviz
digraph treeAncestor {
node[shape=record]
node15 [label="{{<value> 15 | {<parent> 7 | 3 | 0 | -1 | -1 | -1}}}"]
0 -> {1, 2}
1 -> {3, 4}
2 -> {5, 6}
3 -> {7, 8}
4 -> {9, 10}
5 -> {11, 12}
6 -> {13, 14}
7 ->{node15, 16}
8 -> {17, 18}
9 -> {19, 20}
10 -> {21, 22}
11 -> {23, 24}
12 -> {25, 26}
13 -> {27, 28}
14 -> {29, 30}
}
```
treeAncestorCreate
- ```#11 obj->parent = malloc(n * sizeof(int *)); ``` 從這行可以知道結構體成員 parent 為 a pointer to a pointer，故 AAA 為 int ** parent
- ```#13 int max_level = 32 - __builtin_clz(n) + 1;``` 計算最大樹高 (skewed)
- ```
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 ，index i 表示節點編號，index j 存取**上 $2^{j}$ 代祖先**，因此 ```obj->parent[i][j] = -1;``` 先將每個節點的**每 $2^{j}$ 代祖先**設為 -1 (沒有祖先)
- ```
for (int i = 0; i < parentSize; i++)
obj->parent[i][0] = parent[i];
```
每個節點的上一代 ( j = 0 ) 祖先根據給定的 parent 序列逐一指派，例如 parent 給定 [-1,0,0,1,1,2,2]，則第 0 個節點的上一代祖先將被指派為 -1
- ```
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;
}
```
接著建立**上 $2^{j}$ 代祖先**，j 從 1 開始，當存在**上 $2^{j-1}$ 代祖先**時，才會有**上 $2^{j}$ 代祖先**，因此 BBB = -1
treeAncestorGetKthAncestor
- 搜尋**上 k 代祖先**，如果**上 $2^i$ 代祖先存在**，就從上 $2^i$ 代祖先繼續往上搜尋
- 例如 k = 5 (0b101)，則 i 在 0、2 時可能會有上 $2^i$ 代祖先存在，如果上 $2^0$ 代祖先存在，則從上一代祖先繼續往上搜尋上 $2^2$ 祖先
###
---
## 測驗 3
```c=
#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;
}
```
> 從 1 數到 n，
如果是 3的倍數，印出 “Fizz”
如果是 5 的倍數，印出 “Buzz”
如果是 15 的倍數，印出 “FizzBuzz”
如果都不是，就印出數字本身
###
- 從 ```strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);``` 可以回推程式想執行的事情
- 從 "FizzBuzz%u" 中取出特定長度的字串出來放到變數 fmt，再將其打印出來
- 而要取多長則取決於變數 length，從哪裡開始取則取決於 (MSG_LEN >> KK1) >> (KK2 << KK3) ，其中 MSG_LEN 8
- ```unsigned int length = (2 << div3) << div5;```
- 從 1 數到 n ，如果可以被 3 整除則 div3 將被設成 1，否則為 0 ，同理 div 5
- 因此我們會得到下列四種不同的 length
- 3 的倍數，(2 << 1) << 0 得 4
- 5 的倍數，(2 << 0) << 1 得 4
- 15 的倍數，(2 << 1) << 1 得 8
- 都不是，(2 << 0) << 0 得 2
- ```(MSG_LEN >> KK1) >> (KK2 << KK3)``` 根據以上不同的情境將未知的 KK 填入
- 先考慮 3 和 15 的倍數，要印出 “Fizz” 和 “FizzBuzz” 都得從字串的 0 位開始取，先從選項中取固定常數出來嘗試
- KK1 = 1、KK2 = 2、KK3 = 2，可得 0
- 接著考慮 5 的倍數，要印出 “Buzz” 得從字串的 4 位開始取
- 將 KK2 改成 div3 可得 4
- 而最後考慮都不是的情況，要取得字串的輸出控制符 %u 得從字串的 8 位開始取
- 最後將 KK1 改成 div5 可得 8
---
## 測驗 4
> 考慮到整數 PAGE_QUEUES 可能有以下數值:
> (1 or 2 or 3 or 4)
> (5 or 6 or 7 or 8) × ($2^n$), n from 1 to 14
```c=
#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
}
```
其中 CASES 可能形如:
```c
case 2: blockidx /= 2;
break;
```
用最少的 case-break 敘述做出同等 ```size_t blockidx = offset / PAGE_QUEUES;``` 效果的程式碼
- ```__builtin_ffs(x))``` 表示 x 二進位中最後一個 1 的位置
> int __builtin_ffs (unsigned int x)
Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
- ``` ffs32(x) ((__builtin_ffs(x)) - 1)``` 等同於 ctz ，表示尾端有幾個 0，即該數是否含有 $2^n$
- ```blockidx = offset >> ffs32(divident);``` $offset /= 2^n$，先從 offset 提出 $2^n$
- ```divident >>= ffs32(divident);``` $divident /= 2^n$
- 將 $2^n$ 提出後且 PAGE_QUEUES 最多為 $8 \times 2^n$，故只需判斷 ```blockidx /= y```，y = 2, 3, 5, 7 質數即可
---
Sign in with Wallet
Connect another wallet