2022q1 Homework2 (quiz2)

contributed by < PinLin >

測驗 `1`

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

// EXP1 = a & b & 1

(a >> 1) + (b >> 1) + (EXP1) 即是對兩個無號整數取平均值的結果，前面的 a >> 1 和 b >> 1 可以被理解為「除以二後無條件捨去至整數位」，後面的 EXP1 則是我們目前缺少的部分。

將 a 和 b 分別帶入數字，得到了下表：

`a`	`b`	`(a >> 1) + (b >> 1)`	expected
2	2	2	2
2	3	2	2
3	2	2	2
3	3	2	3

我們發現當兩者都是帶入奇數時，a >> 1 和 b >> 1 將各自捨去 0.5，相加後便比我們期望得到的答案還少 1。

因此在這裏 EXP1 應作為一個補償：在 a 與 b 皆為奇數時為 1，否則為 0，以 (a & 1) & (b & 1) 表示，最後簡化為 a & b & 1。

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

// EXP2 = a & b
// EXP3 = a ^ b

這樣的形式讓我想到了加法器的操作，只是要求平均需要多一個除以二的操作，嘗試推導了一下：

a + b = (a ^ b) + ((a & b) << 1)
(a + b) / 2 = ((a ^ b) + ((a & b) << 1)) >> 1
(a + b) / 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));
}

// EXP4 = a ^ b
// EXP5 = a < b

首先我們知道這個函式的輸出只有可能是 a 或是 b，假設 a ^ ((EXP4) & -(EXP5)) 的結果是 a，那麼 (EXP4) & -(EXP5) 就必須是 0；反之，若結果是 b 則將運用到 XOR 的特性，(EXP4) & -(EXP5) 的結果必須是 a ^ b。

根據題目的限制，推斷 EXP4 為 a ^ b，而當 b > a 時 -(EXP5) 應為 -1，否則應為 0，推得 EXP5 即為 a < b。

針對 32 位元有號整數撰寫同樣 branchless 的實作

只需將參數 a、b 和回傳值型別改為 int32_t 即可，因為 a 和 b 皆為有號數，進行的便是有號數的比較。

#include <stdint.h>
int32_t max(int32_t a, int32_t b)
{
    return a ^ ((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;
}

// COND = v
// RET = u << shift

這個函式首先在第 5~8 行中透過檢查 LSB 的方式判斷 u 跟 v 是否是 2 的倍數，是則將兩者各除以二，並將除以二的次數記錄在 shift 中。

接著在第 11~21 行中執行類似輾轉相除法的流程來嘗試找出兩者的最大公因數，由於 u 會等於操作前的 v，v 會等於操作前的 u - v，所以 COND 在此應該判斷 v 是否為 0。

最後離開迴圈之後需再將 u 的值左移 shift 次，便是 u 跟 v 真正的最大公因數。

測驗 `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 & -bitset

這段程式首先將 bitmap 一塊一塊取出作為 bitset，接著透過 EXP6 表示式找出 bitset 目前最低位元的 1 並紀錄到 t。

研究了一下題目提到的 -bitwise 特性，嘗試列出幾個數字和它二的補數：

104 = (01101000)_{b} - 104 = (10011000)_{b}

發現將一個數字和其二的補數做 AND 運算，便可找出該數字最低位元的 1，因此 EXP6 應為 bitset & -bitset。

測驗 `5`









































































































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

// PPP = pos--
// MMM = list_add
// EEE = &heads[remainder % size]

這段程式嘗試求出給定分數的比值，主要分成求出整數和小數的部分。
整數部分直接使用整除除法求得 division 和 remainder，接著小數的部分：

第 72~75 行，因為考慮到有循環小數，需要記錄曾經出現過的 remainder，於是先配置了一段大小為 size * sizeof(struct list_head) 的空間並初始化，作為 hash table 的 buckets。
第 77~97 行，若是 remainder 不為 0 則進入迴圈，首先檢查 hash table 是否存在目前的 remainder。
- 第 79~88 行，若存在即代表結果為「循環小數」，首先整併不循環的小數部分，再整併加上括弧後循環的小數部分，因為 remainder 不可能等於 0，所以至此直接回傳結果。
- 第 89~96 行，若不存在則將其記錄到 hash table 中，接著做下一輪的除法並記錄結果。
第 99~100 行，最後當 remainder 等於 0，便將小數的部分整併至整數的部分並回傳結果。

測驗 `6`

/*
 * 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)

// M = _h
// X = 0

這段程式利用到 struct 會以成員中最大的對齊長度來對齊所有成員的特性，因為成員 char c 對齊長度只有 1，所以只要將目標型別帶入 t 後計算 struct 開頭到成員 t _h 的長度，就可以知道型別 t 所需的對齊長度。

測驗 `7`




























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

// KK1 = div3
// KK2 = div5
// KK3 = div3 << 2

這段程式藉由修改 fmt 的內容去控制輸出，而 fmt 的內容又是在第 17 行中透過 "FizzBuzz%u" 根據不同條件使用不同的起始位置和長度複製過去的。

根據 div3 和 div5 值的不同，列出了下表顯示我們期望的 fmt，以及其所需的 length 和起始位置：

`div3`	`div5`	起始位置	`length`	`fmt`
0	0	8	2	`%u`
0	1	4	4	`Buzz`
1	0	0	4	`Fizz`
1	1	0	8	`FizzBuzz`

但是我發現在第 17 行中間的 &"FizzBuzz%u"[(9 >> div5) >> (KK3)] 在 div3 和 div5 皆為 0 時會將字串起始位置訂在 9，這樣便無解了。所以我認為應該把此處的 9 改為 8 才對。

為了控制 length，KK1 和 KK2 應為 div3 和 div5。而為了控制起始位置，KK3 應該為 div3 << 2。

2022q1 Homework2 (quiz2)

測驗 1

測驗 2

針對 32 位元有號整數撰寫同樣 branchless 的實作

測驗 3

測驗 4

測驗 5

測驗 6

測驗 7