2020q3 Homework4 (quiz4)
===
contribute by `Liao712148`
* 1.從新回答[第4周測驗題](https://hackmd.io/@sysprog/2020-quiz4)
###### tags: `進階電腦系統理論與實作`
## 測驗1
```cpp=
int hammingDistance(int x, int y) {
return __builtin_popcount(x OP y);
}
```
此題要找出2個數轉成2進位後有幾個不一樣的bit，透過
`XOR`的特性:
* 具有交換性
`A^B==B^A`
* 與0作XOR會得到自己
`A^0==A`
* 與自己作XOR會得到0
`A^A==0`
所以我們可以利用`XOR`將2個數不同的部分找出來，再利用`__builtin_popcount()`，將不一樣的總數計算出來。
所以`OP`選擇`^`
### 延伸問題
* 不使用`gcc extension`的`C99`實作程式碼
```cpp=
int hammingDistance(int x, int y) {
int temp=x^y;
int sum=0;
while(temp){
if(temp&0x1) sum++;
temp>>=1;
}
return sum;
}
```
我用了不斷向左位移，並與`0x1`作用來計算不相同的次數，藉此取代`__builtin_popcount()`
* 練習LeerCode[477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)
此題如果用值觀的方式的話，
```cpp=
int totalHammingDistance(int* nums, int numsSize){
int sum=0;
for(int i=0;i<numsSize-1;i++){
for(int j=1;(i+j)<numsSize;j++){
int32_t temp=(*(nums+i))^(*(nums+i+j));
sum+=__builtin_popcount(temp);
}
}
return sum;
}
```
運算複雜度是$\ O(n^2)$，計算時間會過長。
所以改成
```cpp=
int totalHammingDistance(int* nums, int numsSize) {
int ret=0;
int temp=0,temp2=0;
int max=0;
for(int i=0;i<32;i++){
temp=0;
temp2=0;
for(int j=1;j<numsSize;j+=2){
temp=(((nums[j-1]>>i)&0x01)+((nums[j]>>i)&0x01));
temp2+=temp;
if(nums[j]>=max){max=nums[j];};
}
if(numsSize&0x01){temp2=temp2+((nums[numsSize-1]>>i)&0x01);}
ret=ret+temp2*(numsSize-temp2);
if(!(max>>i)){break;};
}
return ret;
}
```
`6~9`行走訪，陣列的每個數值，計入其二進位的least significiant bit是不是1，這樣子我們就可以知道，單就這個位子，此陣列中有幾個是不一樣的。
舉例來說`2=0010`,`7=0111`,`1=0001`，如果執行`6~9`行可以得到`temp=2`,ret=$2\times{(3-2)}$，`temp`代表出現幾個1,`ret`代表單就這個位子，此陣列中有幾個是不一樣的。
* 研讀[錯誤更正碼簡](https://w3.math.sinica.edu.tw/math_media/d184/18404.pdf)及[抽象代數的實務應用](https://www.math.sinica.edu.tw/www/file_upload/summer/crypt2017/data/2017/%E4%B8%8A%E8%AA%B2%E8%AC%9B%E7%BE%A9/[20170710][%E6%8A%BD%E8%B1%A1%E4%BB%A3%E6%95%B8%E7%9A%84%E5%AF%A6%E5%8B%99%E6%87%89%E7%94%A8].pdf)摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說;
* 研讀[Reed–Solomon error correction](https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction)，再閱讀 Linux 核心原始程式碼的[lib/reed_solomon 目錄](https://github.com/torvalds/linux/tree/master/lib/reed_solomon),抽離後者程式碼為單獨可執行的程式，作為 ECC 的示範。
---
## 測驗2
```cpp=
#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`:由第`11`行可以知道`malloc()`會回傳`a pointer to a pointer to int`，所以被指定的對象的型別應該也要是`a pointer to a pointer to int`，所以答案要選`int** parent`。
`BBB`，`CCC`:參考自`RinHizakura`同學
建立一個二維矩陣來存放各個`node`的祖先，`14~17`初始化這個二維矩陣。存放第`1`,`2`,`4`... $\ 2^n$的祖先，如果此`node`的$2^{n-1}$的祖先就已經到根節點了，這樣`node`的$2^{n}$的祖先也會是根結點。如果不是的話`node`的$2^{n-1}$的祖先的$2^{n-1}$的祖先，就是`node`的$2^{n}$的祖先，所以`BBB`選擇`-1`。
假設`K=7`代表要找`node`的第7個祖先，那就是先找((`node`的第4個祖先)的第2個祖先)的第一個祖先。所以`CCC`選擇`i<<1`。
### 延伸問題
* 指出可改進的地方，並實作對應的程式碼
空間再越上層的地方矩陣存放了很多`-1`，造成空間上的浪費。
* 在 LeetCode[1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/)提交你的實作，你應該要在 C 語言項目中，執行時間領先 75% 的提交者
---
## 測驗3
```cpp=
#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;
}
```
此題用到的`wrap around`的方式來判斷是`3,5`的倍數，透過
```cpp=
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;
```
舉例來說，假設`i=3n,n>0`，代入`is_divisible()`會得到 `n*M3=3n`，會小於`M3-1`,如果`j=3n+1,n>0`，代入`is_divisible()`會得到`n*M3=3n+M3`會大於`M3-1`，以此可以延伸至5的倍數。
透過第`12,13`行確認是多少的倍數後，再透過`14`行算出===要複製的大小=。
倘若是`3`的倍數則要印出`Fizz`，所以要從位子0往後複製4的字元。
倘若是`5`的倍數則要印出`Buzz`，所以要從位子4往後複製4的字元。
倘若是`15`的倍數則要印出`FizzBuzz`，所以要從位子0往後複製8的字元。
倘若是都不是則要印出`該數字`，所以要從位子8往後複製42字元。
所以`KK1`要選`div5`,`KK2`要選`div3`,`KK3`要選`2`
---
## 測驗4
```cpp=
#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
}
```
由於已知`PAGE_QUEUES`的分布範圍，可以先對除數進行處理，
* (1 or 2 or 3 or 4)
* (5 or 6 or 7 or 8) × (2n), n from 1 to 14
可以求的除數的形式為:
* $1\times2^{n}$,n from=0,1,2,and 4 to 14
* $3\times2^{n}$,n from=0,2,and to 14
* $5\times2^{n}$,n from=1 to 14
* $7\times2^{n}$,n from=1 to 14
再來觀察`5,6`行，可以知道是在執行把除數，被除數中$2^n$的因式預先除掉，再根據`divident`選擇`case`除以除數剩下的因式，所以`CASEA`答案要選擇`3`,`5`,`7`，如果除數剩下的因式是`1`那就不需要再除了。
Sign in with Wallet
Connect another wallet