# 2022q1 Homework2 (quiz 2)
contributed by < `void110916` >

## [測驗 `1`](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-1)
### EXP1

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (EXP1);
}

`(a >> 1) + (b >> 1)` 在 a, b 均為偶數時滿足平均的結果，因此須考慮的 `EXP1` 為在 a, b 在均為奇數時的進位情況，因此 `EXP1` 為：

a & b & 1

### EXP2, EXP3

uint32_t average(uint32_t a, uint32_t b)
{
    return (EXP2) + ((EXP3) >> 1);
}

當 a, b 在 $n^{th}$ bit 同時為 1 時，會先經過進位( << 1)，再除以2( >> 1)，因此該動作會互相抵銷，則 `EXP2` 為:

a & b

而在其他情況時，因為不會進位，只會有除以2( >> 1)的動作，因此 `EXP3` 為:

a ^ b

以 [Intel® 64 and IA-32 Architectures Optimization Reference Manual](https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html) Table D-17. General Purpose Instructions 為例，`MOV` `ADD` 所需 Latency & Throughput 在同架構下均一樣，而 `SHR` Throughput 略多 0.5 至 1 倍，
## [測驗 `2`](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-2)

#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((EXP4) & -(EXP5));
}

XOR 真值表：
X\\Y|1|0
:--:|:--:|:--:
1|0|1
0|1|0

可以視為 XOR 表示**該位元是否一樣**，因此以下為 XOR 的特性：
* `a^a=0`：所有位元都一樣，所以均為0
* `a^b=b^a`：對調不影響不一樣的位元位置
* `a^b^a=a^a^b=b`

-1 以二進制表示為 `0xffff_ffff` ，為全開遮罩；0 以二進制表示為 `0x0000_0000` ，為全關遮罩，因此 `EXP4` 為:

a ^ b

`EXP5` 為:

a < b

當 $a < b$ 時， `a ^ b` 通過遮罩後的結果為 `a ^ b` ，因此回傳結果為 `a ^ b ^ a = b`
當 $a \geq b$ 時， `a ^ b` 通過遮罩後的結果為 `0` ，因此回傳結果為 `a ^ 0 = a`

## [測驗 `3`](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-3)
`COND`:

v

`RET`:

u << shift

## [測驗 `4`](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-4)

`EXP6`:
## [測驗 `5`](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-5)

`M`:

_h

`X`:

0