contributed by < nelsonlai1
>
這題要算兩數間的 Hamming distance,而 XOR 後在原本相異的位元會變成 1,再用 popcount 就能算出 Hamming distance。
這題最直接的方法應該是計算每對數字的 Hamming distance 再加起來,不過這樣就會超時了,所以要換一種解法。
當兩個數在同一個位元上有差別時才會產生 Hamming distance,而當 x + y 個數在同一個位元上有 x 個 1,y 個 0 時,這個位元能造成的 Hamming distance 是 x * y。
題目敘述中提到陣列中的數不超過 10^9,所以只檢查 30 個位元。計算每個位元共有多少 1 跟 0,再相乘後加到結果中,就能得到答案。
錯誤更正碼簡介中提到在資料傳輸時,可能會有干擾訊號形成錯誤。而錯誤更正碼的精神是在傳輸前先對資料做處理,以這裡介紹的方法為例,是在原本的資料上加上幾個額外的 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 為偶數。
當有一個錯誤發生時,便能透過檢查每個藍色區域中的 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 的內容,並說明如何實際寫成程式碼。
這張圖表示 0 ~ 15 (0000 ~ 1111) 可以透過每個 bit 是 1 或 0 來判斷位於上面 Q1 ~ Q4 的哪個位置,假設第 4 個 bits 是 1,則位於 Q1 的藍色區域,反之則位於褐色區域。其他 bits 以此類推。
當一段資料傳來時,將資料中的 1-bits 位置找出來,並且將其全部做 XOR,就可以得到有問題的那個 bits 的位置,如下圖 :
而可以這樣做是因為 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 一次,如圖所示 :
根據以上做法實作的 code :
解碼部分 :
編碼 :
main function :
結果 :
給你一棵樹,樹上有 n 個節點,編號自 0 到 n − 1。樹以父節點陣列的形式提供,其中
parent[i]
是節點 i 的父節點。樹的根節點是編號為 0 的節>點。請設計
treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
函式,回傳節點 node 的第
k 個祖先節點。若不存在這樣的祖先節點,回傳-1
。樹節點的第 k 個祖先節點是從該節點到根
節點路徑上的第 k 個節點
input 範例 :
其中 [-1,0,0,1,1,2,2] 代表第 0 到第 6 個 node 的 parent,也就是底下程式碼中的 int *parent
TreeAncestor
這個 structure 中有兩個變數,分別是 parent
跟 max_level
。
parent
是一個二維陣列,parent [i][j]
代表 i 這個 node 的第 代祖先。
max_level
用來表示 j 的範圍大小,以 7 個節點為例,最大高度是 6,j 範圍是 0~2 (),所以 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 節點 代祖先是否不存在,不存在的話則 代也不存在。反之 代祖先則是 i 節點的 代祖先的 代祖先。
(這樣講可能有點拗口,可以想像你的曾曾祖父就是你的祖父的祖父。)
quit 則是來判斷若所有節點的第 代祖先都不存在時,可以提前結束,因為之後的也會不存在。
有了以上概念後,int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
也不難懂了。當要找 node 的第 k 個祖先時,會以類似二進位的方式來搜尋。如果要找第 7 代時,會以
node = node 第 祖先 -> node = node 第 祖先 -> node = node 第 祖先的方式移動 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 小,所以這樣就能省下一些空間。
另一個好處是可以把原本的
改成 obj->parent[0] = parent;
省下 for 迴圈的時間。
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
可以達到目的。
根據提示,我把 source code 改成以下 :
naive.c : (if i % 15 == 0
不用加)
bitwise.c :
結果 bitwise.c 的結果居然比較慢
這題要加速運算 size_t blockidx = offset / PAGE_QUEUES;
這行指令。
其中 PAGE_QUEUES
可能的值是(1 or 2 or 3 or 4 or 5 or 6 or 7 or 8) × , n from 1 to 14。
__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 而已。