# 2020q3 Homework4 (quiz4)
contributed by < ddj5523fa >
---
### 想法 & 思考
#### 測驗一
題目:
```cpp=
int hammingDistance(int x, int y) {
return __builtin_popcount(x OP y);
}
```
求x，y的hamming distance。
ANS: hamming distance經過題目上的圖片觀察也能得知: ==是每個位元的差==
所以X、Y的binary中不一樣的bit個數極為答案，而該程式碼中```__builtin_popcount```
是找binary中有幾個1，所以可以聯想到 X 跟 Y 做XOR就能得不同bit變成1。
所以， OP為 ^ <------ ==ANSWER==
##### 延伸學習2.
在測驗2第六題曾做過分別1bit、1bit的比較後再進行一些操作，加上此題題目上程式碼用XOR，讓我將數字轉成binary之後做觀察!
1.得出結論是:
數字(binary)每1bit，分別有多少0跟1的數量相乘，可得到其距離。
EX: [4,12,1]
|4|0100|
|-----|--------|
|12|1100 |
|1 |0001 |
最低位分別為0 0 1 可得到距離: 2* 1 = 2.
第2低位別為0 0 0 距離: 0
第3低位1 1 0 距離: 2 * 1 =2.
第4低位0 1 0 距離: 1 * 2 =2
總和=2+0+2+2=6
hamming distance =6 !
寫成C程式碼:
```cpp=
#include <stdio.h>
int totalHammingDistance(int* nums, int numsSize){
int res = 0, n = numsSize;
for (int i = 0; i < 32; ++i) {
int cnt = 0;
for (int num=0 ;num<numsSize;num++) {
if ((nums[num]>>i) & (1)) ++cnt;
}
res += cnt * (n - cnt);
}
return res;
}
int main ()
{
int nums[]={4,14,2};
printf("%d\n",totalHammingDistance(nums, 3));
}
```
----
#### 測驗二:
題目:
AAA:由malloc()會回傳a pointer to a pointer to int,可知道被指定的對象的型別應該也要是a pointer to a pointer to int，所以答案：int** parent
接下來程式碼多，我認為應舉個例子trace一次以利於理解:
EX:
```graphviz
digraph skew_BST {
size="5"
node [fontname="Arial"];
0 -> 1;
1 -> 2;
2 -> 3;
3 -> 4;
4 -> 5;
}
```
**parent 指向的記憶體空間的內容初始化後長相:
(下圖直接跳到已經補上了node的第一個parent)
```graphviz
digraph hash_table {
nodesep = .05;
rankdir = LR;
node[shape = record, width = 1.1, height = .1];
node0[label = "<f0> int *|<f1> node1 |<f2> int *|<f3> node 3|<f4> int *|<f5> int *", height = 2];
node [width = 1];
node1[label = "{ -1|-1|-1|-1|-1}"];
node2[label = "{ 1|-1|-1|-1|-1}"];
node4[label = "{ 3|-1|-1|-1|-1}"];
node5[label = "{ 4|-1|-1|-1|-1}"];
node0:f0 -> node1;
node0:f4 -> node4;
node0:f5 -> node5;
node0:f2 -> node2;
}
```
接下來依據程式碼可Trace:
表格:
|i \\ j|0|1|2|3|
|-|-|-|-|-|-|
|0|-1|-1|-1|-1|
|1|0|-1|-1|-1|
|2|1|0|-1|-1|
|3|2|1|-1|-1|
|4|3|2|0|-1|
|5|4|3|1|-1|
整理一下規律:parent[i][j]為node i 的往上第$2^j$的node
而BBB選擇-1是因為:
```cpp=
for (int j = 1;; j++) {
int quit = 1;
for (int i = 0; i < parentSize; i++) {
obj->parent[i][j] = obj->parent[i][j + (-1)/*BBB*/] == -1
? -1
: obj->parent[obj->parent[i][j - 1]][j - 1];
if (obj->parent[i][j] != -1) quit = 0;
}
```
第6行程式碼:obj->parent[obj->parent[i][j - 1]][j - 1]; 為依據。
```cpp=
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;
}
```
找第k個根據上面整理的規律:parent[i][j]為node i 的往上第$2^j$的node
所以CCC選擇i<<1。
##### 延伸學習2:
原版:
第一版更改效率:
我只是發現初始化方式是以for迴圈，所以改成了memset(來自於測驗二的靈感)
第二版記憶體空間:(參考了同學quantabase13的表格例子)
我確定了此程式碼運作會有多出一行都-1。所以進行-1與各種debug
某些地方我還沒了解，剛好改完能成功提交而已。日後還需繼續理解:
最終結果:
-----
#### 測驗三:
bitwise.c
```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;
}
```
依據題目先前的程式碼與觀察提示:
```cpp=
#define MSG_LEN 8
char fmt[MSG_LEN + 1];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
```
觀察 printf 的(格式)字串，可分類為以下三種:
整數格式字串 "%d" : 長度為 2 B
“Fizz” 或 “Buzz” : 長度為 4 B
“FizzBuzz” : 長度為 8 B
```
string literal: "fizzbuzz%u"
offset: 0 4 8
```
得出的關鍵為此``` strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);```
然後依據divid 3 OR 5 OR 15 ...得到的offset或是說字元長度 來組合出符合所有可能的答案。
我們依據input 需要得到字串複製的起始點與長度(length)
而```unsigned int length = (2 << div3) << div5;```依據此句程式碼可得長度，再依此推出KK1~KK3。
條件:
case 1: 被3整除；不被5整除
=>length=(2<<1)<<0 =4
=>而output要是Fizz
=>所以offset=0
case 2: 被5整除:不被3整除
=>length=(2<<0)<<1 =4
=>output為Buzz
=>所以offset要是4
case 3:同時被3 與5整除
=>length=(2<<1)<<1=8
=>output=FizzBuzz
=>所以offset=0
Case 4:不被3 && 不被5 整除
=>length=2
=>output:%u
=>所以Offset=8
而MSG_LEN=8，Case4時候位移0剛好得到其offset (div3=0，div5=0)
Case1的時候，需右移4 (div3=1，div5=0)
Case2需右移1 (div3=0，div5=1)
Case3需右移動4 (div3=1，div5=1)
符合的組合便是
FizzBuzz%u[(MSG_LEN >> KK1) >> (KK2 << KK3)]
=FizzBuzz%u[(8>> div5) >> (div3 << 2)]-----------==Answer==
P.S.
原本我以為是div5、2、div3這樣的組合
反省之後，發現此組合將會少考慮到Case 2 :會變成右移3。
-----
Sign in with Wallet
Connect another wallet