2022q1 Homework2 (quiz2)

contributed by < Duodenum >

作業要求

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 其中五樓回復到答案 (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`

參考解讀計算機編碼一文中的 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 演算法

if both x, y are 0,
$g c d (0, 0) = 0$
$g c d (x, 0) = x$ and
$g c d (0, y) = y$
if x, y are both even,
$g c d (x, y) = 2 * g c d (\frac{x}{2}, \frac{y}{2})$
If x is even and y is odd, then
$g c d (x, y) = g c d (\frac{x}{2}, y)$
If x is odd and y is even, then
$g c d (x, y) = g c d (x, \frac{y}{2})$
輾轉相除法，透過不斷相減求出相除會有的餘數結果。其中 while 迴圈的判斷條件，因為以 v 作為餘數， COND == v
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 的可能實作:

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

2022q1 Homework2 (quiz2)

2022q1 第 2 週測驗題

測驗 1

測驗 2

測驗 3

測驗 4

測驗 5

測驗 6

測驗 7