# 2019q1 第 1 週測驗題
:::info
目的: 檢驗學員對 [bitwise operator](https://hackmd.io/s/By0MltO_m) 及遞迴程式設計的認知
:::
---
### 測驗 `1`
西洋棋中的皇后可以直線前進，吃掉遇到的所有棋子，如果棋盤上有 8 個皇后，則這 8 個皇后如何相安無事地放置在棋盤上，1970 年與 1971 年， E.W.Dijkstra 與 N.Wirth 曾用這個問題來講解程式設計之技巧。
關於棋盤的問題，都可以用遞迴求解，然而如何減少遞迴的次數？在八個皇后的問題中，不必要所有的格子都檢查過，例如若某列檢查過，該該列的其它格子就 不用再檢查了，這個方法稱為分支修剪。
所以檢查時，先判斷是否在已放置皇后的可行進方向上，如果沒有再行放置下一個皇后，如此就可大大減少遞迴的次數，例如以下為修剪過後的遞迴檢 查行進路徑：
8 個皇后的話，會有 92 個解答，如果考慮棋盤的旋轉，則旋轉後扣去對稱的，會有 12 組基本解。 [ [source](https://openhome.cc/Gossip/AlgorithmGossip/EightQueen.htm) ]
透過 [bitwise 演算法](http://jgpettibone.github.io/bitwise-n-queens/) 改寫為以下 C 程式:
```cpp
#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
:::success
延伸題目:
1. 讓參數 `n` 的有效範圍比 `[4, 16]` 更大，但仍透過 bitwise 操作，並改寫為 iteration 程式;
2. 考慮到 tail-call optimization (TCO)，改進上述遞迴程式碼並分析效能表現;
3. 考慮旋轉後扣去對稱的解法，求出基本解法的總量;
:::
---
### 測驗 `2`
考慮到以下程式碼:
```clike
#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
Sign in with Wallet
Connect another wallet