2022q1 第 2 週測驗題

contributed by < DokiDokiPB >

測驗 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) 會無條件捨去二進位中最低位元的位數，但若 a 與 b 在最低位加法時進位，則(a >> 1) + (b >> 1) 需再加上 1

以數位邏輯電路中， 取得進位數值的運算為(a & b) 表示當前下個

$carr{y}_{in}$的數值，即上圖中的

$carr{y}_{out}$

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

取 EXP2 為 a & b
取 EXP3 為 a ^ b

在你所不知道的 C 語言：數值系統篇 節錄

在數位邏輯中， a + b 可以用表示(a ^ b) + ((a & b) << 1)
(a + b) / 2 相當於 ((a ^ b) + ((a & b) << 1)) >> 1 = (a ^ b) >> 1 + (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 ^ ... 形式，可以推導

• a <= b，則回傳的形式應為：a ^ a ^ b = b
• a > b，則回傳的形式應為：a ^ 0 = a

若 a <= b 成立，表示 -(a <= b)的數值為-1，在二的補數系統中，表示0xFFFFFFFF。最終取得a ^ a ^ b = b
若 a <= b 不成立，表示 -(a <= b)的數值為0，在二的補數系統中，表示0x00000000。最終取得a ^ 0 = a

測驗 3

#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)
{
    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

直接運算一次：

• 例如
  $gcd(84,13)$
  
  $$\begin{gathered} 84=13\ast 6+6 \\ 13=6\ast 2+1 \\ 6=1\ast 6+0 \end{gathered}$$
• 例如
  $gcd(84,12)$
  
  $$84=12\ast 7+0$$

對應測驗題中原本

$gcd$ 的程式碼， while loop 的中止條件為： v = 0，推導出等價實作的 while loop 的中止條件也為v，因此取 COND 為 v

在題目敘述中

If x and y are both even, gcd(x, y)= 2 * gcd(x, y) because 2 is a common divisor. Multiplication with 2 can be done with bitwise shift operator.

因此 shift 的作用為預先將 2 公因數提出，最後再做 bitwise operation 回去。

在等價實作的程式碼中，都是對 2 預先做處理，其餘運算事實上與原本的

$gcd$ 實作相同。

延伸問題 2 (在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升)

延伸問題 3 (Linux 核心中也內建 GCD (而且還不只一種實作)，例如 lib/math/gcd.c，請解釋其實作手法和探討在核心內的應用場景)

節錄自 lib/math/gcd.c

unsigned long gcd(unsigned long a, unsigned long b)
{
	unsigned long r = a | b;

	if (!a || !b)
		return r;

	/* Isolate lsbit of r */
	r &= -r;

	while (!(b & r))
		b >>= 1;
	if (b == r)
		return r;

	for (;;) {
		while (!(a & r))
			a >>= 1;
		if (a == r)
			return r;
		if (a == b)
			return a;

		if (a < b)
			swap(a, b);
		a -= b;
		a >>= 1;
		if (a & r)
			a += b;
		a >>= 1;
	}
}

在程式碼第 3 ~ 5 行中，r 為 a 與 b 的 2 的冪共同因數，可得

$gcd(a,b)=r\ast ...$

在測驗 1 的延伸閱讀 Introduction to Low Level Bit Hacks #7. Isolate the rightmost 1-bit.，可以得知在二的補數下， r &= -r 取得最低位元的 1 的位置

在程式碼第 6 行中，已知 r 為 a 與 b 最大 2 的共同因數，將 b 多餘的 2 的冪移除。同理在 for loop 中，也將 a 的多餘的 2 的冪移除。

因此在接下來的程式碼中，假設a =

$mr$ 與 b =

$nr$，其中 m, n 為奇數， r 為 2 的冪

在程式碼第 26 ~ 27 行中， a -= b 必為 r 的倍數，且 (m - n)必為偶數，必定多出至少一個 2 的冪，可以 a >>= 1

在程式碼第 28 ~ 30 行中，可以簡單用例子說明：假設 a =

$3r$, b =

$3r$，若不執行if(a & r) a += b，會得到 a =

$1.5r$，這樣 a 不為 r 的整數倍數。 已知

$gcd(a+b,b)=gcd(a,b)$，透過加回一個 b 不影響結果。
並且因為 a += b 必定產生新的 2 的冪，透過 a >>= 1 移除。

事實上移除第 28 ~ 30 行並不影響結果，在下一個 for loop 中， a 多餘的 2 的冪會被移除。

測驗 4

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

以及改寫的程式碼

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

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

LeetCode 題目敘述為：

• 輸入兩個數字，numerator（分子）與denominator（分母），輸出它的小數。以這樣形式的輸入必為有理數，可能是循環小數或是有限小數。
• 題目保證輸出結果一定是
  ${10}^4$ 長度內

在此可能實作中，先做一次整數除法後，得到 division與remainder

• division便是小數點前的整數部位
• remainder便是小數點後的部位

每一次 for loop ，計算小數點後幾位的數字，並且計算remainder。而中止條件為：

• 當 remainder 為 0，表示此小數為有限小數
• 當 remainder 在 hash map 中有相同的數字，表示此小數為循環小數。依據題目要求，在開始循環的小數部位前加入(與)

以 337 / 333 為例：

337 / 333 = 1 餘   4, remainder = 4

40  / 333 = 0 餘   4, remainder = (4 * 10) % 333
400 / 333 = 1 餘  67, remainder = (40 * 10) % 333 = 67
670 / 333 = 2 餘   4, remainder = (67 * 10) % 333 = 4
在 hashmap 中發現相同的 remainder 數值 --> 利用 pos 尋找循環數的起點，插入 ( 與 )並輸出結果
輸出 1.(012)

因此可以取 PPP 為 pos--解答。

在可能實作的程式碼中，使用 hashmap 的方式儲存 remainder，共有 1333 個 index，並使用 Chaining 的方式解決 Collision。可以得出其 hash function 為

$k(mod1333)$
因此可以推導出 EEE 為 &(heads + (remainder % size ))

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

https://hackmd.io/@sysprog/c-pointer#Null-pointer

神奇的問題

My Linux System got broken when I test with the following code, using gcc main.c; ./a.out command.
It is kinda fun.

#include <stdio.h>
#include <stdalign.h>
int main(){
    size_t a = alignof(int);
    printf("%ld\n", a);

    struct foo{
        char c;
        int _h;
    };
    // char b = (char *)( &(((struct foo *)0)->c) - ((char *) ));
    char b = (char *) ( &(((struct foo *)0)->c) );
    printf("%d\n", b);
    return 0;
}

➜  ~ gcc --version      
gcc (Ubuntu 9.4.0-1ubuntu1~20.04) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

測驗 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);
        * 但是會令答案無解，但若是改成下列程式碼，則能正確輸出。
        */
        strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (KK3)], length);
        fmt[length] = '\0';

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

取 KK1 為 div3
取 KK2 為 div5
取 KK3 為 div3 << 2

列出其增值表

div3	div5	(2 << KK1) << KK2	KK1	KK2
0	0	2	0	0
0	1	4	0	1
1	0	4	1	0
1	1	8	1	1

因此取 KK1 為 div3， KK5 取 div5。兩者答案可以對調。

原題目
strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (KK3)], length);
會令輸出產生 u 而非 %u，因此改為
strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (KK3)], length);

考慮 strncpy 複製的範圍，列出其增值表

div3	div5	8 >> div5 >> (KK3)	預期的 KK3
0	0	8	0
0	1	4	0
1	0	0	4
1	1	0	4

可以發現 KK3 數值一直為 div3 的四倍，因此，取 div3 << 2