2020q3 Homework4 (quiz4)

contributed by < grb72t3yde >

tags: sysprog2020

---

Links

• 第四週測驗題
• 作業區

測驗 1

LeetCode 461. Hamming Distance 提及，兩個整數間的 Hamming distance 為其二進位的每個位元的差。請計算輸入參數兩整數 x 與 y 的 Hamming distance，例如整數 1 的二進位為 0 0 0 1，而整數 4 的二進位為 0 1 0 0，則 1 與 4 的 Hamming distance 為 2。

運用第 3 周測驗 提到的 __builtin_popcount (gcc extension 之一)，我們可實作如下:

int hammingDistance(int x, int y) {
    return __builtin_popcount(x OP y);
}

參考資訊:

• 詳解二進位數中 1 的個數

個人解題思路

OP = ?

1. 考慮到使用 __builtin_popcount, 因此直觀地使用 XOR 來使得兩個輸入 x, y 相同的 bit 結果為 0, 而不同的 bit 為 1

延伸問題

• 解釋上述程式碼運作原理，並舉出不使用 gcc extension 的 C99 實作程式碼
• 練習 LeetCode 477. Total Hamming Distance，你應當提交 (submit) 你的實作 (C 語言實作)，並確保執行結果正確且不超時

• 以下為我的實作 (naive.c), runtime 目前為 48ms (better than 35%), 待改進
• 我使用直覺的想法, 以陣列紀錄 0, 1 的個數方式, 以空間換取時間以避免 TLE

int totalHammingDistance(int* nums, int numsSize){

    int res = 0;
    int zeroCount[31] = {0};
    int oneCount[31] = {0};
    
    if (!numsSize)
        return 0;
    
    for(int i=0; i<numsSize; i++)
    {
        for(int j=0; j<30; j++)
        {
            if(nums[i] & (1 << j))
            {
                res += zeroCount[j];
                oneCount[j]++;
            }
            else
            {
                res += oneCount[j];
                zeroCount[j]++;
            }
        }
    }
    
    return res;
}

或許試著找出減少 branch 的方法

• 研讀錯誤更正碼簡介及抽象代數的實務應用，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說
  • 搭配閱讀 Hamming codes, Part I 及 Hamming codes, Part II，你可適度摘錄影片中的素材，但應當清楚標註來源
• 研讀 Reed–Solomon error correction，再閱讀 Linux 核心原始程式碼的 lib/reed_solomon 目錄，抽離後者程式碼為單獨可執行的程式，作為 ECC 的示範

測驗 2

TODO

測驗 3

白板 coding 其實本意 (最好不要是) 不是考一些你已經會的東西，而是考一個你可能不會的問題，然後你要 keep trying, keep doing 下去，因為它的本質是在考一個未來你可能碰到的問題 (而且可能 Google 不到)。
出處: 簡單的 FizzBuzz 藏有深度 (Google 面試題)

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

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

直覺的實作程式碼如下: (naive.c)

#include <stdio.h>
int main() {
    for (unsigned int i = 1; i < 100; i++) {
        if (i % 3 == 0) printf("Fizz");
        if (i % 5 == 0) printf("Buzz");
        if (i % 15 == 0) printf("FizzBuzz");
        if ((i % 3) && (i % 5)) printf("%u", i);
        printf("\n");
    }
    return 0;
}

觀察 printf 的(格式)字串，可分類為以下三種:

1. 整數格式字串 "%d" : 長度為 2 B
2. “Fizz” 或 “Buzz” : 長度為 4 B
3. “FizzBuzz” : 長度為 8 B

考慮下方程式碼:

#define MSG_LEN 8
char fmt[MSG_LEN + 1];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");

我們若能精準從給定輸入 i 的規律去控制 start 及 length，即可符合 FizzBuzz 題意:

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

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

#define MSG_LEN 8

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[MSG_LEN + 1];
        strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);
        fmt[length] = '\0';

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

gcc-9 還內建了 FizzBuzz optimization (Bug 82853 - Optimize x % 3 == 0 without modulo)。

個人解題思路

KK1 = ?

1. 觀察程式碼, 發現 div3, div5 分別表示整數 i 能否被 3, 5 整除
2. 考慮到要從不同的 start 複製 "FizzBuzz%u" 字串, 可以判斷用 MSG_LEN 進行左移兩次的數值 KK1 與 (KK2 << KK3) 個別在處理 能被 5 整除 以及 能被 3 整除的情況
3. 考慮到 i 是 3 的倍數或是 15 的倍數時, 都應該從 [0] 處開始複製, KK1 應為 div5 (否則沒有其他判斷 div5 處)

KK2 = ? KK3 = ?

1. 假設 i 為 3 之倍數, 應該從 [0] 處開始複製, 此時 (KK2 << KK3) 必須為 3 以上的值
2. 但同時考慮到 i 不為 3 的倍數時, 只能透過 KK2 = div3 且 KK3 = 2 來控制此種條件