# 2018q3 Homework3 (review)
contributed by <[`yungchuan`](https://github.com/yungchuan)>
## 第 1 週 - 測驗 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 是一個 bitwise operator ，所以即使使用別的方法實作，基本上還是要用 bitwise operator 來實現。而要使用 bitwise operator 的話，最直覺的工具就是真值表，如下所示：
| | | and | or | xor |
| - | - | --- | -- | --- |
| 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 |
### 解題
由真值表可以很輕鬆的看出來基本的 bitwise operator 的操作，接著重點就是要怎麼組合出 xor 了，首先最直覺的想法， xor 是將不同的值為 true 也就是 1 xor 0 = 1 ，而能辦到這件事的就是 or ，因為 1 or 0 = 1 ，但是不可能直接用 or 運算，必須把 1 xor 1 = 0 考慮進去。而這時就會想用 and 運算，因為 1 and 0 = 0 ，也就是說 or 出現的 1 可以用 and 的方式變成 0 ，達到 xor 的效果。所以會想到最後可能為：
| x | y | x and y |
| - | - | ------- |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| 1 | 1 | 1 |
| 0 | 1 | 0 |
x 為剛剛想到的用 or 的結果，若能給一個 y ，就能使用 and 來實作 xor 了，所以就有以下想法：
| p | q | p or q | ~p or ~q | (p or q) and (~p or ~q) |
| - | - | ------ | -------- | ----------------------- |
| 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 | 0 |
如此就能回答測驗的問題。
## 第 2 週 - 測驗 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` 的內含值？
### 想法
因為 C 語言的 function 是 call by value ，所以在 function 中對區域變數做的事情沒辦法對主程式造成影響。若想要用 function 改變主程式的變數值，則必須將欲改變的變數的位址傳入 function ，然後再使用 * (value of) 運算來改變該位址儲存的資料，達到改變主程式變數資料的效果。
### 解題
其實這題的重點只有：要改變的資料本身就是指標這件事。通常要改變資料的時候都會傳資料的位址到該型態的指標變數中，所以這次也是一樣，既然要改變的資料是指標變數，當然要傳遞的就是指標變數的位址，所以參數宣告應該要是==指標的指標==才行，所以把握這個改念將題目程式碼改成以下：
```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;
}
```
如此就能改變 ptrA 的內容了。
## 第 2 週 - 測驗 5
### 題目
以下程式是合法 C99 程式嗎？
```C
#include <stdio.h>
int main() { return (********puts)("Hello"); }
```
請搭配 C 語言規格書解釋
繼續思考以下是否合法:
```C
#include <stdio.h>
int main() { return (**&puts)("Hello"); }
```
繼續變形:
```C
#include <stdio.h>
int main() { return (&**&puts)("Hello"); }
```
也會合法嗎？為什麼？請翻閱 C 語言規格書解說。
### 想法
這題感覺單純為對於 function pointer 以及 function designator 的應用問題，所以將查詢 C 語言規格書來解題。以下擷取自 C 語言規格書：
1. C99 [6.3.2.1]: 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*’’.==
1. C99 [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*’’. ==If the operand is the result of a unary __*__ operator, neither that operator nor the **&** operator is evaluated and the result is as if both were omitted,== except that the constraints on the operators still apply and the result is not an lvalue.
1. C99 [6.5.3.2-4]: The unary __*__ operator denotes indirection. If the operand points to a function, the result is a function designator.
### 解題
先看到第 1 小題， `(********puts)("Hello");` 我們可由第 3 點知道，用 * 作用在 function 上，會使得結果為 function designator ，而接著因為接下來的 operator 不是 **sizeof** 或 **&** ，所以由第 1 點可知 function designator 會轉成 pointer to function returning type ，如此又會因為緊接著的 __*__ 運算變成 function designator ，因此可以說不管在 function 前放多少 __*__ operator 最後的結果就跟放一個 __*__ 一樣。所以最後就變成執行一次 `puts("Hello");` 。
接著看第 2 小題， `return (**&puts)("Hello");` 首先由第 2 點知道 *&* 會使得 `puts` 原本的 function returning type 變成 pointer to function returning type ，接著 * 會將 pointer to function returning type 變回 function returning type ，也就是 *& 效果上互相抵銷，接著跟第 1 題一樣，非 sizeof 或 & 運算使得 puts 的型態變成 pointer to function returning type ，接著再進行 * 運算，結果變回 function designator。所以依舊是執行 `puts("Hello");` 。
最後第 3 小題， `return (&**&puts)("Hello");` 可由第 2 點中提到的 `If the operand is the result of a unary * operator, neither that operator nor the & operator is evaluated and the result is as if both were omitted.` 知道， &* 運算是不會有效果，也就是會被抵銷的。所以題目就化簡為 `return (*&)("Hello");` 而這部份就跟第 2 題前半一樣，可以知道最後的結果還是一個 function designator 。一樣執行 `puts("Hello");` 。
## 第 3 週 - 測驗 1
### 題目
考慮以下程式碼:
```C=
#include <stdio.h>
#include <stdint.h>
struct test {
unsigned int x : 5;
unsigned int y : 5;
unsigned int z;
};
int main() {
struct test t;
printf("Offset of z in struct test is %ld\n",
(uintptr_t) &t.z - (uintptr_t) &t);
return 0;
}
```
在 GNU/Linux x86_64 環境中執行，得到以下輸出:
```
Offset of z in struct test is 4
```
倘若將第 10 和第 11 換為以下:
```C=10
printf("Address of t.x is %p", &t.x);
```
會發生什麼事？
### 想法
這題比較特別的地方是 bit fields 的宣告，由於這是第一次接觸的東西所以去查了一些資料。這種宣告方式會使得此 struct 中的成員只分到必要的 bit 數，而不向其他型態有固定的 byte。拿題目的例子來說，這個 struct test 中的成員 x 以及 y 都只有分到 5 個 bit ，資料將會當無號整數來儲存，而 z 就單純為無號整數。
這是個方便且可以節省空間的宣告方式，但也有些限制，在規格書中
* C99 [ 106) ]: The unary **&** (address-of) operator cannot be applied to a bit-field object; thus, there are no pointers to or arrays of bit-field objects.
也就是說 bit fields 宣告的成員是沒辦法使用 address-of 運算的。
### 解題
題目要求將原本的 10, 11 行改變成 `printf("Address of t.x is %p", &t.x);` 而上面有提到，規格書有明確的指出， bit fields 的型態是不能使用 address-of 的運算，所以更換成這個敘述後程式將無法編譯成功。
## 第 3 週 - 測驗 4
### 題目
考慮以下程式碼:
```C
#include <stdlib.h>
#include <string.h>
typedef struct rec {
char *value;
struct rec *next;
} record;
void insert_sorted(record **r, const char *value)
{
record *newrec = NULL;
while (*r && strcmp(value, (*r)->value) > 0)
r = &((F1)->next);
newrec = malloc(sizeof(record));
newrec->value = F2(value);
newrec->next = F3;
F4 = newrec;
}
```
函式 `insert_sorted` 的作用是在 r 所指向已依據數值排序的 linked list 中，安插給定的字串，考慮到 string literal 的生命週期，應該在新建立的節點中，複製給定的字串。
請補完上述程式碼。
### 想法
* 這個 linked list 的插入函式有一個特別之處，就是要依據數值排序，所以首先要根據給予要插入的字串以及已經存在的 list 來判斷要插入的位置，所以一開始的 while 迴圈就是要達到這個目的。
* 因為有可能會把新的資料插在開頭的地方，為了要能改變外部儲存這個 linked list 開頭的指標，所以要把"指向 linked list 開頭的指標" 的位址傳進來，所以使用指標的指標 (**r) 來當參數。
* 接著再用 malloc 造一個 linked list 的 node ，來存放資料，考慮到副程式區域變數的生命週期，所以資料(字串)必須要有新的記憶體空間，所以這裡比起 strcpy ，更適用 strdup 。
* 最後，建立新 node 之後必須要將指標調整好，讓他插入一開始找到的 linked list 中的位置。
### 解題
* F1:
* 首先是用 while 迴圈找到要插入的位置，既然要按照順序，那就像題目一樣用 strcmp 的回傳值來找，若回傳值大於 0 ，就繼續去找，找到下一個 node 的資料比要插入的資料大，或是 尾端 (NULL) 的地方。
* 而 r 這個變數一開始是從外部傳入的這個 linked list 的開頭，也就是說從開頭開始比較，不是的話就換下一個，所以 F1 應該要填入的是 *r ，因為 r 是指標的指標，儲存的是前一個比較的 node 成員中 next 的位址，所以用 * 運算可以得到 next 的資料，也就是當前比較的 node 的位址。
* 接著只要用 r 記錄當前比較的 node 成員 next 的位址，就可以經由 while 迴圈重複上述動作。
* F2:
接著創一個新的 node 後，要把資料存入新的 node ，如同上述，為了要能讓資料不隨著函式的結束而消失，這邊使用 strdup 這個語法，他會另外找一塊記憶體，然後把原本記憶體當中的字串複製到新的記憶體中，不會隨著函式結束而消失。
* F3:
再來要把 linked list 的指標調整好插入新 node ，因為一開始的 while 迴圈，現在的 r 儲存的是一個 node 中的 next 的位址，而這個 node 就是新 node 的前一個， next 就是新 node 的下一個 node ，所以先將新 node 的 next 指向下一個 node ，也就是把 *r 的資料存到新 node 的 next 中。所以 F3 要填入 *r 。
* F4:
最後要把前一個 node 的 next 改成新 node 的位址，剛好 r 儲存的就是前一個 node 的 next 的位址，所以只要將 *r 改成新 node 的位址就好。也就是說 F4 要填入 *r 。
Sign in with Wallet
Connect another wallet