sysprog2020
目的: 檢驗學員對 數值系統 及 bitwise 操作 的認知
1
依據 ISO/IEC 9899:TC2 (即 C99) 標準的 6.5.7 章節 (第 84 到第 85 頁):
"The result of
E1 >> E2
is E1 right-shifted E2 bit positions. … If E1 has a signed type and a negative value, the resulting value is implementation-defined."
在 C 語言中,對有號型態的物件進行算術右移 (arithmetic right shift,以下簡稱 ASR 或 asr) 歸屬於 unspecified behavior,包含 Cppcheck 在內的靜態分析器會嘗試找出 C 程式中這項 unspecified behavior。考慮到程式碼的相容性,我們想實作一套可跨越平台的 ASR,假設在二補數系統,無論標的環境的 shift 究竟輸出為何,我們的 ASR 總可做到:
上述 正是 的輸出,並向 進位 (rounding)。
針對有號整數的跨平台 ASR 實作如下:
請補完程式碼。
作答區
OP1 = ?
(a)
<< 1
(b)
>> 1
(c)
* m + n
(d)
+ m
(e)
+ n
(f)
- m
(g)
- n
OP2 = ?
(a)
m
(b)
n
(c)
m < 0
(d)
m == 0
(e)
m > 0
(f)
n < 0
(g)
n == 0
(h)
n > 0
提示: 透過 gcc/clang 編譯程式碼時,可加上 -fsanitize=undefined
編譯參數,在執行時期若遇到未定義行為,會得到以下錯誤訊息:
runtime error: load of misaligned address 0x7ffd8a89be8f for type 'int', which requires 4 byte alignment
補充資訊:
延伸問題:
2
在 C 語言:數值系統篇 中,我們介紹過 power of 2 (漢字可寫作「二的冪」)。
女星楊冪的名字裡,也有一個「冪」字。且,她取這個名字,就有「次方」的意義,因為她一家三口都姓楊,所以是「楊的三次方」。
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 位元寬度。實作程式碼如下:
請補完程式碼。
作答區
OPQ = ?
(a)
> 0
(b)
> 31
(c)
>> 0x2
(d)
>> 0x1
(e)
| 0x1
(f)
& 0x1
(g)
^ 0x1
延伸問題:
clz
的實作方式,並舉出 Exponential Golomb coding 的案例說明,需要有對應的 C 原始程式碼和測試報告;
x-compressor 是個以 Golomb-Rice coding 為基礎的資料壓縮器,實作中也用到 clz/ctz 指令,可參見 Selecting the Golomb Parameter in Rice Coding。
3
population count 簡稱 popcount 或叫 sideways sum,是計算數值的二進位表示中,有多少位元是 1
,在一些場合下很有用,例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 0
元素個數、計算兩個字串的 Hamming distance。Intel 在 2008 年 11 月 Nehalem 架構的處理器 Core i7 引入 SSE4.2 指令集,其中就有 CRC32
和 POPCNT
指令,POPCNT
可處理 16-bit, 32-bit, 64-bit 整數。
對應到 C 程式的實作:
函式 popcnt_naive()
利用不斷清除 LSB 直到輸入的數值 v
為 0。
v &= (v - 1)
的作用是將 LSB 設為 0 (reset LSB) 舉例來說,假設輸入數值為 20
:
類似的操作還有
x & -x
,將x
的 LSB 取出 (isolate LSB)
n = -(~n)
等同 n++
,因為在二補數系統中,
因此 popcnt_naive()
的執行時間取決於輸入數值中 1 (set bit) 的個數。可改寫為以下常數時間複雜度的實作:
對於一個 32 bit 的無號整數,popcount 可以寫成以下數學式:
假設 ,先看看 4 個位元,用以上公式可以計算得:
相當於 C 表達式中
x >> 1
稍微改寫可得到:
因此 popcnt 的一般式可改寫為:
因為 ,只要對應的 為 1,這個 bit 就會在 popcnt 的總和中加一,剛好對應 popcnt_naive()
,因此映證上述數學式確實可計算出 population count。
且一個 32 位元無號整數最多有 32 個 1 (set bit),剛好可用一個 byte 表示,所以可分成幾個區塊平行計算,最後再全部加總到一個 byte 中,進行避免檢查 32 次。
popcnt_branchless
實作一開始以每 4 個位元 (nibble) 為一個單位計算 1 的個數,利用最初的公式計算
關鍵的程式碼,逐行解釋:
n = (v >> 1) & 0x77777777
: 將輸入數值 v
除以 2,得到
v -= n
: 計算結果相當於 n = (n >> 1) & 0x77777777
: 再對 n
除以 2,得到 v -= n
: 計算出 最後這段結束後計算出 ,得到每 4 個位元為一個單位中 set bit 的個數
v = (v + (v >> 4)) & 0x0F0F0F0F
: 將每 4 個位元中 set bit 的個數加到 byte 中:
0x0F0F0F0F
做 mask 可得
v *= 0x01010101
: 在最後一道敘述中,將 v
乘上 0x01010101
。寫成直式如下
我們可發現期望輸出就在原本 的位置 (),因此將 v
右移 24 bits 即為所求,剩下的位數會 overflow ,右移後不影響結果。
return v >> 24
: 最後得到的結果會放在 Most significant byte 中,因此向右位移 24 位元,即為所求的 popcount 值。
GCC 提供對應的內建函式:
__builtin_popcount(x)
: 計算 x 的二進位表示中,總共有幾個1
使用示範:
針對 LeetCode 1342. Number of Steps to Reduce a Number to Zero,我們可運用 gcc 內建函式實作,假設 int
寬度為 32 位元,程式碼列表如下:
請補完程式碼。
作答區
AAA = ?
(a)
__builtin_popcount(num)
(b)
__builtin_clz(num)
BBB = ?
(a)
__builtin_popcount(num)
(b)
__builtin_clz(num)
延伸問題:
提示: Bit Twiddling Hacks 中提及許多 bitwise operation 的使用,如 bit inverse、abs 等等,是極好的參考材料。
4
考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式:
改寫為以下等價實作:
請補完程式碼。
作答區
XXX = ?
(a)
u
(b)
v
(c)
u + v
(d)
u - v
(e)
u >> 1
(f)
v >> 1
YYY = ?
(a)
u
(b)
v
(c)
u << v
(d)
v << u
(e)
u << shift
(f)
v << shift
延伸問題:
__builtin_ctz
改寫 GCD,分析對效能的提升;5
在影像處理中,bit array (也稱 bitset
) 廣泛使用,考慮以下程式碼:
可用 clz 改寫為效率更高且等價的程式碼:
請補完程式碼。
作答區
KKK = ?
(a)
bitset
(b)
bitset & 0x1
(c)
bitset | 0x1
(d)
bitset ^ 0x1
(e)
bitset & -bitset
延伸問題: