# 2018q3 Homework3 (review)
<contributed by < `siahuat0727` >
#### [第 2 週測驗 5](https://hackmd.io/UKpj7o20TLuLqm8t2Erv0g?view#%E6%B8%AC%E9%A9%97-5)
情境 1：
```C
#include <stdio.h>
int main() { return (********puts)("Hello"); }
```
合法。
`puts` 爲 function designator，遇到 `*` 時，因不是搭配 `sizeof` 和 `&` operator 使用，被轉化成 pointer to function（見 6.3.2.1-4），而 fucntion pointer 經過 unary `*` operator 的結果是 function designator（見 6.5.3.2-4），因此多加 `*` 不會影響結果。
>**C99 Standard (§ 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’’.
>**C99 Standard (§ 6.5.3.2-4)**
>The unary __*__ operator denotes indirection. If the operand points to a function, the result is a function designator.
情境 2：
```C
#include <stdio.h>
int main() { return (**&puts)("Hello"); }
```
合法。
`puts` 爲 function designator，經過 `&` operator 取得 pointer to function，之後與情境 1 相同。
情境 3：
```C
#include <stdio.h>
int main() { return (&**&puts)("Hello"); }
```
合法。
如以下 6.5.3.2-3 描述，`&*` 可視爲兩個 operator 都無作用，之後情況與情境 2 相同。
>**C99 Standard (§ 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.
留意到上述描述中，except that the **constraints on the operators still apply** and **the result is not an lvalue**，前者表示 `&*` 不能加在任意位置，後者表示並不是完全無作用，因爲會造成結果不是 lvalue。
舉個例子：
```C
#include <stdio.h>
int main() { return (& puts)("Hello"); }
```
合法。
```C
#include <stdio.h>
int main() { return (& &*puts)("Hello"); }
```
編譯失敗：
>error: lvalue required as unary ‘&’ operand
這裡特意用空格隔開 `&` 是爲了避免解讀爲 unary operator `&&`，詳見 [Labels as Values](https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html)
#### [第 1 週測驗 1](https://hackmd.io/s/S1a9-YO_Q#%E6%B8%AC%E9%A9%97-1)
Q：嘗試不用 XOR 運算子做出等效的 XOR 運算
A：
```c
int my_xor(int x, int y) {
return (x | y) & (~x | ~y);
}
```
這裡只是想分享用不同的角度看待這個操作
+ 若將 `|` 視爲聯集 (union, $\cup$)，則 `(x | y)` 可視爲**至少一者爲真即可**（`x`, `y` 其中一者爲真 或 二者皆爲真）
+ `(~x | ~y)` 中，兩者均取 `~`，表示真假互換，也就是**至少一者爲假即可**（`x`, `y` 其中一者爲假 或 二者皆爲假）
+ 將 `&` 視爲交集 (intersection, $\cap$)，整個表示爲
**至少一者爲真 $\cap$ 至少一者爲假**
= **剛好一真一假**
= **xor operator**
---
#### [第 1 週測驗 2](https://hackmd.io/s/S1a9-YO_Q#%E6%B8%AC%E9%A9%97-2)
Q：補完以下程式碼，達到判斷 parity bit 的功能
```clike
#include <stdio.h>
/* Generate look-up table while pre-processing */
#define P2(n) n, n ^ 1, n ^ 1, n
#define P4(n) P2(n), P2(n ^ 1), P2(n ^ 1), P2(n)
#define P6(n) P4(n), P4(n ^ 1), P4(n ^ 1), P4(n)
#define LOOK_UP P6(0), P6(1), P6(1), P6(0)
/* LOOK_UP is the macro expansion to generate table */
unsigned int table[256] = { LOOK_UP };
int parity(int num) {
/* Number is considered to be of 32 bits */
int max = 16;
// Dividing the number into 8-bit
// chunks while performing XOR
while (max >= 8) {
num = num ^ (num >> max);
max /= N;
}
// Masking the number with 0xff (11111111)
// to produce valid 8-bit result
return table[num & 0xff];
}
int main() {
unsigned int num = 1742346774;
/* Result is 1 for odd parity, 0 for even parity */
int result = parity(num);
printf("%s parity\n", parity(num) ? "odd" : "even");
return 0;
}
```
A： N = 2
從第 24 行 `return table[num & 0xff]`可得知 function 想從 `num` 的最後 8-bit 得知完整 `num` 的 parity，可推斷 function 嘗試將 32-bit 的資訊結合到最後 8-bit 中。
觀察 `num = num ^ (num >> 16)`，也就是將 `num[31:16]` 與 `num[15:0]` 做 xor，試想 16-bit 的結果中 `1` 的個數與操作前 `num[31:0]` 中 `1` 的個數有什麼關係？
只會減少 2*k 個 `1`，不會影響 parity 。(k $\in Z$)
因爲只有 `1 ^ 1 = 0` 會影響 `1` 的個數，每次減少兩個。
可得知再經過 `num = num ^ (num >> 8)` 即完成要求，因此 N = 2。
#### [第 3 週測驗 3](https://hackmd.io/s/BkyQskjK7#%E6%B8%AC%E9%A9%97-3)
以下程式碼計算 parity bit:
```C
#include <stdint.h>
int parity(uint32_t x)
x ^= x >> 1;
x ^= x >> 2;
x = (x & 0x11111111U) * 0x11111111U;
return (x >> P) & 1;
}
```
P = 28
與上一題相似，從 `x = (x & 0x11111111U) * 0x11111111U` 可推斷前面嘗試將 parity 資訊存在能被 4 整除的 bit 中。
`x ^= x >> 1` 可視爲奇數 bit 與 偶數 bit 做 xor 後將結果存在偶數 bit 中。（偶數 bit 的 parity 與 32-bit 的 parity 相同，原因見上一題）
同理，`x ^= x >> 2` 進一步將 parity 資訊存在能被 4 整除的 bit 中。
接下來是 `(x & 0x11111111U) * 0x11111111U`。
觀察 $2^{4n} * \sum_{i=0}^72^{4i}$, where $0 \leq n < 8， n \in Z$，
不管 $n$ 代入多少，相乘結果寫成如 $1*2^0 + 0*2^4 + 1*2^8 + ...$ 的表示式時（係數爲 0 至 $2^4-1$ 的整數，表示式唯一） $2^{28}$的係數都是1。
所以 `(x & 0x11111111U)` 的結果若有 n 個 bit `1`，相乘後 $2^{28}$ 的係數即爲 n，表示成 32-bit 二進制時可將 n 填入 bit[31:28]，第 28 bit 可反映 n 的奇偶，即 `uint32_t x` 的 parity。
Sign in with Wallet
Connect another wallet