Try   HackMD

2022q1 Homework2 (quiz2)

contributed by < Chao-Shun-Cheng >

測驗 1

程式碼解釋






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

首先可以觀察 a >> 1 與 b >> 1 是直接先進行除以 2 的動作再相加，不過要去補償是不是第一個 bit 都是 1，如果是的話要補償回來。

Example

a = 0101, b = 0011, (a + b) / 2 = 0100
a >> 1 = 0010, b >> 1 = 0001, (a >> 1) + (b >> 1) = 0011
(a >> 1) + (b >> 1) + (a & b & 1) = 0100

所以 EXP1 是 a & b & 1。





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

可以觀察到兩數相加可以分為要進位的 bit 跟不須進位的 bit，假如是要進位的 bit 再除以 2 其實就是自己本身，而不需要進位的 bit 則需要另外再除以 2。因此可以知道 EXP2 是代表要進位的 bit，所以 EXP2 是 a & b；EXP3 則是代表不須進位的 bit，所以 EXP3 是 a ^ b。

測驗 2

程式碼解釋






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

假設 a > b 那就代表 a ^ ((EXP4) & -(EXP5)) == a，另外我們知道 a ^ 0 = a，所以代表當 a > b 時 (EXP4) & -(EXP5) == 0。再來 EXP5 是 logical operator，只會輸出 0 或 1 再加上負號，所以會只有 0 跟 -1 兩種可能性。因此我們可以推出 EXP5 就是 a < b。另外我們知道 a ^ a = 0，因此我們可以推出 EXP4 就是 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;
}

首先可以看到第六行的 for 迴圈，會利用 shift 把最大公因數裡有幾次 2 存起來。再來 do while 做的事情就跟 GDB 說明程式一樣，因此 COND 就是 v。當結束 while 迴圈，就代表 u 是最大公因數，但還要記得用 shift 補償回去，因此 RET 就是 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;
}

第八行開始的 while 迴圈就是直接利用 __builtin_ctzll 去找出有 1 的位置，再存進去 out 裡面，其中 t 用來存從低位元開始，第一個出現 1 的位置。

Example

a = 1010, -a = 0110
a & -a = 0010

因此 EXP6 就是 bitset & -bitset

測驗 5

程式碼解釋















































































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 個大小的 hash table 來去尋找是否有相同的餘數。首先看到第 7 與 12 行，先確定除數跟被除數都非 0 。35 行則是先將整數的部分存進 result 裡面，緊接著就是進入 for 迴圈處理餘數的部分。可以先看到 66 行會建立 node ，並把餘數當作是 key ，要存進去 hash table 裡面。第 70 行就是要將 node 存進對應的 bucket 裡面，因此 MMM 就是 list_add，而 EEE 就是 heads + (remainder % size)。第 72 行則是把看目前的數字存進 decimal 裡面。緊接著回頭看第 55 行，如果有找到對應的值，就代表發生循環小數，不過循環小數不一定是小數點第一位，因此要先將循環小數前面的數字存進 result 裡面，因此可以得知 PPP 就是 pos--。

測驗 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)

從題目可以知道會回傳 alignment 的大小，因此只要我們知道一個 member 所佔的大小即可知道答案。因此可以知道 M 就是 _h，而 X 就是 0

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

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

先從以下程式碼可以知道， length 會代表要 print 出來的長度，因此可以知道當整除三同時整除五時 length = 8，當只有整除五或只整除三時 length = 4。因此可以猜出 KK1 就是 div3，KK2 就是 div5。






char fmt[M9];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");

再來看 17 行的程式碼，會有以下幾種情況可以觀察

  • 只被三整除 : (9 >> div5) >> (KK3) = 0
    • 代表 9 >> KK3 = 0
  • 只被五整除 : (9 >> div5) >> (KK3) = 4
    • 9 >> 1 = 4 代表 KK3 = 0
  • 都不整除 : (9 >> div5) >> (KK3) = 9
    • 代表 KK3 = 0
  • 都能整除 : (9 >> div5) >> (KK3) = 0
    • 9 >> 1 = 4 代表 KK3 >= 3

因此可以推斷出 KK3 就是 div3 << 2

Last changed by 
 
Kenny Cheng
Linux Kernel Develop | Android Performance Tuning | BSP System Debugging | ARMv8 | RISC-V
0
182
Published on HackMD