# 2022q1 Homework1 (quiz2)
contributed by < `a12345645` >
## 測驗 1
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
前面的 `(a >> 1) + (b >> 1)` 把 a 與 b 向右移動一個位元相加
可以視為 `floor(a / 2) + floor(b / 2)`
這樣與 `(a + b) / 2` 的差別會是最後一個位元的進位
因為最後一個位元被捨去了
所以 `EXP1` 為 `a & b & 1` 補回最又一個位元是否都為 1 的進位
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
這個是在模仿加法器
加法器的一個 bit 為
$$ S_{i} = (A_{i} or B_{i}) + (A_{i-1} and B_{i-1})$$
所以會是
`S = (A ^ B) + ((A & B) << 1)`
然後 S 除以 2
就變成
`((A ^ B) >> 1) + (A & B)`
`EXP2` = `a & b`
`EXP3` = `a ^ b`
## 測驗 2
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
在 xor 運算中 `a ^ 0 = a` 與 `a ^ a = 0`
所以如果 a 比較大的的話就會希望是 `a ^ 0 = a`
`((EXP4) & -(EXP5))` 等於 `0`
反之會希望為 `a ^ b`
所以 `(EXP4)` 為 `a ^ b`
而 `-(EXP5)` 為判斷 a, b 大小的遮罩
`EXP5` 是 `a < b`
當 a 小於 b 時，打開遮罩
大於的時候關起來
## 測驗 3
```c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
while (!(u & 1))
u /= 2;
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (COND);
return RET;
}
```
1. 判斷 u 與 v 一方為 0 就回傳行一方
```c
if (!u || !v) return u | v;
```
2. 如果 u 與 v 都是偶數，並同時除以 2
因為 `gcd(x, y) = 2 ∗ gcd(x / 2 ,y / 2)` 而除以 2 是可以使用 shift 做到
```c
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
3. 而如果 y 為奇數，而 `gcd(x, y) = gcd(x / 2 ,y)`
```c
while (!(u & 1))
u /= 2;
```
4.
`COND` 為 `v > 0`
`RET` 為 `u << shift`
前面的 `while` 就是在執行步驟 3
而下面的 `if else` 就是原本的輾轉箱除法只是使用減法實現
```c
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v > 0);
return u << shift;
```
## 測驗 4
```c
#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
uint64_t bitset;
for (size_t k = 0; k < bitmapsize; ++k) {
bitset = bitmap[k];
while (bitset != 0) {
uint64_t t = EXP6;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
`EXP6` 的目的是要取得 bitset 最小位元為 1 的遮罩
並把他與 bitset 做 xor 清除 1
負數為取 NOT 並加 1
11001000 -> 00110111 -> 00111000
這樣再與原本的數 and 就會得到所要的遮罩
10001000 and 00111000 = 00001000
## 測驗 5
Sign in with Wallet
Connect another wallet