---
title: 2020q3 Homework4 (quiz4)
tags: sysprog
---

# 2020q3 Homework4 (quiz4)
contributed by < `TsundereChen` >

> [Homework4 (quiz4)](https://hackmd.io/@sysprog/2020-quiz4)

## 題目 `1`
題目 code

int hammingDistance(int x, int y) {
    return __builtin_popcount(x OP y);
}

- 解釋上述程式碼運作原理，並舉出不使用 gcc extension 的 C99 實作程式碼
- 運算 hamming distance -> 找兩個 variable 中 bit 不同的地方
- 不同者為 1，相同者為 0 -> XOR
- 所以 `OP = ^`
- 不使用 gcc extension 的 C99 實作程式碼

int hammingDistance(int x, int y){
  int result = 0;
  for (int i = x ^ y; i != 0; i >>= 1) {
    if (i & 0x1)
      result++;
  }
  return result;
}

- 練習 [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)，你應當提交 (submit) 你的實作 (C 語言實作)，並確保執行結果正確且不超時
- 上面的程式在 LeetCode 跑到較大的測資會發生 TLE，沒有頭緒之下只好去找看看有什麼實作 bitcount 的方法
- 搜尋了一下又找到了 [Bit Twiddling Hacks](http://graphics.stanford.edu/~seander/bithacks.html)，然後發現自己的寫法被列在 `naive way`
- Okay，來看看其他人是怎麽解決這問題的，首先注意到 [Counting bits set, Brian Kernighan's way](http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan)
- Kernighan 的方式被列在 K&R C 之中，然而這個方式一開始是 Peter Wegner 在 CACM 3(1960), 322 發表的
- 程式十分簡潔，如下

          unsigned int v;
          unsigned int c;
          for(c = 0; v; c++)
              v &= v - 1;

- 思考一下程式的邏輯，以 `13 (1101)` 為例
- 第一次進迴圈是 `v &= v - 1`， `v` 是 `1101`， `v - 1` 是 `1100`， `&` 後是 `1100`
- 下一次執行迴圈時， `v` 是 `1100`， `v - 1` 是 `1011`， `&` 後是 `1000`
- 再下一次執行時， `v` 是 `1000`， `v - 1` 是 `0111`， `&` 後是 `0000`
- 所以 `c` 是 `3`
- 真是簡潔的方法，送進去 LeetCode 看看會不會過關?
- 一樣 TLE，但這次跑到更後面的測資了
- 再來找其他方法
- 再來看下一個方法，製表與查表
- 先看程式

        static const unsigned char BitsSetTable256[256] =
        {
        #define B2(n) n,     n+1,     n+1,     n+2
        #define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
        #define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
        B6(0), B6(1), B6(1), B6(2)
        }
        
        unsigned int v;
        unsigned int c;
        c = BitsSetTable256[v & 0xff] + BitsSetTable256[(v >> 8) & 0xff] +
            BitsSetTable256[(v >> 16) & 0xff] + BitsSetTable256[v >> 24];

- 先製備一個 0 ~ 255 的 bitset table，然後要找某數值的 bit 的時候只要進去查表就好
- 看起來也是很快的方法，可是不知道查表跟運算哪個方式比較快?
:::info
TODO 試看看比較查表和運算的速度
:::
- 把查表的方式放進 LeetCode 試看看?
- 還是 TLE，但又比 Kernighan 的方式跑到更大的測資了
- 接下來是 [counting bits set, in parallel](http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel)
- 這一段在看的時候很沒頭緒，直到看到[這篇文章](http://github.tiankonguse.com/blog/2014/11/16/bit-count-more.html#menuIndex5)
- 透過把相鄰的數字相加，最後取得正確的答案，以 `13(1101)` 這個數字為例
- 我們先 2 bit 互相相加，把 `1101` 看成 `11 01`
- 我們希望把相鄰的數值相加，例如 `11` 有兩個 bit，所以我們要用 `2(10)` 來表達，而 `01` 只有一個 bit，所以用 `1(01)` 表達
- 問題在於，我們要怎麽把這樣 bit 的資訊存在原本的數值中
- 透過特殊的 mask，我們可以把 bit 資訊存回原本的數值中
- 我們都把 bit 資訊存在每個 pair 的最低位，如果一個 pair 有 N 個 bit，那這個 pair 的 MASK 從 LSB 開始的 `N/2` bit 都會是 1
- 這樣講好像還是很含糊，實際計算一次

              1101 >> 1 = 0110
              
              1101 & 0101 = 0101
              0110 & 0101 = 0100
              
              0101 + 0100 = 1001 (看成 10 和 01， 10 代表前兩個 bit 有 2 個 1， 01 代表後兩個 bit 有 1 個 1)
              
              1001 >> 2 = 0010
              
              1001 & 0011 = 0001
              0010 & 0011 = 0010
              
              0001 + 0010 = 0011 (代表 4 個 bit 內有 3 個 1)

- 相關鏈接:
- [Ian Ashdown's newsgroup post](https://groups.google.com/g/comp.graphics.algorithms/c/ZKSegl2sr4c/m/QYTwoPSx30MJ)
- [BIT WISE OPERATIONS - GILLIES MILLER METHOD OF SIDEWAYS ADDITION](http://shankudada.blogspot.com/2014/12/bit-wise-operations-gillies-miller.html)
- 再放進 LeetCode 看結果
- 雖然全部的測資都跑完了，但依然 TLE
- 是不是不該用 bitwise 做這個題目...?
- 計算每個 bit 出現 1 的次數
- 上網搜尋了一下題目，發現了這個方法
- 以 `4, 14, 2, 1 (0100, 1110, 0010, 0001)` 為例

          0100 (4)
          1110 (14)
          0010 (2)
          0001 (1)

- 上面的數值中
- 第 0 個 bit 有一個 `1` 三個 `0`
- 在比較這個 bit 的時候，會有三個組合使 Hamming Distance 在這個 bit 為 1
- 第 1 個 bit 有兩個 `1` 兩個 `0`
- 同上，會有四個組合使 Hamming Distance 為 1
- 第 2 個 bit 有兩個 `1` 兩個 `0`
- 第 3 個 bit 有一個 `1` 三個 `0`
- 我們可以發現，只要找出 `1` 和 `0` 分別出現幾次，接下來算總共會有多少個 `1` 與 `0` 的組合即可
- `1` 出現的數量乘上 `0` 出現的數量
- 而由於我們已經知道 array 的長途，故只要計算 `1` 出現的數量， `numsSize - N` 就是 `0` 出現的數量
- 這樣就能計算出 Hamming Distance 了

          int bits[32] = {0};
          for(int i = 0; i < numsSize; i++){
              for(int j = 0; j < 32; j++){
                  if(nums[i] & 0x1) bits[j]++;
                      nums[i] >>= 1;
              }
          }
          int result = 0;
          for(int i = 0; i < 32; i++){
              result += (bits[i] * (numsSize - bits[i]));
          }
          return result;

- 研讀[錯誤更正碼簡介](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`
題目 code

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

- 解釋上述程式碼運作原理，指出可改進的地方，並實作對應的程式碼
- `typedef struct TreeAncestor`
- 用來定義樹的結構，每個樹有 `AAA` 和 `int max_level`
- `max_level` 是用來記錄樹的最大深度
- 從程式中可以推斷 `AAA` 是 `int (*?)parent`，但不知道是 `指標`、`指標的指標` 還是 `指標的指標的指標`
- 觀察底下的程式，可以發現到類似 `obj->parent[i][j]` 的用法，所以可以知道是 `指標的指標`，故 `AAA = int **parent`
- `TreeAncestor *treeAncestorCreate()`
- 用來建立一顆樹
- 首先先建立樹所需要的空間
- `int max_level = 32 - __builtin_clz(n) + 1`
- 這裡用來計算最深的深度，利用 `__builtin_clz` 可以知道該會是幾層
- 每層的第一個 node 都是 `pow(2, 層數)`，而在每一層的節點都不會超過 `pow(2, 層數 + 1)`，所以可以利用 `__builtin_clz` 計算層數
- 這裡 `+1` 是為了接下來的 for loop，在 function 最後有修正 `max_level`
- 第一個 for loop
- 用來初始化 `obj->parent` 變數，先把每個數值都賦值 `-1`
- 第二個 for loop
- 用來初始化 `obj->parent[i][0]`，由於題目已經先給我們每個節點的第一個祖先是什麼了，所以我們可以直接填進去
- 第三個 for loop
- 用來計算第二與更高的祖先
- 從第二個祖先開始算起，依序走訪每個節點，在走訪過程中，我們要判斷我們是不是已經走到 root 了
- `obj->parent[i][j] = obj->parent[i][j + BBB] == -1 ? -1 : obj->parent[obj->parent[i][j - 1]][j - 1]`
- Keyword: [Binary Lifting](https://codeforces.com/blog/entry/74847)
- 這裡的 j 並非代表前 j 個，而是 $2^j$ 個
- 透過只記錄每個節點的 $2^j$ 個祖先，我們可以提升查詢的速度，也降低記憶體開銷，折衷
- 範例
- 第 5(101) 個祖先可以看成找第 4(100) 個祖先的第 1(001) 個祖先
- 第 7(111) 個祖先可以看成找第 4(100) 個祖先的第 2(010) 個祖先的第 1(001) 個祖先
- 如果有任何祖先的更動記錄，就不要打破 for loop，否則結束
- 最後是修正與賦值 `max_level`，然後回傳 `obj`
- `int treeAncestorGetKthAncestor()`
- 尋找某個 node 的第 k 個祖先
- 由於上面在記錄祖先時是使用 $2^j$ 的方式儲存，故在尋找祖先時也需要利用 $2^j$ 的形式尋找，故在這裡使用 `1 << i`
- `void treeAncestorFree()`
- 依序釋放所有建立的記憶體空間
- 在 `treeAncestorCreate` 函式內部，若干記憶體被浪費，請撰寫完整測試程式碼，並透過工具分析
- 嘗試更改 `max_level`
- 在 [LeetCode 1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/) 提交你的實作，你應該要在 C 語言項目中，執行時間領先 75% 的提交者
## 題目 `3`
題目 code

### naive.c
#include <stdio.h>
int main() {
    for (unsigned int i = 1; i < 100; i++) {
        if (i % 3 == 0) printf("Fizz");
        if (i % 5 == 0) printf("Buzz");
        if (i % 15 == 0) printf("FizzBuzz");
        if ((i % 3) && (i % 5)) printf("%u", i);
        printf("\n");
    }
    return 0;
}

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

- 解釋上述程式運作原理並評估 `naive.c` 和 `bitwise.c` 效能落差
- 避免 `stream I/O` 帶來的影響，可將 `printf` 更換為 `sprintf`
- 分析 [Faster remainders when the divisor is a constant: beating compilers and libdivide](https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/) 一文的想法 (可參照同一篇網誌下方的評論)，並設計另一種 bitmask，如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」，然後再改寫 bitwise.c 程式碼，試圖運用更少的指令來實作出 branchless
- 參照 [fastmod: A header file for fast 32-bit division remainders on 64-bit hardware](https://github.com/lemire/fastmod)
## 題目 `4`
題目 code

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

- 解釋程式運算原理，可搭配 Microsoft Research 的專案 [snmalloc](https://github.com/microsoft/snmalloc) 來解說
- 對應的原始程式碼 [src/mem/sizeclass.h](https://github.com/microsoft/snmalloc/blob/master/src/mem/sizeclass.h#L54-L145)
- 練習 [LeetCode 51. N-Queens](https://leetcode.com/problems/n-queens/)，應選擇 C 語言並善用上述的 `__builtin_ffs`，大幅降低記憶體開銷