# 2022q1 Homework1 (quiz2)
contributed by < `a12345645` >

## 測驗 1

#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 的進位

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

#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

#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 就回傳行一方

if (!u || !v) return u | v;

2. 如果 u 與 v 都是偶數，並同時除以 2
因為 `gcd(x, y) = 2 ∗ gcd(x / 2 ,y / 2)` 而除以 2 是可以使用 shift 做到

int shift;
for (shift = 0; !((u | v) & 1); shift++) {
   u /= 2, v /= 2;
}

3. 而如果 y 為奇數，而 `gcd(x, y) = gcd(x / 2 ,y)`

while (!(u & 1))
    u /= 2;

4.
`COND` 為 `v > 0`
`RET` 為 `u << shift`
前面的 `while` 就是在執行步驟 3
而下面的 `if else` 就是原本的輾轉箱除法只是使用減法實現

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

#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