2022q1 Homework2 (quiz2)

contributed by < AmyLin0210 >

2022q1 第 2 週測驗題

測驗 1

解釋程式碼運作原理

在以下的程式碼中，a >> 1 與 b >> 1 分別代表將 a 與 b 除二並無條件捨去到整數位，而後方的 EXP1 要處理的就是進位的問題。
在 a 與 b 皆為奇數時，會需要把前面相加的結果加一，因此 EXP 在這裡是 a & b & 0x1。若 a 與 b 都是奇數，那做完 and 之後最右邊的位元應該要是 1 ，後面再與 0x1 做 and，得到最右邊的位元。

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

觀察二進位加法，以下面的範例為例：

a = 0011
b = 0010
a + b = 0011 + 0010 = 0100 + 0001 = (a & b) << 1 + (a ^ b)

a & b 可以找到 a 與 b 在相同位置是否都是 1，如果是的話，表示在那個位置他們需要進位。
a ^ b 則是找到在哪邊 a 與 b 分別有值，代表的是相加後不需要進位的地方。

在取平均數時，需要把 a 與 b 相加除二，因此我們把上述的算式改進一下：

(a + b) / 2 = ((a & b) << 1 + (a * b)) / 2 = (a & b) + ((a ^ b) >> 1);

uint32_t average(uint32_t a, uint32_t b)
{
    return (a & b) + ((a ^ b) >> 1);
}

測驗 2

解釋程式碼運作原理

在 max 這個函式裡，要做的就是回傳比較大的那個值，因此先來思考，在已經給定

a ^ ((EXP4) & -(EXP5));

這樣的算式時，我要如何分別回傳出 a 與 b 。

看到 xor 的特性:

• 一個數與 0 這個數字做 xor ，那會得到的便是自己。
• 一個數與自己做 xor ，那會得到 0。

再來看看 and 的特性：

• 若一個數與 0 這個數字做 and ，那會得到 0 。
• 若一個數與二進制表示時全部都是 1 的數字做 and ，那會得到自己。

在二補數的系統中，-1 在使用二進制表示時，會全部都是 1 ，因此推論 EXP5 這個判斷式是回傳出 a 或者是 b 的關鍵。

先去考慮 a ^ (EXP) 會回傳出什麼東西

• 若 EXP 為 0 ，會回傳 a 。
• 若 EXP 為 a ^ b 由於 a ^ a 會變成 0 ，所以得到 0 ^ b 會是 b 。

推測 EXP4 為 a ^ b ，這樣才有機會去拿到一個完整的 b。

接下來看到 EXP5 ，目前我們知道目標是如果我想回傳 a ，那會變成 a ^ ((a ^ b) & 0)，如果我想回傳 b，那會變成 a ^ ((a ^ b) & -1) ，這樣 EXP5 的答案就很顯而易見，就是 a < b 。

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

測驗 3

解釋程式碼運作原理

GCD 的演算法特性

1. If both x and y are 0, gcd is zero \(gcd(0, 0) = 0\)
2. \(gcd(x, 0) = x\) and \(gcd(0, y) = y\) because vevrything divides 0.
3. If x and y are both even, \(gcd(x, y) = 2 * gcd(\frac{x}{2}, \frac{y}{2})\) because \(2\) is a common divisor. Multiplication with \(2\) can be done with bitwise shift operator.
4. If x is even and y is odd, \(gcd(x, y) = gcd(\frac{x}{2}, y)\).
5. On similar lines, if x is odd and y is even, then \(gcd(x, y) = gcd(x, \frac{y}{2})\). It is because 2 is not a common divisor.

以下的程式碼就是根據上述 GDB 演算法特性而改寫而來：

#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 (v);
    return RET;
}

在第 4 行可以對照到 GDB 演算法特性的第 1 點與第 2 點，若 u 與 v 其中一方或雙方是 0 時， u | v 的結果便是 0 (在 u 和 v 皆為 0 時) 或者是非 0 的那個數 (在 u 和 v 僅有其中一方為 0 時)。

在第 6 行到第 8 行，可以對照到 GDB 演算法特性的第 3 點，把 u 與 v 共同對 2 的因數給取出來。

在第 9 行到第 10 行與第 12 行到第 13 行，可以對照到 GDB 演算法特性的第 4 點與第 5 點，代表把 u 與 v 對 2 的倍數給拿出來。

在第 14 到 19 行，就是經典的 GDB 操作，大數減去小數後，將結果存在 v，因此第 21 行的 while 迴圈判斷條件為 v，當減完的結果還有值，就表示 GDB 還沒完全完成。

第 22 行，回去看到第 6 到第 8 行，可以發現有把 u 與 v 共同的二的因數個數礎存在 shift 中，因此最後需要回傳 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;
}

我們直接跳到程式碼的第 10 行，在這裡想要使用 GNU extenstion 的 __builtin_ctzll
在這裡的 r 是從低位元往高位元需要連續遇上多少個 0 才碰的到 1。

然後第 12 行想要做的事情就是把已經數到的位元清零，從這邊判斷，EXP6 這裡想要做的事情是找到最低位元的 1 在哪裡，並把他設為 1，其餘位元設為 0。

因此最開始我猜 EXP6 為 1 << __builtin_ctzll(bitset)，但顯然的不符合作答規範。

現在來思考在什麼狀況下可以拿到等同於 1 << __builtin_ctzll(bitset) 的數字。

由於想要把大部分的數字給清零，首先知道 a & ~a 會變成 0 ，但這還不是我們想要的，我們需要留下最低位元的 1 。

以下是範例：

bitmap      = 0b00001100
~bitmap     = 0b11110011
~bitmap + 1 = 0b11110100

bitmap & (~bitmap + 1) = 0b00000100

然後根據二補數的定義， ~bitmap + 1 會等同於 -bitmap，
所以可以得到 EXP6 = bitset & -bitset

測驗 5

這裡我們先來討論一般來說求循環小數會怎麼求。
在數學式部份，以 4 / 333 當作範例：

     0.0120...
    ----------
333) 4          --- 1       
     00
     ---------
     40         --- 2
     333
     ---------
      67        --- 3
      666
      --------
        4       --- 4
        00

可以從上圖很直覺地看到，當我們做到 (4) 時，由於已經與 (1) 重複了，所以就會判斷他是一個循環小數。

現在來對照下方的程式碼：

• 在第 77 行之前，做的事情為判斷正負、找到整數部份等等，第 77 行之後的 for loop 才正式開始找循環小數。
• 在第 78 行的地方，去找到是否數字已經被放在裡面了，在第 13 行的 find 函式就在做這件事情，而且使用 hash table 來加速。
• 如果有找到重複的數字，執行第 79 行到第 88 行的程式碼，如果沒有找到，則執行 89 到第 96 行的程式碼。
  • 我們先來看看沒有找到的情況，在第 90 到 93 行，目標就是把目前的 remainder 與位置存起來，接著做的事情就非常的接近直式除法的部份，將 remainder 乘以 10 之後除以 denominator。
  • 再來是看到有找到的情況，首先我們可以由 pos 得到從哪裡開始重複，當找到重複開始的位置之後，後面的就是循環小數。

#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 (pos-- > 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;

        list_add(&node->link, &heads[remainder%size]);

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

    strcpy(p, decimal);
    return result;
}

測驗 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)->_h) - (char *)0)

首先我們來拆解一下這份程式碼

• 看到 struct { char c; t _h; } *)0 ，表示有個 struct { char c; t _h; } 型態的指標指向了記憶體的位置 0
• (struct { char c; t _h; } *)0)->_h 那到當中的 _h 參數
• (&((struct { char c; t _h; } *)0)->_h) 找到 _h 參數的位置
• ((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0) 強至轉形成 char * 的型態，並找到與 (char *)0 的距離差

簡單作個小實驗，程式碼：

#include <stdio.h>

struct align_int {
    char c;
    int _h;
};

struct align_intp {
    char c;
    int *_h;
};

int main () {
    char *c = 0;
    struct align_int *a_int = 0;
    struct align_intp *a_intp = 0;
}

可以發現 int 的 align 為 4， int * 這個指標的 align 為 8。

(gdb) p c
$1 = 0x0
(gdb) p &(a_int->_h)
$2 = (int *) 0x4
(gdb) p &(a_intp->_h)
$3 = (int **) 0x8

再來看看下面的程式碼，在這邊我做的變化是，在 int 型態的變數前，多塞幾個 char 型態的變數，看看 int 型態變數的記憶體位置會不會有什麼變化。

#include <stdio.h>

struct align_int2 {
    char c[2];
    int _h;
};

struct align_int4 {
    char c[4];
    int _h;
};

struct align_int5 {
    char c[5];
    int _h;
};

int main () {
    char *c = 0;
    struct align_int2 *a_int2 = 0;
    struct align_int4 *a_int4 = 0;
    struct align_int5 *a_int5 = 0;
}

從結果可以看到，int 型態變數的記憶體位置的確會以 4 為倍數對齊。

(gdb) p c
$1 = 0x0
(gdb) p &(a_int2->_h)
$2 = (int *) 0x4
(gdb) p &(a_int4->_h)
$3 = (int *) 0x4
(gdb) p &(a_int5->_h)
$4 = (int *) 0x8

測驗 7

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdbool.h>

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 << div3) << div5;

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

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

is_divisible 可以參考 Faster remainders when the divisor is a constant: beating compilers and libdivide 這篇文章

下面控制 FizzBuzz 的部份，先來看到 length 這個變數，以下有 3 種可能:

• 不是 3 或 5 的倍數，length 為 2 ( %u )。
• 是 3 的倍數或是 5 的倍數，length 為 4 (Fizz 或 Buzz)。
• 是 3 及 5 的倍數，length 為 8 (FizzBuzz)。

看到程式碼的第 20 行，這裡會是 (2 << div3) << div5 的原因為，div3 與 div5 分別表示是不是被 3 或被 5 整除，所以只會是 1 或 0，2 << 0 << 0 、 2 << 1 與 2 << 1 << 1 的結果分別為 2, 4, 8 ，對應到 length 為 2, 4, 8 的情形。

再看到程式碼第 23 行的地方，這裡表示了要從哪裡開始讀 FizzBuzz%u 這個字串。
我們先看到 8 >> div5，這樣出來可能的結果為 8 或者是 4，換句話說就是，如果可以被五整除，那就是從 4 這個位置開始讀，如果不行，那就從 8 這個位置開始。
再來我們來看 div3，如果它是 3 的倍數，那我無論如何都是從 0 開始讀，如果不是，則要維持上面是否為 5 的倍數的結果。在 div3 << 2 這裡，可以發現如果 div3 為 1，出來的數值為 4，若 8 >> 4 會變成 0，反之若 div3 為 0，則不會動。