sysprog2020
homework
contributed by < JKChun
>
1
解釋上述程式運作原理,應提供數學證明和 Graphviz 製作的圖解;
sign bit
( Sign Extension ),-1
為 0xFFFFFFFF
sign bit
,則 -1
右移後還是 0xFFFFFFFF
,會小於0,logical
為0,代表我們不用幫右移後的數補齊1sign bit
,則 -1
右移後會是 0x7FFFFFFF
,會大於0, logical
為1,代表我們要幫右移後的數補齊1m
為負數時,才需要自己補齊 sign bit
,所以只有在此情況 unsigned int fixu
為 0xFFFFFFFF
,其他情況都是0return (m >> n)
就行,如果需要自己補齊 sign bit ,就需要補齊從 MSB ( Most Significant Bit ) 開始往後數的 n 個 bit 為1, (fix ^ (fix >> n))
就可以滿足這樣的結果,假如 n 等於 6,則 (fix ^ (fix >> n))
為 0xFC000000
,就是 11111100000000000000000000000000
,再讓 (m >> n)
跟 (fix ^ (fix >> n))
做 OR 運算
就可以補齊2.練習實作其他資料寬度的 ASR,可參照 C 語言:前置處理器應用篇 撰寫通用的巨集以強化程式碼的共用程度;
2
解釋上述程式運作原理;
num > 0
:放這段的原因在於 num
在 的情況不會是 power of four,所以 num
如果不大於 0 就可以直接 return false(num & (num - 1))==0
:這段是在判斷 num
是否為 2 的 n 次方
num
不是 ,那絕不可能是 power of four!(__builtin_ctz(num) & 0x1)
:如果 num
為 power of four,則它的 trailing 0-bits 一定是偶數個(0, 2, 4,…),__builtin_ctz(num)
的結果最後一個 bit 絕對不是 1,以此區分 和
__builtin_ctz(num) | Binary |
---|---|
00000000 | |
00000010 | |
00000100 |
改寫上述程式碼,提供等價功能的不同實作,儘量降低 branch 的數量;
練習 LeetCode 1009. Complement of Base 10 Integer 和 41. First Missing Positive,應善用 clz;
研讀 2017 年修課學生報告,理解 clz 的實作方式,並舉出 Exponential Golomb coding 的案例說明,需要有對應的 C 原始程式碼和測試報告;
x-compressor 是個以 Golomb-Rice coding 為基礎的資料壓縮器,實作中也用到 clz/ctz 指令,可參見 Selecting the Golomb Parameter in Rice Coding。
3
解釋上述程式運作原理;
answer:
根據題目給的 example 可以發現整個運算就是:
以題目的 14 (1110) 為例:
以上面的例子可以發現:
0x0000000E
(1110) 中,最左側的 1 到 0 有 4 個 bit ( 32 - __builtin_clz(num) ),所以有 3 個 shift step,因為最左側的 1 不 shift 只減 10x0000000E
(1110) 中有3個 1 所以有 3 個減 1 step總結:
32 - __builtin_clz(num) - 1
計算 shift step __builtin_popcount(num)
計算 減 1 的 step改寫上述程式碼,提供等價功能的不同實作並解說;
提示: Bit Twiddling Hacks 中提及許多 bitwise operation 的使用,如 bit inverse、abs 等等,是極好的參考材料。
避免用到編譯器的擴充功能,只用 C99 特徵及 bitwise 運算改寫 LeetCode 1342. Number of Steps to Reduce a Number to Zero,實作出 branchless 解法,儘量縮減程式碼行數和分支數量;
4
考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式:
改寫為以下等價實作:
解釋上述程式運作原理;
!((u | v) & 1)
這個判斷式是在 u
與 v
皆為偶數的情況 ( LSB 為 0 ) 才會成立 ( 0 與 1 AND 等於 0,再 NOT 則為 1 )shift
存數量,用在最後 shift ( 左移、乘以 2 ) 結果u << shift
將 u 乘上之前除掉的共同因數並 return 結束在 x86_64 上透過 __builtin_ctz 改寫 GCD,分析對效能的提升;
5
在影像處理中,bit array (也稱 bitset) 廣泛使用,考慮以下程式碼:
可用 clz 改寫為效率更高且等價的程式碼:
解釋上述程式運作原理,並舉出這樣的程式碼用在哪些真實案例中;
設計實驗,檢驗 clz 改寫的程式碼相較原本的實作有多少改進?應考慮到不同的 bitmap density;
思考進一步的改進空間;