2022q1 Homework2 (quiz2)

contributed by <arthurchang09>

測驗 1

考慮以下對二個無號整數取平均值的程式碼:

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

這個直覺的解法會有 overflow 的問題，若我們已知 a, b 數值的大小，可用下方程式避免 overflow:

#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
    return low + (high - low) / 2;
}

接著我們可改寫為以下等價的實作:

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

a>>1 和 b>>1 可視為 a/2 、 b/2 。然而，若 a 和 b 皆為奇數的話，顯然會和所要的結果差 1 。因此 EXP 需要確認 a 和 b 的最後的 bit 為 1 並加上，最直觀的方法為和 1 取 and ，若為偶數則會變成 0 ，奇數為 1。 EXP 為 a & b & 1 。

我們再次改寫為以下等價的實作:

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

這邊可以運用半加器的方式思考。半加器是由一個 AND 和 XOR 組成。其真值表如下：

A	B	A AND B	A XOR B
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

因此 A XOR B 是兩數相加此位數的值，而 A AND B 是進位。考慮所求為

\frac{A + B}{2}

， XOR 的部分需右移一位，即除以2方能表示此位數的狀況。進位的部分原本應左移一位加到下一位數，因為除以二而變成沒有左移。因此 EXP2 為 a & b 而 EXP3 為 a ^ b >> 1

測驗二

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

此題會運用 XOR 的幾個特性

a ^ 0 = a
a ^ (a ^ b) = b

因此，必須設法使 ((EXP4) & -(EXP5)) 中最後的值為 0 或 a ^ b 。若 a 大於 b 則為 0 ， a 小於 b 則為 a ^ b 。此時可以看到 & 在 EXP4 和 EXP5 之間且 EXP5 是帶有大於小於符號，可判斷 EXP4 為 a ^ b 而 EXP5 透過 & 使 ((EXP4) & -(EXP5)) 為 a ^ b 或 0 。

當 EXP5 為 0 ，-(EXP5) 為 0 ，經過 & 使 ((EXP4) & -(EXP5)) 為 0 ， a ^ 0 為 a 。

當 EXP5 為 1 ， -（EXP5） 為 0xffffffff ，經過 & 使 ((EXP4) & -(EXP5)) 為 EXP4 ，即 a ^ b 。

又此函式求兩數最大值，因此 EXP5 為 a < b 。

測驗三

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

上方程式碼為 Binary GCD algorithm，演算法如下

gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd(u, 0) = u.
gcd(2u, 2v) = 2·gcd(u, v)
gcd(2u, v) = gcd(u, v), if v is odd (2 is not a common divisor). Similarly, gcd(u, 2v) = gcd(u, v) if u is odd.
gcd(u, v) = gcd(|u − v|, min(u, v)), if u and v are both odd.

首先，若兩數有一者為 0 ，則回傳另一數。這邊的回傳使用 u | v ，當其中一者為 0 時， or 的結果為另一數，同上述第 1 點。

若兩數皆為偶數，即 LSB 為 0 ，即可先除以二，這裡使用 for 迴圈將兩數同時除以二，直到有一數為奇數，並用 shift 記下除了幾次。

由於 2 不再是公因數，使用第一個 while 將其中一數 u 的 2 全部除乾淨。

接著使用 do_while 迴圈尋找奇數之公因數。因為 v 可能為偶數，且目前 u 和 v 之公因數不會有 2 ，故先除掉，如同地 3 點。接著進行減法找公因數，若 v 較大則 v - u 為正，直接進行下一次迴圈，若 v 較小，則將兩者之差 assign 給 v ，將原本 v 之值給 u ，如同第四點所述。在此迴圈中主要被減的數為 v ，當 v = 0 時， u 之值為最大公因數中的奇數部分。接著，根據上述第 2 點要將兩數字被同除的 2 乘回。因此 COND 為 v ， RET 為 u<<shift 。

測驗四

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

其中第 9 行的作用是找出目前最低位元的 1，並紀錄到 t 變數。舉例來說，若目前 bitset 為

000101_{b}

，那 t 就會變成

000001_{b}

，接著就可以透過 XOR 把該位的 1 清掉，其他保留 (此為 XOR 的特性)。

考慮到二補數之特性，某數先經過 not ，即 1 變 0 或 0 變 1 ，接著 + 1 的話，若最低位元為 0 ，not 後為 1 ，相加進位為 0 ，直到某數某位元為 1 ， not 後為 0 ，相加結果為 1 ，進位即停止，某數最低位元的 1 的位置會變成 1 。此時較高位元和原數同樣位置呈 not 關係，較低位元皆為 0 。如 a = 10110 ， ~a = 01001 ， ~a + 1 = 01010 。接著將某數與其二補數做 & ，即完成所求。 a & -a = 10110 & 01010 = 00010 。

測驗五





































































































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

尚須修改

程式一開始為輸出的字串配置空間，大小為 1024 byte ，接著算商和餘數，並使用 sprintf 將商放入 result 字串。接著在商後放入小數點。由於題目需要找到循環小數，這裡採用 hash table 存放每一位小數點後的數字。因此第 72 行到第 75 行初始化 hash table。

第 77 行 for 迴圈是要尋找循環小數， i 表示目前處理到第幾位小數。一開始會先去 hash table 尋找數字是否有重複出現，若有的話，先將此位數之前的數字放入 result 中，在第 81 行， *p 是目前要放入值的位址，而 deciaml 則存著目前已處理的小數， pos 則是 hash table 中存放相同數值隻小數的位子，因此 PPP 應為 pos-- ，才能完成前述目的。

接著，放入 ( 再用 while 迴圈將重複數字後的位數一一放入 result 中，最後放入 ) 和 \0 表示循環小數結束及字串結束，並回傳 result 。

若第 78 行沒有找到位置，表示數字沒重複，要在 hash table 中加入新的節點，因此第 89 到第 93 行即是初始化節點並插入。 MMM 為 list_add 將節點插入對應之 linked list 開頭，而所插入的 linked list 需透過 hash 找到是在 heads 陣列中第幾個元素，因此 EEE 為 &heads[remainder % size] 。接著將目前處理的小數放入 decimal 中並更新 remainder 。

最後若沒有循環小數，則將 decimal 複製到 result 小數點後，並回傳結果。

測驗六

__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)

首先，注意到 (struct { char c; t _h; } *)0 ，這裡宣告一個 struct 並將 0 轉型為 struct * ，使此 struct 的位址起點在 0 。在 struct 中，每一個成員所占用的記憶體長度不同，電腦為了方便記憶體存取，會額外給空間使整著 struct 對齊。舉個例子如下：

struct example{
    char c; // 1 byte
    int i; // 4byte
};

為了對齊，實際上 c 後面會額外接上 3 byte ，使其長度和 i 一致。因此 c 的位址和 i 的位址之間是差 4 byte 而非 1 byte。

回到題目，由於以上的特性，想要求出 alignment ，必定要找到所傳入之 t 在這個 struct 的位址，因此 M 為 _h 。由於已將整個 struct 之位址定在 0 ，要求出 alignment 則不必再寫出這一長串 &((struct { char c; t _h; } *)0)->c ， (char *)0 ，即可。因此 X 為 0 。

測驗七

考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目:

從 1 數到 n，如果是 3的倍數，印出 “Fizz”
如果是 5 的倍數，印出 “Buzz”
如果是 15 的倍數，印出 “FizzBuzz”
如果都不是，就印出數字本身
























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

for 迴圈中， div3 和 div5 為某數能否被 3 或 5 整除，為真則為 1 ，反之為 0 。接著要透過控制 length 來決定輸出之方式，如題目所示：

string literal: "fizzbuzz%u"
        offset:  0   4   8

因此當某數為 3 倍數，需要印出 fizz ， offset = 4 = 2 << 1 ，因此 KK1 為 div3 ，若同時為 5 之倍數，要再印出 buzz ， offset = 8 = (2 << 1) << 1 ，因此 KK2 為 div5 。

接下來第 17 行便是決定要從 "fizzbuzz%u" 的哪個位置開始印出字串，若 div3 和 div5 皆為 0 ，則要從第 9 個字元，即數字部分開始印出。若只是為 3 倍數，要從最開頭開始印， 9 須被位移成 0 ， 9 >> 4 = 9 >> (1 << 2) ，因此 KK3 為 2 。若只是為 5 倍數，要從第 4 個元素開始印， 9 須被位移成 4 ， 9 >> 1 = 1001 >> 1 = 0100 = 4 。若為 15 及其倍數，則一樣須從開頭開始印， 9 被位移成 0 ， (9 >> 1) >> (1 << 2) = 4 >> 4 = 0 。最後再印出處理好的字串。

測試的時候發現 "fizzbuzz%u" 應該要改為 "fizzbuzz %u" ，否則不會印出數字而是 u 。

2022q1 Homework2 (quiz2)

測驗 1

測驗二

測驗三

測驗四

測驗五

測驗六

測驗七

Read more

2022q1 Homework5 (quiz8)

2022q1 Homework5 (quiz8) answer

2022q1 Homework3 (fibdrv)

2022q1 Homework1 (lab0)