contributed by < Tcc0403 >
考慮以下對二個無號整數取平均值的程式碼:
這個直覺的解法會有 overflow 的問題,若我們已知 a, b 數值的大小,可用下方程式避免 overflow:
可改寫為以下兩種等價實作:
前兩項的操作為右移一位元,可以視作為 a
, b
兩值除以 2
看似沒有問題,但先進行右移操作,會忽略 a
, b
兩值相加最低位元進位的情況,
因此我們需要補上第三項,判斷最低位元相加是否進位,若有進位則加 1
a[0] | b[0] | Carry |
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
觀察真值表可以得到
轉成程式碼,第三項 EXP1
即為 a & b & 1
回顧半加器 (Half adder) 實作方法
A | B | Carry | Sum |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 |
1 | 0 | 0 | 1 |
1 | 1 | 1 | 0 |
由真值表可得
進行多位元加法時,除了計算兩數在該位元的加總值 (Sum) ,計算出的進位值 (Carry) 還得進位至高位元 (i.e. 第 位元所計算出的進位值必須加到第 位元)
轉成程式碼即為 a & b + (a ^ b) << 1
,等價於 a + b
a & b + (a ^ b) << 1
兩項分別右移一位 (a & b) >> 1 + (a ^ b)
,即為兩數平均(a + b) / 2
EXP2
= a & b
, EXP3
= a ^ b
延伸問題
移動平均(Moving average),又稱滾動平均值、滑動平均,在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數,來分析資料點的計算方法。
移動平均通常與時間序列資料一起使用,以消除短期波動,突出長期趨勢或周期。短期和長期之間的閾值取決於應用,移動平均的參數將相應地設置。例如,它通常用於對財務數據進行技術分析,如股票價格、收益率或交易量。它也用於經濟學中研究國內生產總值、就業或其他宏觀經濟時間序列。
DECLARE_EWMA(name, _precision, _weight_rcp)
巨集依據引數宣告相應的結構體以及操作相關函式
unsigned long
型態的成員 internal
init
, read
, add
_precision
決定 internal
中要用多少位元當作小數部分,即計算平均的精度_weight_rcp
決定計算新的平均值時,新數值與原本平均值的權重觀察 add
函式中實際計算新平均數的程式碼段落
weight_rcp
為以 2 為底的 _weight_rcp
之對數add
,此時 internal
為 0,便直接將新數值作為平均值依照前面訂定的精度格式寫入在實作方法中,由於權重必定為 2 的冪,便可以使用位移操作取代計算效率較低的除法操作,
改寫〈解讀計算機編碼〉一文的「不需要分支的設計」一節提供的程式碼 min,我們得到以下實作 (max):
觀察題目提及的 min
函式
該函式中先計算 diff = a - b
,再透過 bitwise 操作觀察最高位元判斷正負:
diff
為負,即 a < b
, diff & (diff >> 31)
會得到 diff
, b + (diff & (diff >> 31)
所得到的結果即為 a
對有號負數數進行右移是 implementation-defined,在不同環境可能會有不同結果,上述假設對有號負數右移為算術位移 (Arithmetic shift)
摘錄自 C99 [6.5.7] Bitwise shift operators :
The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type
or if E1 has a signed type and a nonnegative value, the value of the result is the integral
part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the
resulting value is implementation-defined.
diff
為正, 即 a > b
, diff & (diff >> 31)
會得到 0 , b + (diff & (diff >> 31)
所得到的結果即為 b
上述函式在判斷最高位元時,順便將此判斷式作為位元遮罩得到相應的修正量,以達成 branchless
分析原題目 max
函式
可以將 a
視作原本給定的值, EXP4
視作相應的修正量, EXP5
為判斷式兼位元遮罩:
EXP5
需要等於 0 , 即 a < b
a < b
為 1,由於二補數編碼的關係,前面加上負號可將其變為 0xFFFF 的位元遮罩,與 EXP4
做位元運算會得到 EXP4
,要使原式 a ^ (EXP4) = b
,透過與 a 自己做 XOR
運算再與欲得之值 b
做 XOR
便能成立,即 EXP4
= a ^ b
延伸問題
git log
檢索。max
:改寫上方的有號整數版本 min
(diff >> 31)
作為判斷式兼位元遮罩,按照上面分析, diff
為正時位元遮罩為 0
,回傳值即是第一項,故改寫為 a
diff
為負,需要回傳 b
= a + (b - a)
= a + (-diff)
,故原本的修量需要補上負號才能正確回傳 b
min
:改寫上方的無號整數版本的 max
只要修改判斷式成立的條件即可
考慮以下 64 位元 GCD (greatest common divisor, 最大公因數) 求值函式:
改寫為以下等價實作:
等價實作中的 do-while 迴圈與原程式中的 while 迴圈皆是在進行輾轉相除法,結束條件為除數等於零,觀察兩段程式碼可以發現 v
皆是當中的除數,因此 COND
同樣也是 v
由於在等價實作中,進行輾轉相除法之前先提出了 u
, v
兩數為最大的 2 的冪公因數,在回傳之前,必須先將由輾轉相除法得到的被除數 u
進行修正,將上面提出的最大的 2 的冪公因數乘回去,RET
即 u << shift
延伸問題
GCD 演算法
以下分段說明:
對應至 GCD 演算法第 2 點
若 u 和 v 中其中一數為 0 ,則直接回傳另一數
x | 0
會得到 x
對應至 GCD 演算法第 3 點
先取出u
和 v
之間屬於 的公因數,shift
即為最大的
對應至 GCD 演算法第4 點
當 u
為偶數時,可以除以
其中 while(!(v &1)) v /= 2;
對應至 GCD 演算法第 5 點
可以透過迴圈不變性 (loop invariant) 來幫助解讀程式
u
為被除數v
為除數當除數 v
為 0 時結束迴圈,被除數 u
為進入迴圈前 u
和 v
的最大公因數
事實上 u
在迴圈前不一定是被除數,因為先前透過 GCD 演算法第 4 點去除不必要的計算
最後回傳最大公因數時,乘上原先取出屬於 的公因數,可以透過左移達成
__builtin_ctz
改寫程式已知除法運算會耗費較多時間,我們可以利用 __builtin_ctz
(編譯器會產生對應到現代微處理器的專門指令) 搭配上述針對二進位特性調整的演算法,減少除法的使用
改寫之前先透過 perf 分析程式,將一百萬組由 rand
函式生成的亂數傳入 gcd64
函式執行
由上圖可以發現,花費 CPU 週期數最多的段落為迴圈當中的 v /= 2
運算,佔據約 28%
以下為改寫過後的程式
透過 perf 分析前後差異
將同樣一百萬筆由 rand
函式所產生的亂數傳入 gcd64
和 gcd64_ctz
函式比較,發現改寫過後的版本花費時間幾乎是原來的一半
在影像處理中,bit array (也稱 bitset) 廣泛使用,考慮以下程式碼:
考慮 GNU extension 的 __builtin_ctzll 的行為是回傳由低位往高位遇上連續多少個 0 才碰到 1。
用以改寫的程式碼如下:
其中第 9 行的作用是找出目前最低位元的 1,並紀錄到 t 變數。舉例來說,若目前 bitset 為 ,那 t 就會變成 ,接著就可以透過 XOR 把該位的 1 清掉,其他保留 (此為 XOR 的特性)。
題目提示要考慮到 -bitwise 的特性,在二補數編碼中,恰巧最低位元的 1 之下的位元皆會保留
(e.g. )
利用此特性,自己與自己的負數(二補數)進行 AND
操作,即可找出最低位元的 1
EXP6
即為 `bitset & -bitset'
延伸問題
以下是 LeetCode 166. Fraction to Recurring Decimal 的可能實作:
請補完,使得程式碼符合預期,儘量以最簡短且符合一致排版的形式來撰寫。
先觀察 PPP
, MMM
, EEE
所處迴圈(第 77-97 行)的用途,可以大致分成三個部分:
remainder
是否存在於 hashmap 之中
result
後,結束該函式並回傳remainder
PPP > 0
為條件式的 while 迴圈,負責更新循環小數前的部分,前面透過 find
函數取得循環小數開始的位數 pos
,所以這裡需要更新 pos
個位數,由於該迴圈內部沒有額外操作,透過 pos--
使迴圈執行的同時遞減 pos
, PPP
即 pos--
MMM
, EEE
處於同一行,該行的作用為將建立好的節點插入對應的 hashmap 位置, MMM
即是 list API 插入節點的巨集 list_add
,至於要插入哪一個 head (heads[?]),需要回頭去看 hash 是如何計算,找到 find
函式有寫到 hash = key % size
,上面呼叫 find
函式時,是將 remainder
傳入 , EEE
即是 heads[remainder % size]
延伸問題
例如,判斷負號只要寫作
bool isNegative = numerator < 0 ^ denominator < 0;
搭配研讀 The simple math behind decimal-binary conversion algorithms
mm/
目錄 (即記憶體管理) 中,找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例,予以探討和解說其應用場景
__alignof__
是 GNU extension,以下是其可能的實作方式:請補完上述程式碼,使得功能與
__alignof__
等價。
觀察題目中的實作方法,發現是兩個位址相減
先透過結構體指標 struct {char c; t _h; } *
將 0 視作該結構體的起始位址,
再存取型態為 t
的結構體成員 _h
位址,減去前一個成員的位址,
便可算出型態 t
在當前環境的 alignment
M
即是上述提到要測試的型態成員 _h
,由於成員 c
作為第一個成員,起始位址與結構體相同,
X
即是一開始設定的結構體起始位址 0
延伸問題
__alignof__
的使用案例 2 則,並針對其場景進行解說ALIGN
, ALIGN_DOWN
, ALIGN_UP
等巨集,探討其實作機制和用途,並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻,儘量共用相同的巨集考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目:
- 從 1 數到 n,如果是 3的倍數,印出 “Fizz”
- 如果是 5 的倍數,印出 “Buzz”
- 如果是 15 的倍數,印出 “FizzBuzz”
- 如果都不是,就印出數字本身
直覺的實作程式碼如下: (naive.c)
觀察
printf
的(格式)字串,可分類為以下三種:
- 整數格式字串
"%d"
: 長度為 2 B- “Fizz” 或 “Buzz” : 長度為 4 B
- “FizzBuzz” : 長度為 8
考慮下方程式碼:
我們若能精準從給定輸入 i 的規律去控制
start
及length
,即可符合 FizzBuzz 題意:以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (
bitwise.c
)其中
is_divisible
函式技巧來自 Faster remainders when the divisor is a constant: beating compilers and libdivide,甚至 gcc-9 還內建了 FizzBuzz optimization (Bug 82853 - Optimize x % 3 == 0 without modulo)。
請補完,使得程式碼符合預期,儘量以最簡短且符合一致排版的形式來撰寫。
依據題目需求,先整理各個條件所對應的長度 length
和起點 start
:
length | start | |
---|---|---|
3 的倍數 | 4 | 0 |
5 的倍數 | 4 | 4 |
15 的倍數 | 8 | 0 |
都不是 | 2 | 8 |
可以發現長度 length
都是 2 的冪
符合條件數與所需的位移量剛好相等,可將判斷條件的布林值直接帶入 KK1
, KK2
,分別為 div3
, div5
再來起點的部分,題目已經先給定了 9 >> div5
的操作,透過真值表觀察位移量
9 >> div5 | (9 >> div5) >> (KK3) | KK3 | |
---|---|---|---|
3 的倍數 | 9 | 0 | 3 |
5 的倍數 | 4 | 4 | 0 |
15 的倍數 | 4 | 0 | 2 |
都不是 | 9 | 8 | ? |
發現題目有問題
延伸問題
naive.c
和 bitwise.c
效能落差
printf
更換為 sprintfbitwise.c
程式碼,試圖運用更少的指令來實作出 branchless;
kernel/time/
目錄的標頭檔和程式碼)
過程中,你可能會發現可貢獻到 Linux 核心的空間,請充分討論