2018q3 Homework3 (review)
=====
contribute by <`yichung279`>
###### tags: `sysprog2018`
## 作業要求
* 從 [第 1 週](https://hackmd.io/s/S1a9-YO_Q), [第 2 週](https://hackmd.io/s/BJA6LjbK7), [第 3 週](https://hackmd.io/s/BkyQskjK7) 選出你感興趣的 5 個題組進行作答，並且回答附帶的「延伸問題」
## 第一周測驗題 測驗 `1`
考慮以下程式碼:
```C
int my_xor(int x, int y) { return (x | y) OP1 (OP2 x OP3 OP4 y); }
int main() {
int x = 3, y = 5;
return my_xor(x, y);
}
```
`my_xor` 嘗試不用 XOR 運算子做出等效的 XOR 運算，其中 OP1, OP2, OP3, OP4 都是 operator，請補完實作。
**從真值表談起**
利用真值表與卡諾圖，配合一些邏輯運算技巧，可以更從容的面對邏輯運算。
* 真值表與卡諾圖
* 迪摩根定理、對合律、雙重否定
* xor 自反：不增加額外變數的交換
* nand：函數完備性
### 真值表與卡諾圖
XOR 的真值表:
|A|B|output|
|:-:|:-:|:-:|
|0|0|0|
|0|1|1|
|1|0|1|
|1|1|0|
將A真與假做為第一二 row，將B真與假做為第一二 col，完成卡諾圖。
卡諾圖:
|A\B|0|1|
|:-:|:-:|:-:|
|0|0|1|
|1|1|0|
若我們想表達XOR，我們可以取 1(true) 的部分的集合，或者使邏輯運算的分配律，或者取 0(false) 的部分的反集合。
$\begin{split}XOR &= (\overline A \land B)\lor(A\land \overline B)&= \overline A B+ A\overline B \\
&= ......&=\overline A A + \overline {AB} + BA +B\overline B \\\
&=(\overline A \land \overline B)\lor(A\land B)&=\overline {AB} + AB\end{split}$
事實上，題目到這裡就結束了，第二行的邏輯運算就是我們答案，但萬一今天需要進一步的轉換，我們就需要更強大的工具。
### 迪摩根定理、雙重否定
舉個很實際的例子，在 NP-Prloem 的推演中，從 SAT 推導到 3-CNF 時，變牽涉到 [CNF](https://zh.wikipedia.org/wiki/%E6%9E%90%E5%8F%96%E8%8C%83%E5%BC%8F) 跟 [DNF](https://zh.wikipedia.org/wiki/%E5%90%88%E5%8F%96%E8%8C%83%E5%BC%8F)的轉換，我們要將 $(A\lor B)\land (C\lor D)$ 轉為 $(A\land B)\lor (C\land D)$。
迪摩根定理:
$\neg(A\lor B) = \neg A\land \neg B$
$\neg(A\land B) = \neg A\lor \neg B$
雙重否定:
$\neg\neg A =A$
並用，$(A\lor B)\land (C\lor D) \\
= \neg(\neg((A\lor B)\land (C\lor D))) \\
= \neg(\neg(A\lor B)\lor \neg(C\lor D)) \\
=\neg ((\neg A\land \neg B)\lor (\neg C\land \neg D))$
### xor 自反：不增加額外變數的交換
自反:
$A \oplus 0 = A$
$A \oplus A = 0$
$B \oplus A \oplus A=B$
```clike
int swap(int x, int y){
x = x ^ y
y = x ^ y
x = x ^ y
}
```
以數學表示最後的 x,y
$y = x \oplus y \oplus y$
$x = x\oplus y\oplus x\oplus y\oplus y$
### nand 與函數完備性
提到 nand 是由於 nand 有兩大特色。
1.實作時，nand 所需的電晶體少於其他邏輯閘。
2.函數完備性，即 nand 可以變現出所有邏輯閘。
:::info
:question: 程式中，運用 nand 計算會因此比較快嗎?有的話，有快到值得去做對應的優化嗎?
:::
## 第二周測驗題 測驗 `2`
[指標篇](https://hackmd.io/s/HyBPr9WGl) 提到 signal 系統呼叫的原型宣告:
```C
void (*signal(int sig, void (*handler)(int))) (int);
```
該如何解析呢？
* `*a[]` : array of pointers
* `(*a)[]`: a pointer to an array
* `*f()` : function return a pointer
* `(*f)()`: a pointer to functon
handler: a pointer to a function, taking a int as parameter, returning void.
sig: int
signal:a fuinction return a pointer to a function which takes a int and retruns void.
提示: 參閱 manpage: [signal(2)](http://man7.org/linux/man-pages/man2/signal.2.html)
:::success
延伸問題: 解釋 signal(2) 的作用，並在 GitHub 找出應用案例
:::
## 第二周測驗題 測驗 `4`
考慮到以下程式碼:
```clike
int B = 2;
void func(int *p) { p = &B; }
int main() {
int A = 1, C = 3;
int *ptrA = &A;
func(ptrA);
printf("%d\n", *ptrA);
return 0;
}
```
該如何修改，才能讓 `func` 得以變更到 `main` 裡頭 `ptrA` 的內含值？
`func` 中，p 原本是個 pointer，隨後被 assign B 的 reference，一傳入 A 的 reference，便被改掉。
若要修改 prtA 的值，應傳入 pointer to ptrA，再以 `*` dereference，取出 value of pointer to ptrA，並 assign B的 reference 給 value of pointer to ptrA。
結論：
要更改 `main` 的物件時，都必須是透過`*`dereference 出原物件，而今天的物件是pointerpointer罷了。
加入一個 pointer to ptrA 便能解決這樣的問題。
```clike
int B = 2;
void func(int **p) { *p = &B; }
int main() {
int A = 1, C = 3;
int *ptrA = &A;
/**********************/
int **ptr2ptrA = &ptrA;
/*********************/
func(ptr2ptrA);
printf("%d\n", *ptrA);
return 0;
}
```
:::success
延伸問題: 在 GitHub 找出使用 the pointer to the pointer 的 C 語言程式碼，並加以討論
:::
## 第二周測驗題 測驗 `5`
以下程式是合法 C99 程式嗎？
```C
#include <stdio.h>
int main() { return (********puts)("Hello"); }
```
請搭配 C 語言規格書解釋
根據 6.3.2.1-4
>A function designator is an expression that has function type. Except when it is the
operand of the sizeof operator or the unary & operator, a function designator with
type ‘‘function returning type’’ is converted to an expression that has type ‘‘pointer to function returning type’’.
除了 `sizeof()` 以及 `&` 外的運算子運算， function designator 會被轉成 pointer to function。所以不論多少`*`， 最後 puts (function designator) 都會被轉成 pointer to function。
繼續思考以下是否合法:
```C
#include <stdio.h>
int main() { return (**&puts)("Hello"); }
```
繼續變形:
```C
#include <stdio.h>
int main() { return (&**&puts)("Hello"); }
```
也會合法嗎？為什麼？請翻閱 C 語言規格書解說。
以 `*&` 搜尋 [c99](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)，相關註解：
>Thus, &*E is equivalent to E (even if E is a null pointer), and &(E1[E2]) to ((E1)+(E2)). It is always true that if E is a function designator or an lvalue that is a valid operand of the unary & operator, *&E is a function designator or an lvalue equal to E.
所以 `*&put` 是 `puts`， `&*puts` 也是 `puts`，程式仍然可以合法運作。
而事實上，6.5.3.2-3
>The unary & operator yields the address of its operand. If the operand has type ‘‘type’’,the result has type ‘‘pointer to type’’.
function designator 使用 `&` 運算本來就會得到 pointer to function，跟 *function designator 的結果一樣。(Types 可分為 object type, function type, incomplete type。--根據 6.2.5-1 )
:::info
:question: 明明 `&` 也會得到 pointer to function returning type，為何 6.3.2.1-4 ，要那樣描述?
:::
## 第三周測驗題 測驗 `2`
考慮以下程式碼，在 little-endian 硬體上，會返回 `1`，反之，在 big-endian 硬體上會返回 `0`:
```C
int main() {
union { int a; char b;
} c = { .a = K1 };
return c.b == K2;
}
```
補完上述程式碼。
K1 = 1, K2 = 1
* little-endian: 最低位位元組，儲存在最低記憶體位址上。
big-endian: 最低位為元組，儲存在最高記憶體位址上。
* 由於 union 語法，整個 c，包含 c.a、c.b 共用同一個記憶體位址，存取時，不論little-endpian，或是 big-endian，都會從最低記憶體位址存取。
而我們知道 int 為 4 bytes，char 為 1 byte，1 的二補數為 `00000001`， 因此我們得知若在 little-endian硬體上，當我們以 int 寫入 1 時， 記憶體如下圖表示，而我們以 c.b 拿 char 大小的記憶體，只會拿到 a 裡的 `01`。
|記憶體位置|記憶體內容|
|:---:|:-:|
| a+3 | 00 |
| a+2 | 00 |
| a+1 | 00 |
| a | 01 |
:::success
延伸問題: 解釋運作原理，並找出類似的程式碼
:::
Sign in with Wallet
Connect another wallet