2020q3 Homework4 (quiz4)

contributed by < RusselCK >

tags: `RusselCK`

指標＆數值系統＆ Bitwise 練習題

Q1. LeetCode 461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

使用 `__builtin_popcount` 實作



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

x ^ y 可以將 x y兩者對應位置不同的 bits 顯示出來，其 1 的個數即為 Hamming distance

Q1. 進階題

不使用 gcc extension 實作

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

LeetCode 477. Total Hamming Distance

find the total Hamming distance between all pairs of the given numbers.

範例

Input: 4, 14, 2

Output: 6

the 4 is 0100, 14 is 1110, and 2 is 0010
So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

超時版

int totalHammingDistance(int* nums, int numsSize){
    int total = 0;
    for(int i=0; i < numsSize ; i++){
        for (int j= i+1 ; j < numsSize ; j++){
            total += __builtin_popcount(nums[i] ^ nums[j]);
        }
    }
    return total;
}

兩兩一組求 Hamming Distance ，最後再加總
共需要算
$(\binom{n}{2}) = \frac{n * (n - 1)}{2}$ 次

不超時版

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

04 = ( 0100 )
14 = ( 1110 )
02 = ( 0010 )

每個 bit 的 #兩兩不同 = ( #1 ) * ( #0 ) = ( #1 ) * ( #nums - #1 )
最後加總 32 個 bit 的 #兩兩不同
效能評估：
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 Weight

錯誤更正碼( Error–Correcting Codes )

由來

1948年以前, 大家在做通訊系統的時候, 都只想到要如何使訊號接收得比較好, 比如把天線加大, 或者把訊號傳遞的功率加大, 但這些都是在物理上做改進
1948年 Claude Shannon 寫了一篇論文叫做 A mathematical theory of communications, 他說事實上我們不必這樣做, 很多情形只要在資料上做手腳, 只要傳資料的速率小於每個通道特有的量( 通道容量 channel capacity ), 就一定有辦法讓資料錯誤的機率很小, 要多小都可以
因為他提出了這件事, 後來造成了整個領域的發展, 這個領域叫做訊息理論 (information theory)

Single–Error Correcting(SEC) Codes / (7, 4) Hamming code

只能改一個錯
(7, 4) : 全部長度是7, 只有4個 bits是原來要傳的資料
- Hamming 在 1950 年所發明的

  Input = d1 d2 d3 d4 p1 p2 p3 

  A = { d1, d2, d4, p1 }
  B = { d1, d3, d4, p2 }
  C = { d2, d3, d4, p3 }

正確的情形：任一集合中，#of 1 is even
- d1 d2 d3 d4 是原來要傳的資料
若有 1 個 bit 傳錯，根據規則可以很快的找出來並修正

Hamming codes 的數學結構

定義 modulo 2 運算
- 先加起來或乘起來後，再除以 2 取餘數
由 (7, 4)Hamming code 規則可以得到：
- 為了與文章一致， ( d4 d3 d2 d1 p3 p2 p1 ) 對應到 ( x1 x2 x3 x4 x5 x6 x7)
  
  ${\begin{matrix} x 1 + x 2 + x 3 + x 5 = 0 \\ x 1 + x 2 + x 4 + x 6 = 0 \\ x 1 + x 3 + x 4 + x 7 = 0 \end{matrix}, d i, p j \in {\begin{matrix} 0, 1 \end{matrix}}$
  線性方程式寫成矩陣
  
  $H = [\begin{matrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{matrix}]$
$C = {\begin{matrix} 所有 C o d e w o r d s \end{matrix}} =$
$H$ 的
$N u l l s p a c e$
- $d i m (H) = 7 - r a n k (H) = 7 - 3 = 4$
- 只要給定其中 4 個 bits ，另外 3個 bits 會對應而生
- 這 4 個 bits 共有
  $2^{4} = 16$ 種可能
  $= | \begin{matrix} C \end{matrix} |$ ( codewords )

Syndrome ( 徵狀 )

$x$ : codeword

$e$ : 錯誤向量

計算 syndrome

$H y^{T} = H x^{T} + H e^{T}$

$因為 x 是 c o d e w o r d ，所以 H x^{T} = 0$
代表 syndrome 只跟錯誤向量有關, 跟傳哪個 codeword 無關
舉例： $y = x + e $ = ( 1101000 ) = ( 1101010 ) + ( 0000010 )

s^{T} = H y^{T} = [\begin{matrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{matrix}] [\begin{matrix} 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}] = [\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}]

根據錯誤的 bit 不同，
$s^{T}$ 的結果也會隨之改變，整理如下：

錯誤的 bit	x1	x2	x3	x4	x5	x6	x7
$e$	(1000000)	(0100000)	(0010000)	(0001000)	(0000100)	(0000010)	(0000001)
$s^{T}$	$[\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}]$	$[\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}]$	$[\begin{matrix} 1 \\ 0 \\ 1 \end{matrix}]$	$[\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}]$	$[\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}]$	$[\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}]$	$[\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}]$

每一個 syndrome 就對應到一種錯的情況
- 我們只要知道它的徵狀是什麼, 就可以知道錯在那裡, 然後把它改正過來

Hamming Distance & Hamming Weight

Hamming distance = 兩個向量不一樣的地方有幾個
Hamming weight = 一個向量不是 0 的的地方有幾個
x + y 的 Hamming weight = x 和 y 的 Hamming distance
- modulo 2 加法
- 加起來之後不為0 的 bits 的個數＝它們之間不同的 bits 的個數
minimum distance
- 任何在
  $C$ 中的兩個不同的 codewords 的 Hamming distance, 它們之中最小的值
  
  $d_{m i n} C = m i n d_{H} (x, y) x, y \in C, x \neq y$
minimum weight
- 所有不為0的 codewords, 它的 Hamming weight 的最小值
  
  $w_{m i n} C = m i n w_{H} (x) x \in C, x \neq 0$
also, minimum distance = minimum weight, i.e.
$d_{m i n} C = w_{m i n} C$

$H = [\begin{matrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{matrix}]$
minimum distance
$d_{m i n} C = w_{m i n} C$ 是多少？
- 1 ?
  - NO! 因為
    $H$ 的任一個 column 中都不存在
    $\vec{0}$
- 2 ?
  - NO! 因為
    $H$ 的任兩個 column 相加不為
    $\vec{0}$
- 3 ?
  - Yes! 取第 1、2、7 個 column 相加，可以得到
    $\vec{0}$

如果要改
$t$ 個錯, 它的 minimum distance 至少要
$2 t + 1$
證明
- 兩球的中心分別為 codeword
  $x$ and
  $x^{'}$
  球內包含所有與中心的 Hamming distance 小於等於
  $t$ 的 binary vector
- 因為有
  $t$ 個錯要改，所以兩個球不能碰在一起，因此，兩球距離最小值為 1 ( 交集為空集合 )
  - 若兩球碰在一起，會有一點和
    $x$ 及
    $x^{'}$ 的距離都小於
    $t$ ，
    此時便不知道要修正為
    $x$ 還是
    $x^{'}$ ，導致不能改
    $t$ 個錯
    
    $\Rightarrow$ x 和 x' 的距離至少要
    $t + 1 + t = 2 t + 1$
    
    $\Rightarrow$ 任兩個 codewords 的距離至少要
    $2 t + 1$

研讀 Reed–Solomon error correction

閱讀 Linux 核心原始程式碼的 lib/reed_solomon 目錄，抽離程式碼為單獨可執行的程式，作為 ECC 的示範

Q2. LeetCode 1483. Kth Ancestor of a Tree Node

You are given a tree with n nodes numbered from 0 to n-1 in the form of a parent array where parent[i] is the parent of node i.
The root of the tree is node 0.
Implement the function getKthAncestor(int node, int k) to return the k-th ancestor of the given node.
If there is no such ancestor, return -1.
The k-th ancestor of a tree node is the k-th node in the path from that node to the root.

Binary Lifting 的實作：





















































#include <stdlib.h>

typedef struct {
    AAA; // AAA = int **parent
    int max_level;
    // int n;
} 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 // 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;
    // obj->n = n;
    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)) // CCC = 1 << i
            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);
}

範例

Input:
["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

Output:
[null,1,0,-1]

Explanation:
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);

treeAncestor.getKthAncestor(3, 1);  // returns 1 which is the parent of 3
treeAncestor.getKthAncestor(5, 2);  // returns 0 which is the grandparent of 5
treeAncestor.getKthAncestor(6, 3);  // returns -1 because there is no such ancestor

Binary lifting :
- the 7th ancestor = the 4th ancestor of the 2nd ancestor of the 1st ancestor
  - 與二進制相關
    
    7 = 4 + 2 + 1 =
    $2^{2} + 2^{1} + 2^{0}$
- the
  $2^{j}$ -th ancestor = the
  $2^{j - 1}$ -th ancestor of the
  $2^{j - 1}$ -th ancestor
  
  the 8th ancestor = the 4th ancestor of the 4th ancestor
  - 可改良int treeAncestorGetKthAncestor()
程式碼解析：

`TreeAncestor treeAncestorCreate(int n, int parent, int parentSize)`









typedef struct {
    AAA; 
    int max_level;
} TreeAncestor;

TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
    reeAncestor *obj = malloc(sizeof(TreeAncestor));
    obj->parent = malloc(n * sizeof(int *));

由 #11 可以知道，AAA 的名字為 parent ，而且是型態為 (int *) 的指標
由 #15、#17可以知道，obj->parent是 二維陣列
因此 AAA = int **parent






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

By Binary Lifting, for each node, 記錄
$2^{k}$ -th ancestor,
$k = 0, 1, 2, . . ., ⌊ l o g (n) ⌋$
因此，我們共需要n *
$(⌊ l o g (n) ⌋ + 1)$ 的二維陣列

以 8 bits 為例， n = 7 = ( 0000 0111 )₂

$⌊ l o g (n) ⌋ + 1 = ⌈ l o g (n) ⌉ = ⌈ l o g (7) ⌉$ = 3 = 8 - __builtin_clz(7)

將 obj->parent 做成 n * max_level 的二維陣列：obj->parent[n][max_level]
- 所有初始值設為 -1 ( i.e. no ancestor )

範例

obj->parent[7][4] = {
                     [-1,-1,-1,-1],
                     [-1,-1,-1,-1],
                     [-1,-1,-1,-1],
                     [-1,-1,-1,-1],
                     [-1,-1,-1,-1],
                     [-1,-1,-1,-1],
                     [-1,-1,-1,-1],
                    }

Why max_level 比預想的多 1 ?


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

parent[i] 存放 node_i 的父親 ( i.e. The 1-th ancestor ) 的位置

obj->parent[i][0] 存放 node_i 的 1-th ancestor
for 迴圈的終止式用 parentSize 來判斷而非 n
- 因為 input 提供有關 ancestor 的資料只有 parent[]
- 若
  $n \neq p a r e n t S i z e$ 且以 n 來判斷，會出現 parent[]沒充分使用或資料不足的情況

範例

obj->parent[7][4] = {
                     [-1,-1,-1,-1],
                     [0,-1,-1,-1],
                     [0,-1,-1,-1],
                     [1,-1,-1,-1],
                     [1,-1,-1,-1],
                     [2,-1,-1,-1],
                     [2,-1,-1,-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;
    }

設置 obj->parent[i][1:max_level] 的資料

For each node, the

2^{j}

-th ancestor = the

2^{j - 1}

-th ancestor of the

2^{j - 1}

-th ancestor

obj->parent[i][j] = obj->parent[obj->parent[i][j - 1]][j - 1]
前提： obj->parent[i][j - 1] 不為 -1
因此， BBB = (-1)

範例

obj->parent[7][4] = {
                     [-1,-1,-1,-1],
                     [0,-1,-1,-1],
                     [0,-1,-1,-1],
                     [1,0,-1,-1],
                     [1,0,-1,-1],
                     [2,0,-1,-1],
                     [2,0,-1,-1],
                    }

#23、#30：若 quit == 1，跳出 for 迴圈
- #28：只要當下檢查的欄位不為 -1 ，代表還有欄位可能需要修改，不能跳出 for 迴圈，設置 quit = 0


    obj->max_level = max_level - 1;

Why max_level 又要 - 1 ?
- 代表先前預想的 max_level 沒有錯
- 可能是 #22 ~ #31 有改進空間


    return obj;

完成設置，回傳 obj

善用 cpp=行號 的標注方式，避免逐行輸入行號，後者對之後的編撰無益。

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 →

jserv

`int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)`








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)) // CCC = 1 << i
            node = obj->parent[node][i];
    return node;
}

k = 7 = ( 0000 0111 )₂
7th = ( 1th 的 2th ) 的 4th

by Binary Lifting, CCC = 1 << i

for循环中的i++和++i有什么区别

Q2. 進階題

指出可改進的部份

在 void treeAncestorFree(TreeAncestor *obj) 中有出現 obj->n
代表 TreeAncestor struct 等地方需要修改：

typedef struct {
    ...
    int n;
} TreeAncestor;

TreeAncestor* treeAncestorCreate(int n, int* parent, int parentSize) {
    TreeAncestor *obj = malloc(sizeof(TreeAncestor));
    ...
    obj->n = n;
}

效能評估：

修改 for 迴圈中止條件


    for (int j = 1;; j++) {

因為沒有中止條件，會導致程式多進一次 for 迴圈
改進方式：
- #14 改為 int max_level = 32 - __builtin_clz(n);
- 設中止條件為 j < max_level
- #33 改為 obj->max_level = max_level;
效能評估：
- 在 C 語言項目中，執行時間領先 78.29% 的提交者

改用 bit array 來記錄

Q3. FizzBuzz

從 1 數到 n
- 如果是 3的倍數，印出 “Fizz”
- 如果是 5 的倍數，印出 “Buzz”
- 如果是 15 的倍數，印出 “FizzBuzz”
- 如果都不是，就印出數字本身

直覺的實作: (`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 觀察

#define MSG_LEN 8
char fmt[MSG_LEN + 1];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");

我們若能精準從給定輸入 i 的規律去控制 start 及 length，即可符合 FizzBuzz 題意:

 string literal: "fizzbuzz%u"
         offset:  0   4   8

bitwise 的實作: (`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);
                                // KK1 = div5 ; KK2 = div3 ; KK3 = 2 ;
        fmt[length] = '\0';

        printf(fmt, i);
        printf("\n");
    }
    return 0;
}

程式碼解析：







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;


        uint8_t div3 = is_divisible(i, M3);
        uint8_t div5 = is_divisible(i, M5);

div3、div5 分別可知道 i 是否為 3 或 5 的倍數
- 若是，則為 1
- 若否，則為 0
除法判別可參考 quiz2 Q3 及 Q4


#define MSG_LEN 8




        unsigned int length = (2 << div3) << div5;

        char fmt[MSG_LEN + 1];
        strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);

根據題目和程式碼，可得下表：

`div3`	`div5`	`length`	`(( 1000 ) >> KK1) >> (KK2 << KK3)`
1	0	4	0 = ( 0000 ) = 8 >> ( 3 or more )
0	1	4	4 = ( 0100 ) = 8 >> 1
1	1	8	0 = ( 0000 ) = 8 >> ( 3 or more )
0	0	0	8 = ( 1000 )

若 div5 = 1 ，則 MSG_LEM >> 1
若 div3 = 1 ，則 MSG_LEM >> ( 3 or more )
綜合上述，KK1 = div5, KK2 = div3, KK3 >= 2

Q4. 除數為 `PAGE_QUEUES` 的除法

整數 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>
size_t blockidx = offset / PAGE_QUEUES;

預先進行計算，避免整數除法指令的使用:

(假設在 x86_64 硬體執行 GNU/Linux 並透過 gcc/clang 編譯)















#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
    // case 3: blockidx /= 3; 
    //           break;
    // case 5: blockidx /= 5; 
    //           break;
    // case 7: blockidx /= 7; 
    //           break;
}

其中， CASES 可能形如

          case 2: blockidx /= 2; 
              break;

這樣的組合，請用最少的 case-break 敘述做出同等 size_t blockidx = offset / PAGE_QUEUES; 效果的程式碼。

__builtin_ffs(x)
- Returns one plus the index of the least significant 1-bit of x
  ( 返回右起第一個 1 的位置 )
- if x is zero, returns zero.

觀察 PAGE_QUEUES 的範圍
- (1 or 2 or 3 or 4) = (
  $2^{0}$ or
  $2^{1}$ or
  $3 \times 2^{0}$ or
  $2^{2}$ )
- (5 or 6 or 7 or 8) × (
  $2^{n}$ ), n from 1 to 14
  = (
  $5 \times 2^{0}$ or
  $3 \times 2^{1}$ or
  $7 \times 2^{0}$ or
  $2^{3}$ ) × (
  $2^{n}$ ), n from 1 to 14
PAGE_QUEUES 可以歸納出另一種形式：
- 1 × (
  $2^{n}$ ), n = 0, 1, 2 and 4 ~ 17
- 3 × (
  $2^{n}$ ), n = 0 and 2 ~ 15
- ( 5 or 7 ) × (
  $2^{n}$ ), n = 1 ~ 14
觀察上述形式，可以發現
- 除以 PAGE_QUEUES = 除以 (1 or 3 or 5 or 7) × (
  $2^{n}$ )
- 因此，可以先處理除以 (
  $2^{n}$ ) 部份，再處理除以 (3 or 5 or 7)
  - 任何數除以 1 等於本身，不用再另外計算
程式碼解析：





#define ffs32(x)  ((__builtin_ffs(x)) - 1)
size_t blockidx;
size_t divident = PAGE_QUEUES;
blockidx = offset >> ffs32(divident);
divident >>= ffs32(divident);

#2 : fs32(x) =
$2^{n}$ 中的
$n$
- __builtin_ffs(x) - 1 = x 最右的 1 後面有幾個 0
#5 : 被除數除以
$2^{n}$ ( i.e. 右移
$n$ )
#6 : 除數除以
$2^{n}$ ( i.e. 右移
$n$ )








switch (divident) {
    case 3: blockidx /= 3; 
              break;
    case 5: blockidx /= 5; 
              break;
    case 7: blockidx /= 7; 
              break;
}

處理除以 (3 or 5 or 7)

Q4. 進階題

LeetCode 51. N-Queens

善用 __builtin_ffs，大幅降低記憶體開銷

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

範例

Input: 4
Output: [
   [".Q..",  // Solution 1
    "...Q",
    "Q...",
    "..Q."],

   ["..Q.",  // Solution 2
    "Q...",
    "...Q",
    ".Q.."]
]

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Backtracking 法：







































































size_t ways[] = {1, 1, 0, 0, 2, 10, 4, 40, 92, 352,
    724, 2680, 14200, 73712, 365596, 2279184, 14772512, 
    95815104, 666090624, 4968057848, 39029188884, 314666222712, 
    2691008701644, 24233937684440, 227514171973736, 2207893435808352, 
    22317699616364044, 234907967154122528};

int N;
char*** res;
int* QueensPos;
int w;

bool CheckQueen(int row,int col){
    for(int i=0; i < row; i++){
        if (QueensPos[i] == col || abs(QueensPos[i] - col) == abs(row - i))
            return false;
    }
    return true;
}

void PushAnswer(){
    char* queen = malloc((N + 1) * sizeof(char));
    queen[N] = '\0';
    for (int i = 0; i< N; i++){
        for(int j = 0; j< N; j++){
            queen[j] = (QueensPos[i]==j) ? 'Q' : '.';
        }
        memcpy(res[w][i], queen, N + 1);        
    }
    free(queen);
    w++;
}

void NQueens(int row){
    
    if(w == ways[N]){
        return;
    }
    
    for (int j=0; j < N ; j++){
        if(CheckQueen(row, j)){
            QueensPos[row] = j;
            (row == N-1) ? PushAnswer() : NQueens(row+1);
        }         
    }
}

char *** solveNQueens(int n, int* returnSize, int** returnColumnSizes){
    
    N = n;
    
    *returnSize = ways[n];
    *returnColumnSizes = malloc(ways[n] * sizeof(int));
    for (int i = 0; i < ways[n]; i++)
        (*returnColumnSizes)[i] = n;
    
    
    QueensPos = malloc(n *sizeof(int));
    res = malloc( ways[n] * sizeof(char**) );
    
    for (int i = 0; i < ways[n]; ++i)
        res[i] = malloc(n * sizeof(char *));
    for (int i = 0; i < ways[n]; ++i)
        for (int j = 0; j < n; ++j) {
            res[i][j] = malloc((n + 1) * sizeof(char));
        }
    
    w = 0; // 不加這行 Submit 會 Runtime Error
    NQueens(0);
    
    return res;
}

觀察上圖的成立解：
- 每一列 ( 行 ) 必定要有一個 Q
- 放 Q 時 (i, j)要考慮
  - 左上方 ( i-k, j-k )
  - 正上方 ( i-k, j )
  - 右上方 ( i-k, j+k )
  - $k = 1$ ~
    $(i - 1)$
程式碼解析：

























char *** solveNQueens(int n, int* returnSize, int** returnColumnSizes){
    
    N = n;
    
    *returnSize = ways[n];
    *returnColumnSizes = malloc(ways[n] * sizeof(int));
    for (int i = 0; i < ways[n]; i++)
        (*returnColumnSizes)[i] = n;
    
    
    QueensPos = malloc(n *sizeof(int));
    res = malloc( ways[n] * sizeof(char**) );
    
    for (int i = 0; i < ways[n]; ++i)
        res[i] = malloc(n * sizeof(char *));
    for (int i = 0; i < ways[n]; ++i)
        for (int j = 0; j < n; ++j) {
            res[i][j] = malloc((n + 1) * sizeof(char));
        }
    
    w = 0; // 不加這行 Submit 會 Runtime Error
    NQueens(0);
    
    return res;
}

ways[] : 記錄 N-queens 的互不相同解個數
*returnSize : *res 的行數 ( i.e. 解的數量 ways[n] )
**returnColumnSizes : *res[w] 的 columns 數 ( i.e. n )
QueensPos : 各列 Q 所在的行數
- QueensPos[row] = column
res : a pointer to pointers to pointers to charater arrays

4-Queens 為例：













void NQueens(int row){
    
    if(w == ways[N]){
        return;
    }
    
    for (int j=0; j < N ; j++){
        if(CheckQueen(row, j)){
            QueensPos[row] = j;
            (row == N-1) ? PushAnswer() : NQueens(row+1);
        }         
    }
}

從 row = 0 開始進行遞迴放置 Queen
#39 ~ #42:
- 找出合法位置擺放 Queen
- 若 row = (N-1) ，代表成功擺到最後一列儲存該解 ( i.e. PushAnswer() )
  若否，進行下一列的遞迴 ( i.e. NQueens(row+1) )
#35 : 若 w = ways[N]，代表已紀錄完所有解，可停止遞迴







bool CheckQueen(int row,int col){
    for(int i=0; i < row; i++){
        if (QueensPos[i] == col || abs(QueensPos[i] - col) == abs(row - i))
            return false;
    }
    return true;
}

檢查想擺放的位置是否合法
QueensPos 紀錄各列 Q 所在的行數
- 若 QueensPos[i] = col，則 ( i, j ) 的上方有 Q
- 若 QueensPos[i] = j-k or j+k，則 ( i, j ) 的左上或右上有 Q
- k = abs( QueensPos[i] - j )
  
  k = i-(i-k)
  j-k = j-(i-(i-k)) = j - i + (i-k) = (col - row + i)
  j+k = j+(i-(i-k)) = j + i - (i-k) = (col + row - i)












void PushAnswer(){
    char* queen = malloc((N + 1) * sizeof(char));
    queen[N] = '\0';
    for (int i = 0; i< N; i++){
        for(int j = 0; j< N; j++){
            queen[j] = (QueensPos[i]==j) ? 'Q' : '.';
        }
        memcpy(res[w][i], queen, N + 1);        
    }
    free(queen);
    w++;
}

將找到的一組解 ( i.e. *QueensPos ) 紀錄到 res[w]

效能評估:

檢測內容

根據 guaneec 的筆記

2020q3 Homework4 (quiz4)

tags: RusselCK

Q1. LeetCode 461. Hamming Distance

使用 __builtin_popcount 實作

Q1. 進階題

不使用 gcc extension 實作

LeetCode 477. Total Hamming Distance

超時版

不超時版

Hamming Distance 和 Hamming Weight

錯誤更正碼( Error–Correcting Codes )

Hamming Distance & Hamming Weight

研讀 Reed–Solomon error correction

閱讀 Linux 核心原始程式碼的 lib/reed_solomon 目錄，抽離程式碼為單獨可執行的程式，作為 ECC 的示範

Q2. LeetCode 1483. Kth Ancestor of a Tree Node

Binary Lifting 的實作：

TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)

int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)

Q2. 進階題

指出可改進的部份

Q3. FizzBuzz

直覺的實作: (naive.c)

bitwise 觀察

bitwise 的實作: (bitwise.c)

Q4. 除數為 PAGE_QUEUES 的除法

原本的運算：

預先進行計算，避免整數除法指令的使用:

Q4. 進階題

LeetCode 51. N-Queens

Backtracking 法：

搭配 Bitewise mask ( 參考 RinHizakura 同學 )

Read more

VSCode 套件安裝

ARGB To BW

深入淺出物件導向分析與設計 筆記

TCL 讀書會(?