2020q3 Homework4 (quiz4)

contributed by < shauming1020 >

tags: homework

測驗 1

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 實作程式碼
  ​​​​int hammingDistance(int x, int y) {
  ​​​​x ^= y;
  ​​​​y = 0;
  ​​​​while (x) {
  ​​​​    y += (x & 1);
  ​​​​    x >>= 1;
  ​​​​}
  ​​​​return y;
  ​​​​}
  

LeetCode 477. Total Hamming Distance

• 暴力法

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 總數，因此

$totalsum=1\times 2+2\times 1+2\times 1+0\times 3=6$

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^{\prime }=(1101010),d_H(x,x^{\prime })=3$

  • Hamming Weight : 一個向量不是 0 的的地方有幾個

    e.g.

    $w_H(x)=3,w_H(x^{\prime })=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]

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

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

#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

#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 可能形如:

    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 質數即可

---