contributed by < allenliao666 >
思路:運用直式開方法的變形,找出要開平方的數的 MSB
並持續測試回傳值平方後是否超過原數,直到 LSB
。
ffs
: 回傳第一個(Least significant) 被設定的位元
fls
: 回傳最後一個(Most significant) 被設定的位元
可以用fls
取代題目中的__builtin_clz()
,改寫如下:
在 Linux 原始程式碼以關鍵字 sqrt
搜尋,發現在 arch 、 driver 等目錄下有非常多有關平方根運算的程式碼,其中在 linux/block/blk-wbt.c 僅有一段程式碼有關 sqrt
如下:
考量在相鄰敘述進行 mod 10 和 div 10 操作,觀察除法原理:
可以發現 ,若我們知道 div 10,就可以反推得出 mod 10。
,因為10並非2的冪,所以我們使用近似值 實做。首先透過 bitweise operation 湊出13,因為13 = 8 + 4 + 1 ,等同計算 如下
但 LSB 數來3個位元會被捨棄,因此在上述操作前要先記錄該位元。文中的 0b1
表示二進位表示法的1。
把上述兩段程式碼結果相加後,即可得到 。最後除以128達到 ,即 div10的效果。不過令人疑惑的是為什麼 不透過 bitwise 左移如下,而是使用右移和 d0, d1,d2 補回位元?
完整程式碼如下
題目程式碼如下
用 、、、 和輸入值 比大小,若 ,表示 x。並對 右移 x 位元。反之,若 ,則比較 和 的大小, ,直到最後。
計算以2為底的對數,等同尋找 fls
,因此使用 __builtin_clz
改寫如下:
在 kernel/sched/fair.c 中有部分程式碼使用對數,例如SCHED_TUNABLESCALING_LOG
等排程器相關設定。
首先 EWMA 使用結構體紀錄相關資訊如下:
internal
: 目前的 EWMA
factor
: 定點數的小數位元數
weight
:EWMA 的衰變率
從 ewma_read
在輸出前執行avg->internal >> avg->factor
可以發現 EWMA 是以定點數的格式儲存,因此輸出時才要右移 avg->factor
個位元。
EWMA原式定義為:
即隨著 增加,前 個數值的影響逐漸減少。但對應到 ewma_add
中:
和原式的計算方式略有不同,經過左右同乘 後:
就會符合程式碼的計算方法,因此可知 avg->weight
和 的關係為:
完整程式碼:
首先 x--
確保後續的 x > 等比較大小時,能輸出1的 x 必大於 。換句話說,避免 x 等於2的冪時,最終輸出的對數取頂會比正確值多1。接著拿 x 和 比較大小,若 x 較大,則用 r 紀錄對應的 bitwise 右移量,同時 r 也代表 x 的對數,並且使用 shift 持續更新 r 。執行到 return (r | shift | x > 1) + 1;
時, x 已經右移30位元,只剩下最後2位元可能非零,即 x 可能為0到3其中之一,所以用 x > 1
檢測。最後因為要取頂,所以再加1。
popcount 用於計算數值的二進為表示中,有多少位元設定為1
,其數學式:
設 ,經過推導後,得到:
依照上述數學式,我們以 4 個位元(nibble)為一組計算1的個數,即 ,實作程式碼如下
v >> 1
: 即 。例如令 v 為7,二進位表示式為0111,右移1位元後就得到3,等同 。
n & 0x77777777
: 因為以 nibble 為單位操作,所以要與0x77777777進行 bitwise & 。舉例如下
接著分析 v = (v + (v >> 4)) & 0x0F0F0F0F
的功能:
0x0F0F0F0F
為 mask 得到最後執行 v *= 0x01010101
,令 (B1+B0) 為 A0 ,依此類推
可以發現在原本 A6 的位置即是 v 的 set bit 的個數,因此將 v 右移24位元即為所求。
Hamming Distance 為兩個整數的二進位表示每個位元差的和,例如
0001 //1
1000 //4
兩數間的 Hamming Distance 為2。以下透過 A B 計算 A 和 B 之間每個位元差,再用 GCC 內建函式 __builtin_popcount(x)
計算位元差的總和。
就 LeetCode 477. Total Hamming Distance 的其中一解的程式碼
上述程式碼自 num[] 中依序比較 i 和 j 的 Hamming Distance 並記錄在 total ,其時間複雜度為 ,因為 num[] 中每個元素都會被算到兩次,所以最後一行右移1位元。
從位元的角度出發,改進如下
以 nums[3] = {4, 14 ,2}為例,他們的二進位表示法如下
0100 //4
1110 //14
0010 //2
首先自 LSB 觀察,發現3個數值的 LSB 皆為0,所以此位元的 Hamming Distance = 0。
接著觀察 位元,1有兩個,所以此位元的 Hamming Distance = 2 * numsize - 2。
因此我們可以歸納出每個位元的 Hamming Distance = 該位元1的數量 * numsize - 該位元1的數量,時間複雜度改進為 。
程式中 i
表示目前的位元位置, nums[j] 右移後和1執行 bitwise & 以檢測該位元是否為1,並用 bitTotal
紀錄此位元1的數量。最後再加總各位元的 bitTotal * (numsSize - bitTotal)
即為輸出值。
AVL tree 和 red-black tree 雖然樹高都屬於 ,但實際上因為 AVL tree 會確保左右子樹的樹高相差不超過1
,因此 AVL tree 的樹會較 red-black tree 茂密(bushy),然而也必須花費更高成本作旋轉( rotation )。
XTree 嘗試兼具 AVL tree 和 red-black tree 的優點,其中 XTree 的平衡機制類似 AVL tree 。 XTree 的 hint 計算方式為,其左右節點 hint 最大值 +1 並且只有在被呼叫到 xt_update 時才會被更新。
XTree 有4個主要操作, rotate_left
, rotate_right
, replace_right
和 replace_left
。 XTree 在插入和刪除節點後會更新部分節點的 hint ,此時會用到 rotate_left
和 rotate_right
;移除節點時會用到 replace_right
和 replace_left
其中之一。
更新 hint 的規則為:
rotate_left
:
rotate_right
replace_right
replace_left
include/linux/rbtree_types.h 中 :
回傳該節點之親代節點的位置,使用 __rb_parent_color & ~3
清除 LSB 數來兩位元後,再將其強制轉型為紅黑數節點的指標。
兩者功能皆為將節點的 __rb_parent_color
設定為自己。