contributed by < LindaTing0106
>
i_sqrt 版本一利用 log2 函式得出 N 的最高有效位元在 msb 。 隨後再迴圈內檢查該 N 為二進位表示時,將在逼近的數字加上 後將其平方後,不會超過原數字。
藉由此種方式得出 N 的平方根。
將 log2 函式利用迴圈方式將其取代。
i_sqrt 版本三則是利用 Digit-by-digit calculation 的方式,其中先將要開平方根的數 用二進位方式表示。
假設 ,使其變為 。
若將其表示位十進位則得 ,則要算出 就要將其展開,則為 ,在此 or ,將其利用矩陣展開後可以得其規律。
故此處可以假設
則 。
則 。 為 的平方根,故我們想求出 的話就需要去知道每個 為零或不為零,但如果每一輪都將 的話將會導致運算成本過高。
在這裡將 拆解為 和 ,其中
以此類推
則在程式進行時,會由 往下查看 中有無 。
故可以看出,求出 則等於求出 的平方根為何。
版本三
確認 x 不為 0 或是其他小於 0 的數。
int m 為 ,故第一次進來迴圈時, int m = 。 因為 故 必不可能為奇數,因此要 & ~1UL
。
因為 故每次迴圈往右位移 2 。
並且每次得出 ,
且若 則減去 得 。
__builtin_clz
實作在每一次迴圈中,使用 ffs 得到 temp 中最低有效位元 var 後,將其右移 var ,一直重複此操作,最終可以得到其最高有效位元的位置。但還需要將其減 1 才會與 (31 - __builtin_clz(x))
相等。
在迴圈內使用 mask 取代原先條件句。
一般在計算商數和餘數時,我們都會直接使用 / 、 % 對其進行運算,如此造成運算成本較高的後果。
因此採用 bitwise operation 來實作除法,但可以發現當我們希望將 n 除以 10 時,無法直接使用 shift 指令完成,因為 10 並不能直接使用 的方式來表示。因此我們需要利用 n / x 來完成除以 10 的動作。
但我們應該要先證明其除以 x 後,應該在小數點後第一位時的精確度都是正確的。
故設
,確保 n 除以 x 後其跟 n 除以 10 直到小數點第一位時的精確度都是正確的。
,由於 ,故 。
而 ,故
故 , 而因為 ,故 。
故可以保證 其在小數點後第一位的精確度。
因為被除數的大小不會超過 19 ,所以我們接著直接用 19 來做討論。
故從上面式子,我們可以帶入 :
故我們只要找到一 其在此範圍內,便可保證將某數除以 時,其到小數點後第一位的精確度都會是正確的。
在這邊老師用了 這個數字來當作 x 。
故將 n 除以 ,即可取代除以 10 ,而 n 除以 同時也等同於 n * 。因此我們要想辦法用 bitwise operation 操作出 。
得出 。
往左位移 3 讓
為了避免在向右位移時導致前面 3 個位元丟失,先用 mask 的方式將位元暫存下來。
但這裡不太懂的是 d2 應該是為了避免 (tmp >> 3) 丟失的位元, d0 則是應該是為了避免 (tmp >> 1) 丟失的位元,那為什麼需要加 d1 呢?
接著再將 ,故往右位移 7 。
最後為了要算出 mod 10 ,將 tmp 減 ( div 10 的結果乘以 10 )。
最終可將程式包裝為
在這邊我們會先把 ,之後再將其減掉 ,如此我們可以得到 。
in | 1 是在 in 為偶數時,會使 in + 1 ,其用意為?
。
而 。
此處用來使 更接近 。
如果不進行逼近的話,會導致結果有錯嗎?
將 變為 。
最後為了要算出 mod 10 ,將 in 減 ( div 10 的結果乘以 10 )。
由於 (q & ~0x7) = q & ~0..0111 = q & 1..1000 。也就等於將 *div << 3 。
故為要湊出 *div 。故將 *div << 3 + *div << 1 。
ilog2 版本一是用來計算以 2 為底的對數,原先的版本為利用將二進位的數字往右位移 1 ,則表示其可以除以 2 一次,重複以上算式,直到數字被除至 0 。
但此函式的缺點為,此數字的最高 set bit 的位置在 n 處,該迴圈就應該要執行 n 次。
故將其改寫為 ilog2 版本二,
若有一數為 ,則在原本的程式中需要執行 32 次,但在改寫完的程式中只須執行 2 次。因此可省下原本需要的時間。
亦可寫為 ilog2 版本三, builtin_clz 用以得出一二進位數字其最高有效位元前,共有多少個 0 ,在利用 31 減去此數後,則可以得到其為 。而需要傳入 v | 1 則是為了避免 v 為 0 時,由於 builtin_clz 對於 0 未定義導致錯誤的情況發生。
指數加權移動平均為一種在取平均的手段,其特點為可以調整歷史資料加權降低的程度。其公式為 ,其中 表示歷史資料加權降低的程度, 表示在 時獲得的新資料, 表示在 時算出的指數加權移動平均。將以上式子展開後可得
在程式中,利用 factor 去縮放新傳進來的資料, weight 則是表示歷史資料加權降低程度。
實作出 ceil_ilog2 ,在最一開始處先將 x - 1 ,此目的為最終可以直接無條件進位,下面 r = (x > 0xFFFF) << 4;
則是若 則將 並傳給 r ,而後再讓 x 去向右位移 r ,最後是為了判斷 x 是否是一個大於 0 的數字,若 x 大於 0 則其 ceil_ilog2 必定要加一。
利用 x 減去 (x > 0) ,使當 x = 0 的情況下不會減到 1 , x 也就不會變為 0xFFFF_FFFF ,最後在原本加 1 處改為加 (原本的 x >= 1) ,讓 x 為 0 時不會加 1 。
在 popcount_naive 函式中的缺點為,如果 v 中有多少個 set bit ,則程式就需要執行多少次。故引入了 popcount_branchless 的寫法,利用 可以知道在 x[3:0] 範圍內 1 的數量。
推導為:設 ,其中 or 。
則 = 。
整理後為 。
故可以發現在 為 1 的時候 也會為 1 ,以此類推。
故可以得知確實可以利用 得知 4 bits 範圍內的 1 的 bits 數。
利用此段程式碼我們可以得到此圖。
也可以得到此算式 。
v = 32'b0100_1111_0000_0100_0111_0001_0001_1100
v = 32'b0001_0100_0000_0001_0011_0001_0001_0010
,但可以看出我們應該要將每個 nibble 的位置調整好,相加後才是 1 的總數。假設 代表第 n 個 nibble (4 位元) 中的數值
v = 32'b0001_0100_0000_0001_0011_0001_0001_0010
v = 32'b0000_0101_0000_0001_0000_0100_0000_0011
。此處的 為上面剛計算完的
v = 32'b0000_0101_0000_0001_0000_0100_0000_0011
v = 32'b0000_1101_0000_xxxx_0000_xxxx_0000_xxxx
可以看到我們所求的數字就位於 v[31:24] 處,故最後將其向右為移即可結束。
return 32'b..._0000_1101
。在與算出 hammingDistance 有關的題目中,可以利用 popcount 計算兩數有幾個不相同的值,而最後回傳回去時需要右移 1 ,是因為此處會重複運算到一次,所以需要除以 2 也就是右移 1 。
用位元的位置去看,在 x 位元時, nums 中有幾個 1 ,從此處也可以得出 0 的數量,把 1 數量乘上 0 的數量,即是當前位元位置的 Hamming Distance ,最後把所有位置的 Hamming Distance 都加總起來後即是 Total Hamming Distance 。
由於 , 故 ,而 ,若 i 為奇數,則 n mod 3 的結果會 -1 。
故 。
可以看出我們只要將 在偶數的位元數減去 在奇數的位元數即可得到 n 。
故得出此式 n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA)
。
在 tic-tac-toe
程式碼中,進行一個 3x3 大小的圈圈叉叉,由於大小為 3x3 故總操作數只會有 9 次。此時的操作為每次從陣列中選出一個可以操作的位置,選擇完後將本次選擇的位置,從陣列中移除。並將其給 board | move_masks[move]
,隨後去檢查該名玩家是否勝利。
若左邊有一條直線達成連線則 player_board = 0x44470041
。
若中間有一條直線達成連線則 player_board = 0x22207022
。
若右邊有一條直線達成連線則 player_board = 0x11100714
。
若上面有一條橫線達成連線則 player_board = 0x70044444
。
若中間有一條橫線達成連線則 player_board = 0x07022222
。
若右邊有一條橫線達成連線則 player_board = 0x00711111
。
若左上有一條斜線達成連線則 player_board = 0x42142172
。
若右上有一條橫線達成連線則 player_board = 0x12412427
。
可以看出只要 player_board 在 16 進位的表示下,只要有其中一個位元為 7 則表示勝利。
故在此段程式碼中將每個位元都加 1 ,再將每個位元都 & 8 ,如果回傳不為 0 則表示此為玩家勝利。
在 Makefile 中可以看到當執行 make check 命令時,其會去對 treeint 檔進行編譯,可以從其中看到 insert, find, remove 等操作的執行時間。而 treeint 呼叫的函式是在 treeint_xt 定義。
treeint_xt_destroy
函式中會呼叫 xtree 中的 xt_destroy
xt_root
存在時,會再進入 __xt_destroy
,使用遞迴方式將樹的左右子樹刪除,最終再刪除自己本身。treeint_xt_insert
函式中會呼叫 xtree 中的 xt_insert ,在函式中會呼叫 __xt_find
,去尋找應該 insert 至何處,如果找到此值已經在樹中了則不用新增,反之找到該新增位置後,就將節點插入進去。treeint_xt_remove
函式中會呼叫 xtree 中的 xt_remove , 在函式中會呼叫 xt_find
,但 xt_find
不同於 __xt_find
, xt_find 將不會回傳位置,其目的只是在於確認欲刪除的節點確實存在。
xt_replace_right
xt_replace_left