---
tags: linux2022
---

# 2022q1 Homework2 (quiz2)
contributed by < [Duodenum](https://github.com/Duodenum87) >
> [作業要求](https://hackmd.io/@sysprog/BybKYf5xc)

## 2022q1 第 2 週測驗題

### 測驗 `1`
將前者程式碼改成後者

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

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

其中 `(a >> 1) + (b >> 1)` 相當直覺為兩者除以二後相加，但各自的最後一個 bit 將會流失，故 `EXP1` 即須將此資訊補回。
而只有當 a 即 b 的最後一個 bit 皆 set 時，相加才會需要進位。也就是說 `EXP1` == `(a & 1) & (b & 1)`。
繳出後才發現需要化到最簡，即 `EXP1` == `a & b & 1` 。

再次改寫成以下

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

看到題目第一直覺要填 `(a + b) >> 1` ，但與題目要求不符。直接餵狗 [average bitwise operation](https://stackoverflow.com/questions/1533131/what-useful-bitwise-operator-code-tricks-should-a-developer-know-about) 其中五樓回復到答案 `(a & b) + ((a ^ b) >> 1)`

static inline ulong average(ulong x, ulong y)
// Return floor( (x+y)/2 )
// Use: x+y == ((x&y)<<1) + (x^y)
// that is: sum == carries + sum_without_carries
{
    return (x & y) + ((x ^ y) >> 1);
}

其中 `x + y == ((x & y) << 1) + (x ^ y)` 即為加法器實作。

### 測驗 `2`
參考 [解讀計算機編碼](https://) 一文中的 branchless `min` 如下:

// find the smaller one of two integer
int32_t min(int32_t a, int32_t b) {
    int32_t diff = (a - b);
    return b + (diff & (diff >> 31));
}

即透過 `(a - b)` 為正或負來使得 `b + (a - b) = b` 或 `b + (-(a - b)) = a` 。

接著實作 branchless `max`:

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

推理過程如下
| step 1 | a > b | a < b |
| -------- | -------- | -------- |
| OUTPUT |a ^ () = a | a ^ () = b|
|() = | 0 | a ^ b|

為了使得 `((EXP4) & -(EXP5))` 達成 `0` 或 `a ^ b`
| step 2 | a > b | a < b|
| -------- | -------- | -------- |
| EXP4 | a ^ b | a ^ b |
| -(EXP5) | 0 | -1 |
| EXP5 | 0 | 1 |

即可得出 `EXP5` == `a < b`

### 測驗 `3`
考慮以下 64 位元 GCD (greatest common divisor, 最大公因數) 求值函式:

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    while (v) {                               
        uint64_t t = v;
        v = u % v;
        u = t;
    }
    return u;
}

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    // 1. and 2.
    if (!u || !v) return u | v;
    // 3.
    int shift;
    for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }
    // 4.
    while (!(u & 1))
        u /= 2;
    do {
        // 5.
        while (!(v & 1))
            v /= 2;
        // 6.
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (COND);
    return RET;
}

分別對應了以下 GCD 演算法
1. if both x, y are 0, $gcd(0,0) = 0$
2. $gcd(x,0)=x$ and $gcd(0,y)=y$
3. if x, y are both even, $gcd(x,y)=2*gcd(\frac{x}{2},\frac{y}{2})$
4. If x is even and y is odd, then $gcd(x,y)=gcd(\frac{x}{2},y)$
5. If x is odd and y is even, then $gcd(x,y)=gcd(x,\frac{y}{2})$
6. [輾轉相除法](https://en.wikipedia.org/wiki/Euclidean_algorithm) ，透過不斷相減求出相除會有的餘數結果。其中 while 迴圈的判斷條件，因為以 `v` 作為餘數， `COND` == `v`
7. `RET` 的值即為最大公因數，但因為先前的操作中已經先將所有 2 因數取出並存在 `shift` 中。需要重新乘回，也就是 `u * s ^ shift` = `u << shift`

### 測驗 `4`
在影像處理中，bit array (也稱 bitset) 廣泛使用，考慮以下程式碼:

#include <stddef.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
    size_t pos = 0;
    for (size_t k = 0; k < bitmapsize; ++k) {
        uint64_t bitset = bitmap[k];
        size_t p = k * 64;
        for (int i = 0; i < 64; i++) {
            if ((bitset >> i) & 0x1)
                out[pos++] = p + i;
        }
    }
    return pos;
}

以 `__builtin_ctzll` 改寫成以下

#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;
}

`TODO`

### 測驗 `5`
以下是 LeetCode [166. Fraction to Recurring Decimal](https://leetcode.com/problems/fraction-to-recurring-decimal/) 的可能實作:

#include <stdbool.h>                       
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
    
struct rem_node {
    int key;
    int index;
    struct list_head link;
};  
    
static int find(struct list_head *heads, int size, int key)
{
    struct rem_node *node;
    int hash = key % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (key == node->key)
            return node->index;
    }
    return -1;
}

char *fractionToDecimal(int numerator, int denominator)
{
    int size = 1024;
    char *result = malloc(size);
    char *p = result;

    if (denominator == 0) {
        result[0] = '\0';
        return result;
    }

    if (numerator == 0) {
        result[0] = '0';
        result[1] = '\0';
        return result;
    }

    /* using long long type make sure there has no integer overflow */
    long long n = numerator;
    long long d = denominator;

    /* deal with negtive cases */
    if (n < 0)
        n = -n;
    if (d < 0)
        d = -d;

    bool sign = (float) numerator / denominator >= 0;
    if (!sign)
        *p++ = '-';

    long long remainder = n % d;
    long long division = n / d;

    sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
    if (remainder == 0)
        return result;

    p = result + strlen(result);
    *p++ = '.';

    /* Using a map to record all of reminders and their position.
     * if the reminder appeared before, which means the repeated loop begin,
     */
    char *decimal = malloc(size);
    memset(decimal, 0, size);
    char *q = decimal;

    size = 1333;
    struct list_head *heads = malloc(size * sizeof(*heads));
    for (int i = 0; i < size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (int i = 0; remainder; i++) {
        int pos = find(heads, size, remainder);
        if (pos >= 0) {
            while (PPP > 0)
                *p++ = *decimal++;
            *p++ = '(';
            while (*decimal != '\0')
                *p++ = *decimal++;
            *p++ = ')';
            *p = '\0';
            return result;
        }
        struct rem_node *node = malloc(sizeof(*node));
        node->key = remainder;
        node->index = i;

        MMM(&node->link, EEE);

        *q++ = (remainder * 10) / d + '0';
        remainder = (remainder * 10) % d;
    }

    strcpy(p, decimal);
    return result;
}

`TODO`

### 測驗 `6`
`__alignof__`是 GNU extension，以下是其可能的實作方式:

/*
 * ALIGNOF - get the alignment of a type
 * @t: the type to test
 *
 * This returns a safe alignment for the given type.
 */
#define ALIGNOF(t) \
    ((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X)

令一個起始位址為 0 的 struct 指標，且其指向成員 M ，再求出其地址，最後減去 X
因為 struct 中只有一成員， `M` = `_h`
為求型態 t 的 alignment ， `X` = `0`

### 測驗 `7`
實做 FizzBuzz:

// naive
#include <stdio.h>
int main() {
    for (unsigned int i = 1; i < 100; i++) {
        if (i % 3 == 0) printf("Fizz");
        if (i % 5 == 0) printf("Buzz");
        if (i % 15 == 0) printf("FizzBuzz");
        if ((i % 3) && (i % 5)) printf("%u", i);
        printf("\n");
    }
    return 0;
}

// bitwise
static inline bool is_divisible(uint32_t n, uint64_t M)
{
    return n * M <= M - 1;
}

static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1;

int main(int argc, char **argv)
{
    for (size_t i = 1; i <= 100; i++) {
        uint8_t div3 = is_divisible(i, M3);
        uint8_t div5 = is_divisible(i, M5);
        unsigned int length = (2 << KK1) << KK2;

        char fmt[9];
        strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (KK3)], length);
        fmt[length] = '\0';

        printf(fmt, i);
        printf("\n");
    }
    return 0;
}