# 2020q3 Homework4 (quiz4)

contributed by < ddj5523fa >

---

### 想法 & 思考

#### 測驗一

題目:

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程式碼:

#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:

digraph skew_BST {
    size="5"
    node [fontname="Arial"];
    0 -> 1;
    1 -> 2;
    2 -> 3;
    3 -> 4;
    4 -> 5;
}

**parent 指向的記憶體空間的內容初始化後長相:
(下圖直接跳到已經補上了node的第一個parent)

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是因為:

 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]; 為依據。

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

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

依據題目先前的程式碼與觀察提示:

#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。

-----