1
: Using bitwise operations to compute square root先看原程式碼
編譯方式
因為呼叫 log2,所以需要連結 libm (math library),即 -lm 選項
假設 N = =,msb = 5
=> a =
接著進入迴圈中
迴圈次數 | a | result | 是否進入迴圈 |
---|---|---|---|
1 | 0 | y | |
2 | 0 | y | |
3 | 0 | y | |
4 | y | ||
5 | y | ||
6 | 0 | n |
在此 bitwise
操作中, (result + a)
的平方逐一比較 N
值,當值較小時就疊加當前的值,即 result += a
,直到為 N 的開方根值。
此題一開始用十進位去看比較容易明白,
a >>= 1
看作a / 2
。
編譯方式:$ gcc -o i_sqrt i_sqrt.c -lm
版本二使用右移操作直到 n 值為 0 ,藉此計算 msb
版本三使用 Digit-by-digit calculation 方法進行開方根。將平方數拆成 2 的冪相加
令 ,其中 N 即為所求的開方根
即為所求
推論出:
後續將求出所有 or ,從 一直到 ,而求得 只須比較,有兩種情況:
由於每輪逐一比較的運算成本過高,提出了另個想法
將 的值表示位
將(1)式減(2)式可得
其中 平方為
令
最後將 代回到(3)式可得:
將 拆解
得:
藉由位元運算從推出下一輪
Linux 核心原始程式碼 linux/block/blk-wbt.c
尚未完成
2
: Using bitwise operations to perform mod 10 and div 10參考《Hacker's Delight》,採用 bitwise operation 來實作除法
此題選用 a=13 N=7 => ,其中 為 。
完整程式碼
將 改寫成 ,其中 可從下方程式碼得到
由於 tmp
右移三位會遺失原本最低三位的 bit ,因此將分別用 d0
、 d1
、 d2
來儲存原先的 bit ,再將遺失的 bit 補回來,最後在除以128,即為 ,得到一個近似 的結果 ( q
)。
上述程式碼中不太理解為何補足遺失的最低三位 bit 是加上 + d0 + d1 + d2
,在我實作中發現就算缺少這段程式碼也不會影響其結果,其大致的觀念我能理解是為了增加其精度,但又為何不直接加上 + d2
就好。
下方程式碼根據餘數定理:,可以得到 (餘數)
其中(((q << 2) + q) << 1)
等於
將程式碼包裝成
uint32_t x = (in | 1) - (in >> 2)
得到
uint32_t q = (x >> 4) + x;
得到 ,其中 約為 近似
再經由 bitwise 操作使 0.796875 更接近 0.8
最後 *div = (q >> 3);
即為
((q & ~0x7) + (*div << 1));
為 ,其中 為商。
在由餘式定理: 求得 *mod
值為何
練習撰寫不依賴任何除法指令的 % 9 (modulo 9) 和 % 5 (modulo 5) 程式碼
尚未進行
3
: Using bitwise operations to calculate the logarithm base 2用 ilog2
計算以 2 為底的對數,且其輸入和輸出皆為整數。
稍微改寫一下原程式碼方便識讀,舉例
while ( i >= 2 ) | 原 i | 後 i | log |
---|---|---|---|
第 1 次迴圈 | 100 | 10 | 1 |
第 2 次迴圈 | 10 | 1 | 2 |
輸出 log = 2
改寫後的程式碼,將 i
用一定數量的位元去進行判斷,有效提升數字較大時的計算速度,其原因為原程式碼每個位元逐一去判斷,反覆進行多次的迴圈,改後後判斷分成 4 個階段,若 i
大於 則直接進行位元操作。
在 Linux 核心原始程式碼找出 log2 的相關程式碼 (或類似的形式),並解說應用案例
看到 log2 為底的形式就想到 clz
、 ffs
、 fls
等相關的操作都有類似的手法。
在 linux/arch/arc/include/asm/bitops.h 中找到 fls 的實作,其作用為返回最高有效 bit 位(由最低位往左數),當判斷式為 0 進行位移操作,其手法相似 log2 ,不同於位元操作向左進行。
該順序不同於 log2
, constant_fls
從 1 起始,當沒有有效位返回 0 。
4
: Using bitwise to calculate EWMAExponentially Weighted Moving Average
賦予資料指數衰減的權重,主要目的使越舊的資料權重越低,反之越新的資料對整體平均值的影響越大,以下為此統計手法的公式:
@internal
: 看作 當前的位置
@factor
: 縮放因子,必須是 2 的冪次
@weight
: 資料的權重,在這 透過右移來達到,必須是 2 的冪次
一開始 ,因此 對應到 avg->internal = (val << avg->factor);
,接著 avg->internal = (((avg->internal << avg->weight) - avg->internal) + (val << avg->factor)) >> avg->weight
的理解較為困難,看起來與題意的公式不同,在 stevendd543 筆記中的舉例有非常清楚解釋:
令 ,將公式改寫成
其中 等效於 ((avg->internal << avg->weight) - avg->internal)
, 等效於 (val << avg->factor)
,最後將整個公式 >> avg->weight
即為 (當時 的EWMA)。
將計算的平均值除以縮放因子而得到真正的平均值。
在 Linux 核心原始程式碼找出 EWMA 的相關程式碼 (或類似的形式),至少該涵蓋無線網路裝置驅動程式
5
: Test 3 Extension延伸測驗 3,已知輸入必為大於 0 的數值 (即 x > 0),以下程式碼可計算 [log2] ,也就是 ceil 和 log2 的組合並轉型為整數。
x--
目的為避免 x
為 2 的冪,接著使用類似測驗 3
的作法,在指定的位元寬度中比較,若條件成立就會進行位元操作,下方程式碼寫的更加複雜因此實際帶入數值去進一步解釋。
case 1
x = 0000 0000 0000 0000 0000 1000 0000 0000
shift = (x > 0xFF) << 3
決定 x
要右移的大小r |= shift
等效 r += shift
,用來記錄由第 0 bit 往左數到 msb 的有效位x--
的值加回來改進程式碼,使其得以處理 x = 0 的狀況,並仍是 branchless
當 x = 0
時 ceil_ilog2
應要回傳 0 ,因此設立一個 mark
來紀錄最後是否 +1 。
Linux 核心原始程式碼
尚未完成
1
: Total Hamming Distance閱讀 population count 了解計算二進位表示式中有多少個位元為 1
、 了解 Hamming distance 所代表的意思。
更進階的操作參照測驗1,大致內容為每4個位元為一個單位,求出其中的 set bits 個數,32位元中總共有 8 組,將每組算得的 set bits 個數加總在一起,裡面的推導過程需詳讀就能得知最後為何 v >> 24
即為 popcount 。
考題針對 LeetCode 477. Total Hamming Distance
Leetcode 範例描述到
在考題程式碼中為兩兩成對的去計算 popcount ,因此會出現HammingDistance(4, 14)與HammingDistance(14, 4)這種情況,因此最後回傳要除以 2 (即 return total >> 1
)。
不依賴 popcount,嘗試以上述歸納的規則,針對 LeetCode 477. Total Hamming Distance 撰寫出更高效的程式碼
參考 solution 中的解答
使用 bitwise 逐一比較二進制中每個位元是否為 1 ,其判斷式 (nums[j] >> i) & 1
每當比較完一位元,便計算其 HammingDistance 的值 ( ans += c * (numsSize - c)
)
n 'th bit | 3 | 2 | 1 | 0 |
---|---|---|---|---|
input 4 | 0 | 1 | 0 | 0 |
input 14 | 1 | 1 | 1 | 0 |
input 2 | 0 | 0 | 1 | 0 |
2
: Remainder by Summing digits了解 [ 離散數學 ] 同餘(Mod)的性質及定義
詳讀 Hacker's Delight 中提及 Remainder by Summing digits
以除 3 為例, ,
n 以二進制表示成
將上式結合 popcount 寫成程式
0x55 = 0b01010101
0xAA = 0b10101010
再由定理
定理證明在 Hacker's Delight 裡有提到,頁碼:P13
化簡成
為了避免 n
變成負數,因此加上一個足夠大的 3 的倍數,範例中為加 39 ,在第二輪應用使 n
介於 -3~2 之間而非 -3~3 之間。
return n + ((n >> 31) & 3)
主要用作避免 n 為負數值,若為 n 為正則不受影響。
lookup table
使用查表的方式去尋找對應的餘數。
tictactoe.c
將上述手法應用於第三次作業中,追求更有效的賽局判定機制。
3
: XTreeAVL Tree 是一種Binary Search Tree (BST) 實作方法,透過高度計算及 balance factor 判斷是否需要旋轉來平衡。
red-black tree 遵循以下規則來達成平衡:
此題 XTree 的平衡機制與 AVL tree 相似,利用 hint 來評估是否需要做 rotate,然而 xt_node 的 hint 的計算方式是,其左右節點 hint 最大值 +1 並且只有在被呼叫到 xt_update 時才會被更新。
xt_create
: 初始化 XTree
xt_destroy
利用遞迴
將樹裡的每個節點釋放,在 __xt_destroy()
中
若 xt_left
(左子樹)或 xt_right
(右子樹)存在則繼續往下走直到盡頭 tree->destroy_node(n)
來釋放。
xt_first
用遞迴的方式尋找最左邊的節點
xt_last
與 xt_first
一樣,但變成尋找最右變的節點
xt_rotate_left
這段程式碼為下圖操作
假設 p 的右子樹不存在
重新定義 n 節點的 parent
xt_rotate_right
操作手法與 xt_rotate_left
相似,因此僅用圖示
xt_balance
與 AVL Tree 中 Balance Factor of T, BF(T) 的平衡判斷相似,這裡的 hint 為左子樹高 - 右子樹高
xt_max_hint
選擇左子樹與右子樹的 hint 的最大值 +1
即為節點 n 的 hint 值(更新 hint)
xt_update
若樹不平衡 xt_balance < -1
進行 xt_rotate_right
, xt_balance > 1
進行 xt_rotate_left
xt_insert
插入新節點在樹中
xt_remove
當移除一節點 del
時,將該右子樹的最左來填補,即 least
來替換掉原本的 del
,並檢查是否平衡 xt_update
,反之則用左子樹的最右節點來點補,若被刪除的節點為 leaf
將不用進行交換。