2022q1 Homework2 (quiz2)

contributed by < YiChainLin >

測驗題目

實驗的 gcc 編譯器版本

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

測驗1

兩數平均數，直觀的作法為直接對兩數相加並除以二
考慮相加的兩數在 32 位元無號整數，範圍: 0 ~ 4294967295 ，設定兩數分別為 3000000000

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

int main(){
    uint32_t a = 3000000000;
    uint32_t b = 3000000000;
    uint32_t sum = average(a, b);

    printf("%d\n", sum);
    return 0;
}

得出的結果為:

852516352

這是可預期的結果，在 a + b 的時候造成了 overflow 的結果，因此 a + b 的值為 6000000000 - 4294967295 = 1705032705 ，除二後得到 852516352 的結果
避免 overflow 的方式

若我們已知 a, b 數值的大小，可用下方程式避免 overflow :
透過較高的數值減去較低的數值可避免

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

透過 bitwise 方式避免 overflow 方式
參考你所不知道的 C 語言: bitwise 操作

將兩數個別透過位移運算子( Shift operator )，將二進制數值進行右移或左移

以 7₁₀ = 0111₂ 為例:
左移 : 0111₂ << 1 = 1110₂ = 14₁₀
將位元向左移，並在右邊補0，在10進制中等價為乘2

右移 : 0111₂ >> 1 = 0011₂ = 3₁₀
將位元向右移，並在左邊補0，在10進制中等價為除2

因此計算兩數平均為將個別數值進行右移，但是右移的過程會將最右一個位元忽略刪除，所以要先確認兩數在最後一個位元在相加時是否有進位的可能
檢查方式將兩數使用 & 運算子確認 a & b 是否進位，若有進位則為 1 若無則 0
最後在與 1 再進行 & 運算，若有進位表示在移位時，進位的值不可忽略，要補 1 回去

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

EXP1 = a & b & 1

以下使用 4 位元的數值進行平均數的舉例
a = 10₁₀ = 1010₂ ， b = 6₁₀ = 0110₂

a >> 1 = 0101
b >> 1 = 0011
(a >> 1) + (b >> 1) + (a & b & 1) = 1000 + 0000 = 1000
           二進位        二進位
            0101         1010
         +  0011         0110
        ........     &   0001
            1000     ........
                         0000

得到的結果為 1000₂ = 8₁₀

透過 bitwise 方式避免 overflow 另一種方式

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

EXP2 = a & b
EXP3 = a ^ b

使用 XOR 邏輯運算子可計算出兩數相加的結果，但不進位，所以進位的部分要透過 AND 運算子計算在配合右移，因此先思考兩數的相加為:

(a ^ b) /*相加但不進位*/
((a & b) << 1) /*計算進位*/
a + b = ((a & b) << 1) + (a ^ b)

因此兩數平均為:
(a + b) >> 1 = (((a & b) << 1) + (a ^ b)) >> 1  (分配律)
             = (a & b) + ((a ^ b) >> 1)

以下使用 4 位元的數值進行平均數的舉例
a = 10₁₀ = 1010₂ ， b = 6₁₀ = 0110₂

a & b = 0011
a ^ b = 1100
(a ^ b) >> 1 = 0110

(a & b) + ((a ^ b) >> 1) = 0010 + 0110 = 1000
           二進位        二進位
            1010         1010
         &  0110     ^   0110
        ........     ........
            0010         1100
                     >>1
                     ........  
                         0110

得到的結果也為 1000₂ = 8₁₀

測驗2

改寫〈解讀計算機編碼〉一文的「不需要分支的設計」一節提供的程式碼 min，我們得到以下實作 (max):
相關對於 XOR 運算子讀物: That XOR Trick

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

思考方式:
- 利用 XOR 運算子 Toggle (切換)特性
- 重複使用 XOR 會抵消，舉例來說， a ^ a ^ b (交換律)-> b ^ a ^ a 為 b 對 a 做了兩次的切換結果會得到 b 自己
- 觀察題目使用 a 做 XOR 運算得出 a 或 b
  - 要得出 a : a ^ 0 = a
  - 要得出 b : a ^ a ^ b = b
- 所以在 EXP4 中為 a ^ b
- EXP5 要能在 a ^ b 中得到 0 或 a ^ b 的結果
  - 利用 1 或 0 的遮罩方式選擇( 1 的遮罩為 1111…，在十進位數值為 -1 )
  - a ^ b & -1 = a ^ b
  - a ^ b & 0 = a ^ b
- 而 -1 或 0 可透過判別式取得 1 或 0 的結果，因此要加上 - 將 1 轉 -1

如何得到 111… 的二進制數值遮罩，在看到題目的引數值為 uint_32 也就是32 位元的無號整數，因此思考到關係運算子( relational-expression，>、<…) 出來的值為是否為有號或無號的整數

參考ISO/IEC 9899:1999 規格書的 6.5.8 中的第 6 點

Each of the operators < (less than), > (greater than), <= (less than or equal to), and >= (greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false.) The result has type int.

指出關係運算子得出來 1 或 0 型態為 int ，為有號的整數

所以在題目中的 a < b 判別式中得出的 1 或 0 為有號的整數，而在 -1 的二進位表示方式為 111111… 為 1 的遮罩方式

程式運作
以下使用 4 位元的數值進行平均數的舉例
a = 10₁₀ = 1010₂ ， b = 6₁₀ = 0110₂

a ^ b = 1010 ^ 0110 = 1100

若 a < b ( ~(a < b) = 1):      若 a > b( ~(a < b) = 0):
        二進位                            二進位
         1100                             1100
      &  1111                         &   0000
     ........                         ........
         1100                             0000
         
分別對 a 進行 XOR 運算:
        二進位                            二進位
         1010                             1010
      ^  1100                         ^   0000
     ........                         ........
         0110   <--得到 b                  1010  <--得到 a

EXP4 = a ^ b
EXP5 = a < b

反過來說，將也可以將題目改寫成使用 b 進行 XOR 運算得出較大的值

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

延伸問題:針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
不管是在無號數或是有號數，在 a > b 中的敘述中就能判斷出兩數的大小，所以在此函式即能判斷出兩數的最大值，因此修改引數的宣告

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

測驗3

考慮以下 64 位元 GCD (greatest common divisor, 最大公因數) 求值函式:

#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 演算法:

If both x and y are 0,
$g c d (0, 0) = 0$
$g c d (x, 0) = x$ and
$g c d (y, 0) = y$ because everything divides
$0$ .
以下程式碼針對上述兩個條件進行判別:
若其中數值為 0 的情況下，會透過 OR 運算子得到另一個非 0 數值
若兩數皆為 0 則也會返回 0 的數值

if (!u || !v) return u | v;

If x and y are both even,
$g c d (x, y) = 2 * g c d (\frac{x}{2}, \frac{y}{2})$ because
$2$ is a common divisor. Multiplication with
$2$ can be done with bitwise shift operator.
計算兩數擁有共同公因數 2 的數量，在最後輸出的時候，可以透過 shift 的方式簡化計算，直到兩數其中一數不為 2 的倍數(奇數)

for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
}

再來為非偶數的輾轉相除法( GCD )過程

首先先將兩數確保為奇數(因為已經判斷過2的倍數的數量了)，透過 while 迴圈消除

while (!(u & 1))
    u /= 2;
while (!(v & 1))
    v /= 2;

在傳統的輾轉中，透過兩數不斷的相減取餘數相減的方式，直到其中一邊為 0 ，則另一邊的餘數為最大公因數，以圖中的示例來說最大公因數為
$10 - 8 = 2$
程式的執行方式相似:

固定 u 數為較大值(被除數)，v 數為取餘數後的結果，若 v 數較大則進行調整，由 t 進算兩數取餘數的結果
$u$ mod
$v$ =
$t$ ，u 透過 v 回歸最大值，v 成為新的除數 t，直到餘數為 0 的時候，

因此當 v 為餘數 = 0的時候停止 while 迴圈，所以 COND = v

if (u < v) {
    v -= u;
} else {
    uint64_t t = u - v;
    u = v;
    v = t;
}

此時的 u (被除數) 即為最大公因數，但是不包含
$2$ 的倍數，因此返回值不為 u，應為 u * (因數 2 的數量)，而數量由 shift 變數紀錄

因此 RET = u << shift
延伸問題:在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升
可以得知 __builtin_ctz 函式用於找出最低位的 1 後面有多少 0 的個數

Built-in Function: int __builtin_ctz (unsigned int x)
Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined. gcc 文件說明

舉例說明:

int a = 8; /* 0100 */
__builtin_ctz(a) /* 2 ,最低位的 1 後面有兩個 0 */

運用函式可改寫在尋找 2 的因數
改善的部分在於:
- 不以 for 迴圈找尋兩數的 2 的因數的數量，改用 if-else 敘述找出
- 自訂兩變數在用於找出 u 、 v 兩變數 2 的因數數量，並 shift 該個數次數
- 在 do-while 迴圈中，每次皆會更新 v 可能在每一輪餘數中 2 倍數的可能性，將其維持在奇數
改寫為下列

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int u_ctz = __builtin_ctz(u);
    int v_ctz = __builtin_ctz(v);
    int shift = u_ctz < v_ctz ? u_ctz : v_ctz;

    u >>= u_ctz;
    v >>= v_ctz;
    
    do {
        v >>= __builtin_ctz(v);
        
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (v);
    return u << shift;
}

改寫後使用 perf 工具進行分析，分別執行 5 次
尚未改寫程式的運行表現

Performance counter stats for './quiz_w2_3.out' (5 runs):

             5,082      cache-misses              #   10.399 % of all cache refs      ( +- 63.07% )
            48,873      cache-references                                              ( +-  3.38% )
           819,973      instructions              #    0.93  insn per cycle           ( +-  0.77% )
           879,293      cycles                                                        ( +-  3.48% )

         0.0005822 +- 0.0000363 seconds time elapsed  ( +-  6.24% )

使用 __builtin_ctz 改寫後的程式運行表現

Performance counter stats for './quiz_w2_3_v2.out' (5 runs):

             4,217      cache-misses              #    8.505 % of all cache refs      ( +- 69.49% )
            49,581      cache-references                                              ( +-  1.48% )
           814,529      instructions              #    0.92  insn per cycle           ( +-  0.42% )
           885,792      cycles                                                        ( +-  3.32% )

         0.0004346 +- 0.0000208 seconds time elapsed  ( +-  4.78% )

測試的結果可以看到，在減少了 for 迴圈的使用下，運行的時間提升了約有 30% 的速度(可見 for 迴圈增加了不少運行時間)，並且也減少了在 cache-misses 的發生，整體而言使用 __builtin_ctz 改寫後程式的運行有較好的改善

測驗4

在影像處理中，bit array (也稱 bitset) 廣泛使用，考慮以下程式碼:

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

其中第 9 行的作用是找出目前最低位元的 1，並紀錄到 t 變數。舉例來說，若目前 bitset 為 000101b，那 t 就會變成 000001b，接著就可以透過 XOR 把該位的 1 清掉，其他保留 (此為 XOR 的特性)。

EXP6 = bitset & -bitset

參考這篇文章 : Find the lowest set bit

本題要找出數值 bitset 中的最低位元，可透過 2 補數( two's complement )的方式查找
以下以用 8 位元的數值做示例
bitset = 01011100₂

 bitset = 01011100
-bitset = 10100011 + 00000001  /* 2's complement */
        =10100100
        
        01011100  <-  bitset
     &  10100100  <- -bitset
     ...........
        00000100  <- 最低位元

透過二補數與原數做 AND 運算，找出最低位元的數值

測驗5

以下是 LeetCode 166. Fraction to Recurring Decimal 的可能實作:

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

題目主要功能為浮點數的運算方法，也考慮到無限循環小數的運算
透過指標、 hash table 、 linked list 的實作進行
使用 Leecode 中的例子進行 trace: (預期結果 "0.(012)")

int numerator = 4, int denominator = 333;

整數的運算，主要存取 n/d 所產生的整數值， 4 / 333 = 0 ，透過sprintf 函數寫入整數值在 p 中，最後透過移位加入 . 字元(小數點)

#include <stdio.h>
int sprintf(char * restrict s,const char * restrict format, …);
Description:
The sprintf function is equivalent to fprintf, except that the output is written into
an array (specified by the argument s) rather than to a stream.

char *p = result;
long long remainder = n % d;
long long division = n / d;

sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);

p = result + strlen(result);
*p++ = '.';

建立空的 hash table ，主要用於儲存計算的結果，與循環小數的查找

size = 1333;
struct list_head *heads = malloc(size * sizeof(*heads));
for (int i = 0; i < size; i++)
    INIT_LIST_HEAD(&heads[i]);

浮點數的運算，建立每一次小數運算值的資料 struct rem_node *node
- key 為每一輪小數除法的餘數值(模除)
- index 為紀錄整個 for 迴圈的輪次
- link 為 struct list_head 結構用於資料的指標連接

所以範例 4 / 333 中的第一位小數為 0 ， remainder 為 40 在 for 迴圈的 i = 0 的輪次，也就是 key = 40 index = 0 ，將結果加入到 hash table 中

MMM = list_add 為加入 hash table 的巨集
EEE = &head[remainder % size] 加入的位置在對應模除的位置
(EEE 參考 laneser(quiz2)同學的開發紀錄)

最後將該輪次的商數，也就是 (remainder * 10) / d 加入在 q 中，但是 q 的型態為 char * 需要將算出來的商數轉換成字元型態才能加入
注意到後面有 + '0' 的一個敘述，這是一個將整數轉字元的技巧，觀察其 ASCII 碼就會發現在 48~57 區間的顯示字元為 '0'~'9' ，而 '0' 所代表的值為 48
remainder = (remainder * 10) % d; 更新下一輪的餘數值進行運算，如果 = 0 則表示已除盡
q 每一輪會存取該輪的除法的商值，以 4 / 333 來說經過 3 輪存下了 0 、 1 、 2

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;

因此經過了 4 / 333 經過四輪後得到像這樣的 hash table :

由於此範例會有循環小數的產生，觀察 find 函數，利用 hash table 找尋是否會有餘數相同的情況，也就是在 hash table 在任意 head[i] 中找到有相同 key (相同餘數)
所以範例中在 head[4] 中透過 list_for_each_entry 走訪可以得到會有相同的 key 發生，因此返回當前的 index 值，"返回第一次 key 的 index 值"，範例中返回 index = 0
返回 index 值意義在於不重複的循環小數值的數量，例如:可能會有結果為 "0.23(45)" 其中 2 、 3 不為循環小數，此時在 find 的函數值會返回 2

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

list_for_each_entry 對一個 linked list 的中，對每一個成員的起始位址進行訪查，所以能得到結構內部的資料

#define list_for_each_entry(entry, head, member)                       \
    for (entry = list_entry((head)->next, __typeof__(*entry), member); \
         &entry->member != (head);                                     \
         entry = list_entry(entry->member.next, __typeof__(*entry), member))

解析循環小數的填入方式:
- 透過 find 函數找出不重複的循環小數值的數量，在 3~4 行中進入 while 迴圈要填入未循環的小數(商)值
- 加入 '(' 表示循環小數的開始
- 依序填入循環小數的值 (從 q = decimal )
- 加入 ')' 表示循環小數的結束
- 最後加入結尾符 '\0'
以 4 / 333 的範例中得出的結果為 "0.(012)"

PPP = pos– 為每一次填入未循環小數就會遞減已填入的數量











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

延伸問題:指出程式碼不足，並予以改進
改寫程式碼

bool sign = (float) numerator / denominator >= 0; /* origin */
bool sign = numerator < 0 ^ denominator < 0 /* improved */

看到程式碼中使用 malloc 配置記憶體，但是卻沒有釋放，因此需要釋放掉整個 hash table 所佔的記憶體空間(包含 head 與 node)
所以在計算 while 迴圈中的循環小數的 return 敘述前與程式最後的 return 前加入釋放記憶體的自定義函數
利用 list_for_each_safe 走訪每一個 heads 中所連結的 node 資料，並將其釋放
- 由於要進行記憶體釋放，所以透過 cur 可以記住走訪點的下一個位置，避免發生錯誤，在走訪的過程中較安全(也因此有 safe 敘述)

void free_ht(struct list_head *heads, int size)
{
    struct rem_node *node, *cur;
    list_for_each_safe (node, cur, heads) {
        free(node);
    }
    free(heads);
}

list_for_each_safe 函式，參考 list.h

#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; \
	     !list_is_head(pos, (head)); \
	     pos = n, n = pos->next)

在兩個 return result; 前加入釋放記憶體的函式

free_ht(heads, size);
return result;

測驗6

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

請補完上述程式碼，使得功能與 __alignof__ 等價。

程式的目的，傳回變數型態的佔用 byte 長度，透過記憶體對齊的方式
舉例:

printf("%ld", ALIGNOF(short)); /* 2 */
printf("%ld", ALIGNOF(int)); /* 4 */

查找的方式(以 int 示例):
- 為了記憶體對齊，所以 char 的宣告長度會與 int 一樣，如下圖
- 在 struct 定義中順序為先宣告 char 再宣告 int
- 由於 int 占了 4 bytes， char 占 1 byte，分配的方式如下圖
- &((struct { char c; t _h; } *)0)->M) 在這個敘述中目的要取得 t 的記憶體位置，因此 M 為 struct 結構中 t 型態的便數成員，所以 M = _h
- 得到了 int 的宣告的起始位置再扣掉 char 的起始位置，也就是單一變數型態的宣告長度，所以 X = 0 表示該結構的起始位置(也就是 char 的位置)，計算後就可以得到引數的占用記憶體長度

M = _h
X = 0

延伸問題:在 Linux 核心原始程式碼中找出 __alignof__ 的使用案例 2 則，並針對其場景進行解說
在 kernal.h 中找到兩個函式使用到 __alignof__
觀察兩個函式會發現主要兩個引數的型態，分別為 unsigned int 與 unsigned long ，第二個函式分別為 unsigned int 與 long 主要是將 unsigned int 轉換成 long 的型態變換
if-else 判斷系統的 long 與 long long 分配的記憶體長度，進而選擇要對哪一種的型態進行記憶體對齊
參考至Data Model，舉例來說如果在 LP64 model 下執行，因為 long 與 long long 都是 64-bits 所以會執行 if 的敘述使 32-bits 的 int 與 long long 轉換，並記憶體對齊
若是在 LLP64 model 則 long 與 long long 分別為 32-bits 與 64-bits ，此時會執行 else 敘述，使 32-bits 的 int 與 long 轉換，並記憶體對齊
- 引數中的 const char *s 用途與題目的 char c 一樣，編譯器會挑選占用較大的記憶體型態進行分配

static inline int __must_check kstrtoul(const char *s, unsigned int base, unsigned long *res)
{
     /*
      * We want to shortcut function call, but
      * __builtin_types_compatible_p(unsigned long, unsigned long long) = 0.
      */
     if (sizeof(unsigned long) == sizeof(unsigned long long) &&
         __alignof__(unsigned long) == __alignof__(unsigned long long))
         return kstrtoull(s, base, (unsigned long long *)res);
     else
         return _kstrtoul(s, base, res);
 }
 
 static inline int __must_check kstrtol(const char *s, unsigned int base, long *res)
 {
     /*
      * We want to shortcut function call, but
      * __builtin_types_compatible_p(long, long long) = 0.
      */
     if (sizeof(long) == sizeof(long long) &&
         __alignof__(long) == __alignof__(long long))
         return kstrtoll(s, base, (long long *)res);
    else
         return _kstrtol(s, base, res);
    }

測驗7

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

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

以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (bitwise.c):

首先先分析 is_divisible 函數，功能為判斷是否為被整數 n 整除
- 以本題的 M3 為例創造一個 64 位元的 111..11 遮罩
  示例一個整數 6 與 5 判斷，可發現值會有很大的差異

6:
    6 * ((0xFFFFFFFFFFFFFFFF) / 3 + 1) = 4
5:
    5 * ((0xFFFFFFFFFFFFFFFF) / 3 + 1) = -6148914691236517202

原因是如果是 3 的倍數的話乘回去，會剛好因為 overflow 的特性，所以 6 = 3 * 2 也就是整個補數系統會轉兩圈，所得出來的值為 6 - 2(補了2次的111..11遮罩到 0) = 4
因此可以判斷出數值使否能被該數的遮罩技巧整除，能剛好達到意外的效果檢測

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;

在 length 中要決定字串的長度，最多為 8 ，所以要讓 length 達到 8 的可能為 2 shift 2 次，也就是若 div3 與 div5 都返回 bool 的 1 就可以決定要顯示多少長度的字串，分別為 2 (印出數字本身) 、 4 (Fizz 或 buzz) 、 8 (Fizzbuzz)

兩者個結果可交換，不管是否為 3 或 5 的倍數，都透過 is_divisible 函式判斷是否要 shift
KK1 = div3
KK2 = div5

再來就是決定要印出的位置
- 可以看到 8 >> div5 若 div5 = 1 則會等於 4 會從 [4] 的位置開始印，若 div5 = 0 則會從 [8] 的位置開始印 "%u" 也就是原始數字
- 所以要從第 [0] 的位置開始印的話，必須把 8 透過 shift ，變成 0，所以 8 要至少要 shift 4 次，才能將 8 變成 0
- KK3 要能等於 4 由 div3 決定，也就是 div3 = 1 可透過左移 2 位得到 4

KK3 = div3 << 2
















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"[(8 >> div5) >> (KK3)], length);
        fmt[length] = '\0';

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

在下列程式碼中第 9 行考慮到字串的位置 F 的位置是 [0] 、B的位置是 [4]、%的位置是 [8]，要印出數字應該要是 "%u" 要從第 [8] 的位置印出
原程式碼為 9 會從 "u" 開始印，則會顯示不出原始數字

2022q1 Homework2 (quiz2)

測驗1

測驗2

測驗3

測驗4

測驗5

測驗6

測驗7

參考文獻

Read more

2022q1 Homework6 (ktcp)

2022q1 Homework 5 (quiz8)

2022q1 Homework3 (quiz3)

2022q1 Homework1 (lab0)