2019q1 第 1 週測驗題

目的: 檢驗學員對 bitwise operator 及遞迴程式設計的認知

---

測驗 1

西洋棋中的皇后可以直線前進，吃掉遇到的所有棋子，如果棋盤上有 8 個皇后，則這 8 個皇后如何相安無事地放置在棋盤上，1970 年與 1971 年， E.W.Dijkstra 與 N.Wirth 曾用這個問題來講解程式設計之技巧。

關於棋盤的問題，都可以用遞迴求解，然而如何減少遞迴的次數？在八個皇后的問題中，不必要所有的格子都檢查過，例如若某列檢查過，該該列的其它格子就 不用再檢查了，這個方法稱為分支修剪。

所以檢查時，先判斷是否在已放置皇后的可行進方向上，如果沒有再行放置下一個皇后，如此就可大大減少遞迴的次數，例如以下為修剪過後的遞迴檢 查行進路徑：

8 個皇后的話，會有 92 個解答，如果考慮棋盤的旋轉，則旋轉後扣去對稱的，會有 12 組基本解。 [ source ]

透過 bitwise 演算法 改寫為以下 C 程式:

#include <stdio.h>
#include <stdlib.h>

static int sol_count = 0;
void recursive_solver(int row, int maj_con, int min_con, int col_con, int n)
{
    int queen_position;
    int conflicts = min_con | maj_con | col_con;
    int i = 0;

    min_con &= 65535;
    while (i < n) {
        queen_position = 1 << (A1 - i);
        if (!(queen_position & conflicts)) {
            if (row == n - 1)
                sol_count++;
            else
                recursive_solver(row + A2, (maj_con | queen_position) >> A3,
                                 (min_con | queen_position) << A4,
                                 col_con | queen_position, n);
        }
        i++;
    }
}
void solve_queens(int n)
{
    int minor_dconflict = 0, major_dconflict = 0, column_conflict = 0;
    recursive_solver(0, column_conflict, major_dconflict, minor_dconflict, n);
    printf("solutions = %d\n", sol_count);
}

其中 solve_queens 的參數 n，數值介於 4 到 16。
請補完程式碼。

作答區

A1 = ?

• (a) 16
• (b) 15
• (c) 14
• (d) 13
• (e) 12
• (f) 11
• (g) 10
• (h) 9
• (i) 8

A2 = ?

• (a) 7
• (b) 6
• (c) 5
• (d) 4
• (e) 3
• (f) 2
• (g) 1
• (h) 0

A3 = ?

• (a) 7
• (b) 6
• (c) 5
• (d) 4
• (e) 3
• (f) 2
• (g) 1
• (h) 0

A4 = ?

• (a) 7
• (b) 6
• (c) 5
• (d) 4
• (e) 3
• (f) 2
• (g) 1
• (h) 0

延伸題目:

1. 讓參數 n 的有效範圍比 [4, 16] 更大，但仍透過 bitwise 操作，並改寫為 iteration 程式;
2. 考慮到 tail-call optimization (TCO)，改進上述遞迴程式碼並分析效能表現;
3. 考慮旋轉後扣去對稱的解法，求出基本解法的總量;

---

測驗 2

考慮到以下程式碼:

#include <stdint.h>
#define ALIGN_uint32(x, a) __ALIGN_MASK(x, ((uint32_t)(a)) - 1)
#define __ALIGN_MASK(x, mask) (((x) + (mask)) & ~(mask))

這是 data alignment 的巨集，data alignment 的意思是，data 的 address 扣除 base address 後 (也就是 offset) 可被 1, 2, 4, 8 等等這些數字整除，從這些數字可以發現他們都是 2^N (N 為從 0 開始的整數)。換句話說，這些 data object 可以用 1, 2, 4, 8 byte 去 alignment

• 電腦處理器如何抓取資料呢？CPU 不會一次只抓取 1 byte 的資料，因為這樣太慢了，如果有個資料型態是 int 的 資料，如果你只抓取 1 byte ,就必須要抓 4 次 (假設 int 資料寬度為 4 byte)，相當不理想。所以 CPU 傾向一次擷取 4 byte(實際看硬體規格而定，32 位元的 cpu 一次可以讀取 32 bit 的資料，64 位元一次可以讀取 64 bit)，並按照順序取的。舉例來說:
  • 第一次取: bit 0 ~ bit 3
  • 第二次取: bit 4 ~ bit 7
    

所以如果你的資料是分布在 bit 1 ~ bit 4 那還是會

• 第一次取 byte 0 ~ byte 3，再去除 byte 0 的資料，留下 byte 1 ~ byte 3
• 第二次取 byte 4 ~ byte 7，並去除 byte 5 ~ byte 7 的資料，留下 byte 4
• 再將 byte 1 ~ 3 和 byte 4 整合為 32-bit
  
  
  由於資料分布不在 4 的倍數，導致了存取速度降低，編譯器在分配記憶體時，就會按照宣告的型態去做 alignment ，例如 int 就是 4 byte alignment。

考慮 4-byte boundary，當 x 是 0x1006, a 是 4, 那麼 ALIGN(x, a) 會得到什麼數值？

作答區

X = ?

• (a) 0x1000
• (b) 0x1004
• (c) 0x1008
• (d) 0x100b
• (e) 0x1010