# 2020q3 Homework3 (quiz3) contributed by < `JimmyLiu530` ＞ ###### tags: `進階電腦系統理論與實作` > [題目](https://hackmd.io/@sysprog/2020-quiz3) ## 測驗1: Arithmetic right shift for signed integers 在 C 語言中，對有號型態的物件進行算術右移(簡稱 ASR)歸屬於 unspecified behavior。考慮到程式碼的相容性，我們想實作一套可跨越平台的 ASR，假設在二補數系統，無論標的環境的 shift 究竟輸出為何，我們的 ASR 總可做到: $-5>>^{arith}1$ $= -3$ 上述 $-3$ 即為 $\dfrac{-5}{2}$ 向 $-\infty$ 進位的輸出 ```c= int asr_i(signed int m, unsigned int n) { const int logical = (((int) -1) OP1) > 0; unsigned int fixu = -(logical & (OP2)); int fix = *(int *) &fixu; return (m >> n) | (fix ^ (fix >> n)); } ``` ### 程式說明 算術右移一個正數其最左邊的 bit 必定是補 0 ，而算術右移一個負數有可能是補 0 或是補 1，而根據題目的意思，顯然是後者，因此需要知道 compiler 是補 0 還是 1。若是補 1，則符合我們的要求不需修補；否則需要修補。而這個修補會在 line 6 的`| (fix ^ (fix >> n))`。 line 3 的用意就是在看此 compiler 對一個負數算術右移後會補 0 還是 1，若補 1，則右移後的結果為負 (<0)，因此 logical 為 0；否則 logical 為 1。所以 `OP1 = >> 1`。 接著，考慮算術右移一個負數補 0 的情況，因為 line 6 的修補項是要用來修補的，所以 `(fix ^ (fix >> n))` 的最高的 n 個位數一定要是 1，也就代表 `fix` 會是 `0xffffffff`，最後可推得 `OP2 = m < 0`。 此結果也符合一開始說的條件: 除了原本 compiler 右移負數補 1 不用修補之外，正數也不需要 (即只有`右移補 0` 且 `為負數`才需要修補)。 :::info 已解問題: `int fix = *(int *) &fixu;` 這樣寫的用意? `int fix = (int) fixu;` 以及可以改成這樣嗎? > 雖然此程式看似可互換，但這兩行程式碼的意義不太相同，前者為 `interpret`，後者為 `cast`。看下面的例子: > ```c= > float a = 0.5; > int b = (int)a; > int c = *(int*)&a; > printf("%f 0x%08x 0x%08x\n", a, b, c); > ``` > 會得到: > ```c= > 0.500000 0x00000000 0x3f000000 > ``` > 也就是說前者以 整數 的角度去詮釋(interpret) 浮點數，好讓我們去對其中的某幾個位元做操作。 > > 而後者是直接把 浮點數 強制轉型(cast)成 整數。 ::: ### 延伸問題 #### 1. 數學證明和 Graphviz 製作的圖解 #### 2. 練習實作其他資料寬度的 ASR，可參照 [C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor) 撰寫通用的巨集以強化程式碼的共用程度; ------------------------------------- ## 測驗2: Leetcode [342. Power of Four](https://leetcode.com/problems/power-of-four/) GCC extension 其中包含兩個函式: ctz 和 clz: > 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. > Built-in Function: int __builtin_clz (unsigned int x) > - Returns the number of ==leading== 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined. 我們可用 `__builtin_ctz` 來實作 LeetCode 342. Power of Four，假設 int 為 32 位元寬度。實作程式碼如下: ```c= bool isPowerOfFour(int num) { return num > 0 && (num & (num - 1))==0 && !(__builtin_ctz(num) OPQ); } ``` ### 程式說明 line 3 的第二個條件 `(num & (num - 1))==0` 其實就區分出 2 的冪次方的數了，像是 $2^3 =1000_{(2)}$ 減1後，$7 = 0111_{(2)}$，因此接下來只要排除掉 2 的冪次方($2^n$)中，n 為奇數的數即可。一樣可以透過觀察: | decimal | binary | # of trailing zero | | ------- | ------ | ------------- | | 2 | 10 | 1 | | **4** = $4^1$ | 100 | **2** | | 8 | 1000 | 3 | | **16** = $4^2$ | 10000 | **4** | | 32 | 100000 | 5 | | **64** = $4^3$ | 1000000 | **6** | 發現 n 為奇數的數，其 trailing zero 也會是奇數個，因此 `OPQ = & 0x1`。 ### 延伸問題 #### 1. 改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量 ```c= bool isPowerOfFour(int num) { return num > 0 && __builtin_popcount(num) == 1 && !(__builtin_ctz(num) & 0x1); } ``` 將原本的 `(num & (num - 1))==0` 改成 `__builtin_popcount(num) == 1`，兩者都可以過濾掉非 2 的冪次方的數。 又或是可以改寫成: ```c= bool isPowerOfFour(int num) { return num > 0 && !(__builtin_popcount(num) ^ 0x1) && __builtin_ffs(num) & 0x1); } ``` `__builtin_popcount(num) == 1` 等價於 `!(__builtin_popcount(num) ^ 0x1)`，且 4 的冪次方的數其 first set bit 的位置會是奇數。 > Built-in Function: int __builtin_ffs (int x) > - Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero. #### 2. 練習 LeetCode [1009. Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/) 和 [41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/)，應善用 clz **Complement of Base 10 Integer**: ```c= int bitwiseComplement(int N){ if (N == 0) return 1; uint32_t mask = 0xffffffff >> __builtin_clz(N); return N ^ mask; } ``` ![](https://i.imgur.com/98Sq7j0.png) - 位元反轉 -> 想到 `^ 1111...1111` - 只需要反轉最低 `32 - (N 的 leading zero)` 個位元 **First Missing Positive**: ```c= // TODO ``` ---------------------------------------------- ## 測驗3: LeetCode [1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/) 給定一個非負整數 `num`，回傳將此數依照下面的規則變成 0 需要幾步。而規則就是: > 當目前的數為偶數，則將它除以 2；否則將它減 1。 我們可運用 gcc 內建函式實作，假設 int 寬度為 32 位元，程式碼列表如下: ```c= int numberOfSteps (int num) { return num ? AAA + 31 - BBB : 0; } ``` ### 程式說明 因為在正整數中，除以 2 即為右移 1 位元，所以總共要除幾次就等於 MSB 移到最低位需要移幾次，MSB 移至最低位需 `31 - __builtin_clz(num)` 步，因此也需要除那麼多次。 再者，當 `num` 的二進位表示法中有 k 個 1 時，代表總共需要做 k 次的減 1，因為這些 1 總會被移到最低位元的位置，而最低位元為 1 代表是奇數需要減 1 ，所以共需 `__builtin_popcount(num)` 次減 1 因此最後答案就會是 `AAA = __builtin_popcount(num)` 及 `BBB = __builtin_clz(num)` ### 延伸問題 #### 1. 改寫上述程式碼，提供等價功能的不同實作並解說 ```c= // TODO ``` #### 2. 避免用到編譯器的擴充功能，只用 C99 特徵及 bitwise 運算改寫 LeetCode [1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)，實作出 branchless 解法，儘量縮減程式碼行數和分支數量 ```c= // TODO ``` --------------------------------------- ## 測驗4: 64-bit GCD 考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式: ```c= #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; } ``` 改寫為以下等價實作: ```c= #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 (XXX); return YYY; } ``` ### 程式說明 此改寫後的程式與最原本單純利用輾轉相除法不同的點在於，做輾轉相除法之前，先做了以下的步驟: - 先將兩數中所有 2 的因數都提出來，最後再將結果**左移**對應的位數即可 - 當其中一數不存在 2 因數時，代表 2 就不會是他們的公因數，因此將另一個仍含有 2 因數的數除以 2 直到變成奇數, e.g. gcd(24,9) = gcd(6,9) line 5-6 其實就是在做上述的第一點，總共提出`shift` 個 2。line 8-9 及 11-12就是做上述的第二點。而程式中的 do-while 其實就是輾轉相除法，只是是用減法去實現，因此 `XXX = v`。最後，再將原本的結果 u 左移 shift 個 bit(即 x$2^{shift}$)，所以 `BBB = u << shift`。 ### 延伸問題 #### 1. 在 x86_64 上透過 `__builtin_ctz` 改寫 GCD，分析對效能的提升 ```c= uint64_t gcd64(uint64_t u, uint64_t v) { if (!u || !v) return u | v; int shift; int ctz_u = __builtin_ctz(u); int ctz_v = __builtin_ctz(v); if (ctz_u < ctz_v) shift = ctz_u; else shift = ctz_v; u = u >> ctz_u; v = v >> ctz_v; do { while (!(v & 1)) v /= 2; if (u < v) { v -= u; } else { uint64_t t = u - v; u = v; v = t; } } while (v); return u << shift; } ``` // TODO分析 _____________________________________ ## 測驗5: Positions of set bits in bit array 在影像處理中，[bit array](https://en.wikipedia.org/wiki/Bit_array) (也稱 bitset) 廣泛使用，考慮以下程式碼: ```c= #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; } ``` 可用 clz 改寫為效率更高且等價的程式碼: ```c= #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 = KKK; int r = __builtin_ctzll(bitset); out[pos++] = k * 64 + r; bitset ^= t; } } return pos; } ``` ### 程式說明 第一個程式的作用在於看 `bitmap` 中哪些 bit 為 1，並將其位置記錄在 `out` 中。第一與第二個程式只有 line 8 的那個 while 的不同而已，因此聚焦在此。 透過觀察第一個程式碼，可知其脈絡為一個位元一個位元地去檢查 `bitset` 是否為 1，即 若要檢查第 k 個位元，需將 `bitset` 右移 k 位元，再與 1 比較。 而第二個程式也是 follow 這個脈絡，只是在 line 10 計算了 `bitset` 的 trailing zero，可以減少傻傻地去檢查為 0 的位元的時間，來提升效率。最後，line 12 需將把檢查過的位元變成 0，因此 `KKK = bitset & -bitset`，這是因為 `x & -x = x & (~x + 1) = 保留其 LSB，其餘設為 0`，所以 x ^ (x & -x) 會將原本 x 的 LSB 變成 0。 ### 延伸問題 #### 1. 舉出這樣的程式碼用在哪些真實案例中 - 在 linux kernel 中有使用這種資料結構 - 第 k 位被設成 1 若且唯若 k 在佇列裡時，可提升從硬體中找到「首位 0」操作的效率 - 也會用在記憶體頁、inode、磁碟分割區等的分配上，去看哪些記憶體已被使用 #### 2. 設計實驗，檢驗 clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 [bitmap density](http://www.vki.com/2013/Support/docs/vgltools-3.html) #### 3. 思考進一步的改進空間
Last changed by  
 
JimmyLiu0530
380

Read more

台灣萬萬稅

報稅懶人包

12/17/2023
CS:APP 第一章重點整理 - Introduction

contributed by < JimmyLiu0530 > {%hackmd BJrTq20hE %} 課程錄影 (Fall 2015) 課程錄影(中英字幕) 課程介紹 (Spring 2021) 概述 CS:APP 在一開始利用所有新手程式員學的第一支程式，即在螢幕上輸出 hello world，來展示程式從被產出、執行、結束的過程，也幾乎都有點到了各章節的重點，因此接下來內容的範例幾乎都是以 hello.c 為主。

3/11/2022
GDB介紹

{%hackmd BJrTq20hE %} 最簡單方便的除錯工具不外乎是列印指令 (e.g., printf)，但是設想下以下的情況： 某個迴圈可能在第一百萬零七十三次才出錯，這當中印出來的 debug 資料可能多到令人頭昏。因此我們需要一個工具，讓我們可以一邊執行你的程式, 一邊視需要將它停下來觀察當中某些變數的變化。如果發現問題不在此處，還可以叫它繼續執行。執行到一半，還可以手動修改變數的值，看看如果這個問題解決了，下個又在何處，一口氣解決好幾個問題。這些就是 debugger 的工作。 GDB 一種命令列模式的 debugger。若以下列語言撰寫程式 C, objective C, C++, Fortran, Pascal, Ada, ... 等等，而且採用的編譯器是來自 gnu，那麼就可以拿 GDB 來除錯。 使用方法 (以 c 程式舉例) 首先在編譯程式時，需要加上 -g 參數，以便編譯器將除錯資訊加入到程式裡:

3/11/2022
Ubuntu 20.04 wifi 選項消失之解決方法

{%hackmd BJrTq20hE %} 發生原因：如果 windows 中 wifi 可用，但在 Ubuntu 下不可用，那麼及有可能是無線網卡的驅動程式損壞或是消失。因此我們接下來要手動將驅動程式安裝回來。 首先，打開 terminal 使用命令查詢網卡的狀態 $ lshw -C network 得到類似的訊息如下：

3/11/2022
Read more from JimmyLiu0530
Published on HackMD