Try   HackMD

2020q3 Homework4 (quiz4)

contributed by < nelsonlai1 >

測驗 1

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

這題要算兩數間的 Hamming distance,而 XOR 後在原本相異的位元會變成 1,再用 popcount 就能算出 Hamming distance。

延伸問題

1. 舉出不使用 gcc extension 的 C99 實作程式碼

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

2. 練習 LeetCode 477. Total Hamming Distance

int totalHammingDistance(int* nums, int numsSize){ int result = 0, ones = 0; for (int i = 0; i < 30 ; i++) { for (int j = 0; j < numsSize; j++) { ones += ((nums[j] >> i) & 1); } result += ones * (numsSize - ones); ones = 0; } return result; }

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

這題最直接的方法應該是計算每對數字的 Hamming distance 再加起來,不過這樣就會超時了,所以要換一種解法。

當兩個數在同一個位元上有差別時才會產生 Hamming distance,而當 x + y 個數在同一個位元上有 x 個 1,y 個 0 時,這個位元能造成的 Hamming distance 是 x * y。

題目敘述中提到陣列中的數不超過 10^9,所以只檢查 30 個位元。計算每個位元共有多少 1 跟 0,再相乘後加到結果中,就能得到答案。

3. ECC & Hamming distance, Hamming weight

錯誤更正碼簡介中提到在資料傳輸時,可能會有干擾訊號形成錯誤。而錯誤更正碼的精神是在傳輸前先對資料做處理,以這裡介紹的方法為例,是在原本的資料上加上幾個額外的 bits。如此一來,只要錯誤小於一定的數量,就能夠更正回來。

Hamming distance : 兩個數間不一樣的 bits 有幾個。
Hamming weight : 一個數裡面 1-bits 有幾個 (popcount)。
裡面提到 x 和 x' 的 Hamming distance 是 x + x' 的 Hamming weight,其實就是本題的做法(文章中的加法指的是 XOR 運算)

Hamming codes, Part I 較容易理解,裡面提到一種叫做 Hamming code 的錯誤更正碼,可以改正一個錯誤 bits。
以 (15, 11)Hamming code (15 個 bits 中帶有 11 個有內容的 bits) 為例,

0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

第 1, 2, 4, 8 bits 作為 redundant bits,檢查錯誤用,第 0 個 bit 無作用(或是在 extended Hamming code 中檢查整體的 1-bits 是否為偶數)。

第 1, 2, 4, 8 bits 的值依照底下這張圖的規則來填入值,分別計算 Q1 ~ Q4 中藍色區塊的 1-bits 數量並調整第 1, 2, 4, 8 bits 的值來讓每個藍色區塊中的 1-bits 為偶數。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

當有一個錯誤發生時,便能透過檢查每個藍色區域中的 1-bits 數來找到錯誤發生的 bits。Q1, Q2 用來找到特定的 column,Q3, Q4 用來找特定的 row。

從圖中可以發現第 0 bit 不會被檢查到,所以無從判斷有沒有錯誤,為了解決第 0 bits 沒有用到的問題,extended Hamming code 會計算整體的 1-bits 數,並且調整第 0 bit 的值來讓整體的 1-bits 為偶數。這樣一來,如果有兩個或偶數個錯誤發生時,會觀察到整體的 1-bits 是偶數,但檢查藍色區域時會發現有錯,這時就能判斷傳輸時產生了偶數個錯誤。雖然不能更正錯誤,但可以發現錯誤並要求傳送端重新傳送。

Hamming codes, Part II 延續 part I 的內容,並說明如何實際寫成程式碼。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

這張圖表示 0 ~ 15 (0000 ~ 1111) 可以透過每個 bit 是 1 或 0 來判斷位於上面 Q1 ~ Q4 的哪個位置,假設第 4 個 bits 是 1,則位於 Q1 的藍色區域,反之則位於褐色區域。其他 bits 以此類推。

當一段資料傳來時,將資料中的 1-bits 位置找出來,並且將其全部做 XOR,就可以得到有問題的那個 bits 的位置,如下圖 :

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

而可以這樣做是因為 XOR 的特性,有偶數個 1-bits 時會輸出 0。
先從計算結果的第四個 bit 看起,第四個 bit 為 0 代表著 Q1 中藍色區域的 1-bits 是偶數,同時代表著有問題的位置在褐色區域,其他 bits 以此類推,所以這個結果正好是有問題的位置。

而如果現在要做 encode 也很類似,一樣將 1-bits 的位置做 XOR,接著調整第 1, 2, 4, 8 bits 的值來讓結果變成 0000。以影片中的 1010 為例子,將 1000 跟 0010 分別對 1 做 XOR(toggle 1 and 0) 就能讓結果變成 0000,因為如果要刪去一個做 XOR 的元素實際上也等同於再 XOR 一次,如圖所示 :

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

根據以上做法實作的 code :
解碼部分 :

uint16_t ecc(uint16_t n) { int flip = 0; for (int i = 0; i < 16; i++) { if ((n >> i) & 1) flip ^= i; } return flip ? n ^ (1 << (15 - flip)) : n; }

編碼 :

uint16_t encode(uint16_t n) { int mod = 0; uint16_t result = n; for (int i = 0; i < 16; i++) { if ((n >> i) & 1) mod ^= i; } while (mod != 0) { result ^= (1 << (15 - (mod & -mod))); mod ^= (mod & -mod); } return result; }

main function :

int main() { uint16_t ori = 7777; uint16_t noise, rec; printf("original message : "); for (int i = 12; i >=0; i--) { if (i == 11 || i == 7) continue; printf("%d", (ori >> i) & 1); } printf("\n"); ori = encode(ori); noise = ori ^ (1 << 2); rec = ecc(noise); printf("received message : "); for (int i = 12; i >=0; i--) { if (i == 11 || i == 7) continue; printf("%d", (rec >> i) & 1); } printf("\n"); }

結果 :

original message : 11101100001
received message : 11101100001

測驗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]]

其中 [-1,0,0,1,1,2,2] 代表第 0 到第 6 個 node 的 parent,也就是底下程式碼中的 int *parent

#include <stdlib.h> typedef struct { int **parent; 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 - 1] == -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 & (1 << i)) node = obj->parent[node][i]; return node; } void treeAncestorFree(TreeAncestor *obj) { for (int i = 0; i < obj->max_level; i++) free(obj->parent[i]); free(obj->parent); free(obj); }

TreeAncestor 這個 structure 中有兩個變數,分別是 parentmax_level
parent 是一個二維陣列,parent [i][j] 代表 i 這個 node 的第

2j 代祖先。
max_level 用來表示 j 的範圍大小,以 7 個節點為例,最大高度是 6,j 範圍是 0~2 (
6=21+22
),所以 max_level 是 3。

TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize) 中,
第 14~18 行將 obj->parent 做初始化,將每個都設成 -1。
19~20 行將輸入的 parent (第一代祖先)存在 obj->parent[i][0] 中。
22~31 行中,obj->parent[i][j] = obj->parent[i][j - 1] == -1 ? -1 : obj->parent[obj->parent[i][j - 1]][j - 1]; 先判斷 i 節點

2j1 代祖先是否不存在,不存在的話則
2j
代也不存在。反之
2j
代祖先則是 i 節點的
2j1
代祖先的
2j1
代祖先。
(這樣講可能有點拗口,可以想像你的曾曾祖父就是你的祖父的祖父。)
quit 則是來判斷若所有節點的第
2j
代祖先都不存在時,可以提前結束,因為之後的也會不存在。

有了以上概念後,int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k) 也不難懂了。當要找 node 的第 k 個祖先時,會以類似二進位的方式來搜尋。如果要找第 7 代時,會以
node = node 第

20 祖先 -> node = node 第
21
祖先 -> node = node 第
22
祖先的方式移動 node 最後找到目標節點。

延伸問題

在第 13 行計算 max_level 時多加了 1,是因為在第 22~31 行的迴圈使用 quit 作為終止條件,不這樣的話在 worst case (一條直線)下可能會存取到超過 array 範圍,然後就出錯了。因此第一個改動就是把第 22 行加上 j < max_level,就可以不用加 1 了。而這裡也可以順便把 max_level 這個變數直接用 obj->max_level 取代。

第二個可以改的地方是把 row, column 交換。原本需要 malloc(n * sizeof(int *))
malloc(obj->max_level * sizeof(int)),改完後變成 malloc(obj->max_level * sizeof(int *))malloc(n * sizeof(int))。差別在於 int 大小是 4 bytes,而 int* 大小是 8 bytes。因為 max_level 會比 n 小,所以這樣就能省下一些空間。
另一個好處是可以把原本的

for (int i = 0; i < parentSize; i++)
    obj->parent[i][0] = parent[i];

改成 obj->parent[0] = parent; 省下 for 迴圈的時間。

typedef struct { int **parent; int max_level; } TreeAncestor; TreeAncestor* treeAncestorCreate(int n, int* parent, int parentSize) { TreeAncestor *obj = malloc(sizeof(TreeAncestor)); obj->max_level = 32 - __builtin_clz(n); obj->parent = malloc(obj->max_level * sizeof(int *)); for (int i = 1; i < obj->max_level; i++) { obj->parent[i] = malloc(n * sizeof(int)); for (int j = 0; j < n; j++) obj->parent[i][j] = -1; } obj->parent[0] = parent; for (int i = 1; i < obj->max_level; i++) { int quit = 1; for (int j = 0; j < n; j++) { obj->parent[i][j] = obj->parent[i - 1][j] == -1 ? -1 : obj->parent[i - 1][obj->parent[i - 1][j]]; if (obj->parent[i][j] != -1) quit = 0; } if (quit) break; } return obj; } int treeAncestorGetKthAncestor(TreeAncestor* obj, int node, int k) { for (int i = 0; i < obj->max_level && node != -1; i++) if (k & (1 << i)) node = obj->parent[i][node]; return node; } void treeAncestorFree(TreeAncestor* obj) { for (int i = 0; i < obj->max_level; i++) free(obj->parent[i]); free(obj->parent); free(obj); }

測驗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; }

is_divisible 運用了 quiz2 的技巧判斷是否整除,當整除時回傳 1,其他則回傳 0。

length 用來決定要複製多長的字串,
當 i 是 3 或 5 的倍數,且非 15 的倍數時要複製四個字元 (Fizz or Buzz),
當 i 是 15 的倍數時要複製八個字元 (FizzBuzz),
其餘則複製兩個字元 (%u)。
所以這裡用 length = (2 << div3) << div5; 可以達到目的。

第 17 行可以從前面的敘述中知道,
當 i 是 3 的倍數時,start 要為 0。
當 i 是 5 的倍數且非 15 的倍數時,start 要為 4。
其餘時候 start 要為 8。
可以統整為,當有因數 3 時,MSG_LEN 要右移 3 “以上“,當有因數 5 時,要右移 1。所以 KK1 = div5, KK2 = div3, KK3 = 2 可以達到目的。

延伸問題

1. 評估 naive.c 和 bitwise.c 效能落差

根據提示,我把 source code 改成以下 :
naive.c : (if i % 15 == 0 不用加)

int main() { char buf[20]; for (unsigned int i = 1; i <= 100000000; i++) { if (i % 3 == 0) sprintf(buf, "Fizz"); if (i % 5 == 0) sprintf(buf, "Buzz"); if ((i % 3) && (i % 5)) sprintf(buf, "%u", i); } 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; char buf[20]; int main(int argc, char *argv[]) { for (size_t i = 1; i <= 100000000; 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 >> div5) >> (div3 << 2)], length); fmt[length] = '\0'; sprintf(buf, fmt, i); } return 0; }

結果 bitwise.c 的結果居然比較慢

Performance counter stats for './naive':

           3584.62 msec task-clock                #    1.000 CPUs utilized          
                18      context-switches          #    0.005 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
                51      page-faults               #    0.014 K/sec                  
     148,7757,0325      cycles                    #    4.150 GHz                    
     431,0389,3880      instructions              #    2.90  insn per cycle         
      73,3560,5643      branches                  # 2046.408 M/sec                  
         4543,6601      branch-misses             #    0.62% of all branches        

       3.585121376 seconds time elapsed

       3.584910000 seconds user
       0.000000000 seconds sys
Performance counter stats for './bitwise':

           5265.99 msec task-clock                #    1.000 CPUs utilized          
                13      context-switches          #    0.002 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
                49      page-faults               #    0.009 K/sec                  
     218,8159,0327      cycles                    #    4.155 GHz                    
     642,2565,2212      instructions              #    2.94  insn per cycle         
     110,4922,7345      branches                  # 2098.223 M/sec                  
         4712,5830      branch-misses             #    0.43% of all branches        

       5.266343370 seconds time elapsed

       5.266260000 seconds user
       0.000000000 seconds sys

測驗4

這題要加速運算 size_t blockidx = offset / PAGE_QUEUES; 這行指令。
其中 PAGE_QUEUES 可能的值是(1 or 2 or 3 or 4 or 5 or 6 or 7 or 8) ×

2n, 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 }

__builtin_ffs(x) 這個 function 用來表示 x 二進位的最後一個 1 的位置。所以
((__builtin_ffs(x)) - 1) 的值等同於 x 的 trailing 0-bits。從第 5,6 行可以看到 blockidx 會先除以 divident(PAGE_QUEUES) 的 2^N 因數,接著 divident 也會把自己的 2^N 因數去除。

而最後的 switch (divident) 就是將其餘的因數分 case 做處理(也就是再除以剩下的因數)。由於 PAGE_QUEUES 的範圍是固定的,所以去除 2^N 因數後剩下的因數只有 3, 5, 7 而已。