2024q1 Homework4 (quiz3+4)

contributed by <marvin0102>

第一周測驗

測驗 1: 計算開平方根

假設我們要求

$x$ 的平方根，將

$x$ 轉為二進位後，可以將

$x$ 拆成 2 的冪相加:

$x=(000b_0{b}_1{b}_2...b_{n-1}{b}_n{)}^2$

其中

$000b_0{b}_1{b}_2...b_{n-1}{b}_n$ 為 bits pattern，而

$b_0$ 為最高位的 1 。

設

$a_0=000...b_n$ 、

$a_1=000...b_{n-1}0$ …

$a_1=000...b_{n-2}00$ ，因此可以將

$x$ 拆成：

$x=N^2=(a_n+a_{n-1}+a_{n-2}+...+a_0{)}^2$ ,

$a_m=2^m$ or

$a_m=0$

使用矩陣乘法可得

$$\left[\begin{array}{ccccc}{a}_0{a}_0& a_1{a}_0& a_2{a}_0& ...& a_n{a}_0\\ a_0{a}_1& a_1{a}_1& a_2{a}_1& ...& a_n{a}_1\\ a_0{a}_2& a_1{a}_2& a_2{a}_2& ...& a_n{a}_2\\ ...\\ a_0{a}_n& a_1{a}_n& a_2{a}_n& ...& a_n{a}_n\end{array}\right]$$

可以將這個矩陣拆為：

$$\left[\begin{array}{ccccc}{a}_0{a}_0& a_1{a}_0& a_2{a}_0& ...& a_n{a}_0\\ a_0{a}_1& & & & \\ a_0{a}_2& & & & \\ ...\\ a_0{a}_n& & & & \end{array}\right]$$

$$\left[\begin{array}{cccc}{a}_1{a}_1& a_1{a}_2& ...& a_n{a}_0\\ a_1{a}_1& & & \\ a_1{a}_2& & & \\ ...\\ a_1{a}_n& & & \end{array}\right]$$

至最後一向

$$\left[\begin{array}{c}{a}_n{a}_n\end{array}\right]$$

將這些矩陣結合可以整理成以下公式

$$\begin{array}{rl}{N}^2& =a_n^2+[2a_n+an-1]a_{n-1}+[2(a_n+a_{n-1})+a_{n-2}]a_{n-2}+...+[2(\sum _{i=1}^n{a}_i)+a_0]a_0\\ & =a_n^2+[2P_n+an-1]a_{n-1}+[2P_{n-1}+a_{n-2}]a_{n-2}+...+[2P_0+a_0]a_0\end{array}$$
其中

$P_m=a_n+a_{n-1}+...+a_m$
而所求

$N=P_0$ 即為所求。

可以知道

$P_m=a_n+a_{n-1}+...+a_m=(a_n+a_{n-1}+...+a_{m+1})+a_m=P_{m+1}+a_m$

經由測試

$P_m^2\le N^2$ 判斷

$a_m=2^m$ or

$a_m=0$

$$\{\begin{array}{ll}{P}_m=P_{m+1}+2^m,& \text{if }{P}_m^2\le N^2\\ P_m=P_{m+1},& \text{otherwise}\end{array}$$

$m=0$ 時，

$P_m$ 即為所求

可以透過上一輪的差值計算比較

$P_m^2\le N^2$ ，設

$X_m=N^2-P_m^2$ 為

$P_m^2$ 、

$N^2$ 的差值，可以由上一輪的差值

$X_{m+1}$ 減去

$Y_m$ 而得，

$Y_m$ 的計算如下：

• $X_m=N^2-P_m^2=X_{m+1}-Y_m$
• $Y_m=N^2-P_{m+1}^2-(N^2-P_m^2)=P_m^2-P_{m+1}^2=2P_{m+1}{a}_m+a_m^2$

因此，可以由上一輪的

$P_{m+1}$ 計算

$Y_m$
將

$Y_m$ 拆成

$c_m,d_m$，可得

$$Y_m=\{\begin{array}{ll}{c}_m+d_m,& \text{if }{a}_m=2^m\\ 0,& \text{if }{a}_m=0\end{array}$$
其中

$c_m=P_{m+1}{2}^{m+1}$ 、

$d_m=(2^m{)}^2$

接著嘗試通過

$c_m$ 、

$d_m$ 推論下一輪的

$c_{m-1}$ 、

$d_{m-1}$:

• $$c_{m-1}=P_m{2}^m=(P_{m+1}+a_m)2^m=P_{m+1}{2}^m+a_m{2}^m=\{\begin{array}{ll}{c}_m/2+d_m,& \text{if }{a}_m=2^m\\ c_m/2,& \text{if }{a}_m=0\end{array}$$
• $d_{m-1}=(2^{m-1}{)}^2=\frac{d_m}{4}$

接下來就可以游上往下尋找

$a_n+a_{n-1}+...+a_0$，設從

$a_n$ 開始往下尋找：

• 因為
  $n$ 為最大位數，因此
  $P_{n+1}=0$ ，
  $c_n=P_{n+1}{2}^{n+1}=0$
• $d_n=(2^n{)}^2=4^n$

因為

$d_m$ 最小為 1 ，但是座位移操作最後必為 0 ，因此我們可以將

$d!=0$ 作為搜尋的判斷式。

從原始碼來解析：

int i_sqrt(int x)
{
    if (x <= 1) /* Assume x is always positive */
        return x;

    int z = 0;
    for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= AAAA) {
        int b = z + m;
        z >>= BBBB;
        if (x >= b)
            x -= b, z += m;               
    }
    return z;
}

因為無法計算虛數，因此須先將

$x$ 為負數的情況排除。

從 1UL << ((31 - __builtin_clz(x)) & ~1UL) 的作用為計算

$x$ 中最大 2 的冪為多少，也就是

$x=N^2=(2^n+2^{n-1}+...+1{)}^2$ 中

$(2^n{)}^2$ ，因此我們可以知道 m 為

$b_n=4^n$。

又由上面的公式，

$d_{m-1}=(2^{m-1}{)}^2=\frac{d_m}{4}$ 可知，每一輪迴圈 m 須除 4 ，也就是右移 2 bits ，因此 AAAA 為 2 。

從 return z; 及 z 的起始值為 0 可推得， z 即為

$c_n$，且 b 為

$Y_n$，又因為 z 每次累加

$(2^n{)}^2$，因此需要每次迴圈除 2 ，使 z 變為

$P_n$，因此 BBBB 為 1。

Linux 平方根運算應用案例：

在 block/blk-wbt.c 中尋找到函式 rwb_arm_timer 使用 int_sqrt 的應用案例。
int_sqrt 被定義於 lib/math/int_sqrt.c 中，用於計算整數的平方根。

從註解可以了解

 * buffered writeback throttling. loosely based on CoDel. We can't drop
 * packets for IO scheduling, so the logic is something like this:
 * - Monitor latencies in a defined window of time.
 * - If the minimum latency in the above window exceeds some target, increment
 *   scaling step and scale down queue depth by a factor of 2x. The monitoring
 *   window is then shrunk to 100 / sqrt(scaling step + 1).

如果上述 window 中的最小延遲超過某個目標值，則增加 scaling step ，並將佇列深度縮小 factor 的 2 倍。然後，monitoring window 縮小為 100 / sqrt(縮放步驟 + 1)。
具體程式碼：

rwb->cur_win_nsec = div_u64(rwb->win_nsec << 4,
					int_sqrt((rqd->scale_step + 1) << 8));

實作更快的程式碼：

TODO

測驗 2: 計算除法

不使用 / 與 % 求一數字除以 10 的商跟餘數，相當於乘

$\frac{1}{10}$，但因為 10 不能以 2 的冪表示，因此需要找近似值

$\frac{a}{2^N}$ 使近似於

$\frac{1}{10}$ ，當

$2^N=128$ 、

$a=13$ 時，

$\frac{128}{13}\approx 9.84$ 與 10 很接近

unsigned d2, d1, d0, q, r;

d0 = q & 0b1;
d1 = q & 0b11;
d2 = q & 0b111;
q = ((((tmp >> 3) + (tmp >> 1) + tmp) << 3) + d0 + d1 + d2) >> 7;
r = tmp - (((q << 2) + q) << 1);

因為

$13=8+4+1$ 因此我們可以透過 (((tmp >> 3) + (tmp >> 1) + tmp) << 3) 計算

$x\ast 13$ ，因為右移時，會遺失最低位的 3 個位元，因此須利用 + d0 + d1 + d2，紀錄並將其加回。
在我們得到

$x\ast 13$ 後，在除以 128 即為我們所求的商，也就是 >> 7。

而餘數可以利用公式，

$f-g\times Q=r$ 得到，r = tmp - (((q << 2) + q) << 1);。

完整程式碼為：

#include <stdint.h>
#include <stdio.h>

int main()
{
    for (int n = 0; n <= 19; n++) {
        unsigned d2, d1, d0, q, r;
        d0 = q & 0b1;
        d1 = q & 0b11;
        d2 = q & 0b111;
        q = ((((n >> 3) + (n >> 1) + n) << 3) + d0 + d1 + d2) >> 7;
        r = n - (((q << 2) + q) << 1);
        printf("q: %d r: %d\n",  q, r);
    }
    
    return 0;
}

可包裝為以下函式:

#include <stdint.h>
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
    uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
    uint32_t q = (x >> 4) + x;
    x = q;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;

    *div = (q >> CCCC);
    *mod = in - ((q & ~0x7) + (*div << DDDD));   
}

起初在觀察程式時，並沒有理解到兩程式之間的關聯性，在閱讀 Hacker's Delight 時，發現兩程式都是用近似值計算除以 10 的結果。
x = (in | 1) - (in >> 2) 計算

$x=in-\frac{1}{4}in=\frac{3}{4}in$ ，q = (x >> 4) + x 可以得

$q=\frac{x}{16}+x=\frac{3}{64}in+\frac{3}{4}in=\frac{51}{64}in\approx 0.79in$ 近似 0.8，有此可知 *div = (q >> CCCC) 須將 q 除以 8 才可得 in/10 ，因此 CCCC 為 3。

    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;

而四次位移是為了縮小誤差。

而餘數的計算同樣是將 in - div*10 而得，(q & ~0x7)保留除了最後三位元以外的其他位元，能等同於 div<<3，因為 10 = 0b1010，我們已經取得了div<<3，引此 (*div << DDDD) 為 (*div << 1)。

測驗 3:

當我們計算以 2 為第底數的對數時，我們可以計算一數的 leading set bit (從 most significant bit 開始計算）得到對數的近似值，例如：

log(128) = log(0b1000 0000) = 7 // first set bit of 128 is 8
log(160) = log(0b1010 0000) = 7.321 // first set bit of 160 is 8

我們可以使用類似二元搜尋樹的方式加快 leading set bit 的搜索，方法如下：

static size_t ilog2(size_t i)
{
    size_t result = 0;
    while (i >= AAAA) {
        result += 16;
        i >>= 16;
    }
    while (i >= BBBB) {
        result += 8;
        i >>= 8;
    }
    while (i >= CCCC) {
        result += 4;
        i >>= 4;
    }
    while (i >= 2) {
        result += 1;
        i >>= 1;
    }
    return result;
}

從第一個迴圈中i >>= 16 可知，此迴圈一次檢查 16 位元，如果 i 的 leading set bit 大於 16 位時，可以直接將 i 右移 16 位元，因此 AAAA 為 0xffff。
後面的迴圈同樣分別檢查 8 、 4 、 1 位元，因此 BBBB 、 CCCC 分別為 0xff 與 0xf。

可以利用 GNU extension __builtin_clz 來改寫使得程式更精簡：

int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(DDDD));
}

從 GCC online documentation 的敘述：
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_clz 返回從 most significant bit （32 or 64) 開始計算，到碰的第一個 set bit 為止， 0 的數量。
其中，前綴的 __builtin_ 代表此函式為 GCC 的 built-in 函式，

因此，ilog32(n) 就是先使用 __builtin_clz(n) 計算 leading bits 的數量，再用 31 減掉，就可以得到從 most significant bit 數來第一個 set bit 的位置。

Linux log2 的應用案例:

在 include/linux/log2.h 中定義了 log2 相關的聚集 ilog，其中包含了函式 __ilog2_u64 及 __ilog2_u32 ，使ilog2 可以計算變數大小為 64 或 32 位元的對數值。

Linux/block 負責磁碟管理，其中block/blk-zoned.c 使用 ilog2 計算 zone 的個數。

unsigned int bdev_nr_zones(struct block_device *bdev)
{
	sector_t zone_sectors = bdev_zone_sectors(bdev);

	if (!bdev_is_zoned(bdev))
		return 0;
	return (bdev_nr_sectors(bdev) + zone_sectors - 1) >>
		ilog2(zone_sectors);
}

測驗 ４:

從函式　ewma_init 中， avg->factor 為 factor 的對數，且函式 ewma_read 中，返回值為 avg->internal >> avg->factor 可以知道，再做 ewma 計算時，會以

$internal=factor\ast avg$ 做計算，當讀取數值時，須先將

$internal÷faxtor$ 才會得到正確的值。

在此前提下，分析函式 ewma_add ：

struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
    avg->internal = avg->internal
                        ? (((avg->internal << EEEE) - avg->internal) +
                           (val << FFFF)) >> avg->weight
                        : (val << avg->factor);
    return avg;
}

對照 EWMA 的數學定義：

$$S_t=\{\begin{array}{ll}{Y}_0& t=0\\ \alpha Y_t+(1-\alpha )S_{t-1}& t>0\end{array}$$
當加入第一筆資料時

$S_0=Y_0$ 對應到 avg->internal = (val << avg->factor) 符合觀察。因此，

$S_t=\alpha Y_t+(1-\alpha )S_{t-1}$ 在程式內乘上

$factor$ 後，
變為

$internal=weight\ast (factor\ast val)+(1-weight)\ast internal$，但在函式中卻用了
>> avg->weight ，在觀察程式後發現，將

$\alpha =\frac{1}{2^{avg->weight}}$ 帶入公式計算可以發現，原本的公式變為

$S_t=\frac{1}{2^{avg->weight}}{Y}_t+(1-\frac{1}{2^{avg->weight}})S_{t-1}$ ，
同乘

$2^{avg->weight}$ 後

$2^{avg->weight}{S}_t=Y_t+(2^{avg->weight}-1)S_{t-1}$ 與 ((avg->internal << avg->weight) - avg->internal) + (val << avg->factor) 相符，因此最後計算的結果須除

$2^{avg->weight}$ 才會得到正確的結果。

Linux EWMA 的相關程式碼與應用案例：

include/linux/average.h 定義了 EWMA 的巨集 DECLARE_EWMA ，其中可以使用巨集引數 name 自行定義 EWMA 相關函式名稱，分別有 ewma_##name##_init 、 ewma_##name##_read 、 ewma_##name##_add 三個函式與結構體 ewma_##name。
DECLARE_EWMA 引數中 _precision 為定點數得 fraction bit 個數，而 EWMA 數學定義中的

$\alpha$ 則是以 1/_weight_rcp 的形式定義。

在 drivers/net/wireless/ath/ath11k/core.h 中，使用了 DECLARE_EWMA(avg_rssi, 10, 8) 定義了結構體 ewma_avg_rssi ，並且用 ath11k_sta 包裝。

在 drivers/net/wireless/ath/ath11k/mac.c 中函式 ath11k_mac_station_add 初始化，確切的作用仍在理解中。

測驗 5：

函式 ceil_ilog2 的作用為計算以2為底數的對數並且向上取整，實作方法與測驗 3 類似，通過二元搜尋的方式找出從 msb開始計算的 leading set bit 的位置。

r = (x > 0xFFFF) << 4;
x >>= r;

r 為記錄leading set bit 的位置，當 x > 0xFFFF 成立時， r 為

$2^4$ ，代表 leading set bit 大於 16 位元，而 x >>= r 則是將 x 右移 16 位元再做後續的比較，若 x > 0xFFFF 不成立時，則 r = 0 且 x 無位移。

shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;

在檢驗完 16 位元後，接續檢驗 8 位元，而 r |= shift 則是將兩次檢驗的位元結果相加。

再分別檢驗完 16 、 8 、 4 、 2 位元後，接著將這些檢驗結果與 (x>1) 相加即為從 msb開始計算的 leading set bit 的位置。

而因為結果需要向上取整，因此最後的結果需要加 1 ，如果 x 為

$2^n$ 則結果就會錯誤，因此在函示一開始需加上 x-- 以避免此情況。

改進程式碼

在原本的函示中，因為 x-- 在 x 為 0 時，會將 x 變為負數進而無法計算，因此只要將程式碼改為：

- x--;
+ x -= !(!x);

第二周測驗

測驗 1:

因為需要計算陣列 nums 中任兩個元素的 Hamming distance ，因此需要兩個迴圈將陣列 nums 中的元素相互比對並且透過 __builtin_popcount(nums[i] ^ nums[j] 計算 Hamming distance ，但因為兩層迴圈都是從頭開始走訪陣列 nums 因此會有重複計算的問題，例如：當 i=0 時， nums[i] ^ nums[j] 會計算 j=1,2,…,n， 而 i=1 時，會計算 j=0,2,…,n ， 其中 nums[0] ^ nums[1] nums[1] ^ nums[0]重複計算了，因此當計算完成時， total 為兩倍的 Hamming distance ，在最後還須除 2 ，也就是 total>>1。

觀察每個 bit 的 Hamming distance ：

n'th bit	4	3	2	1	0
input 7	0	0	1	1	1
input 5	0	0	1	0	1
input 10	0	1	0	1	0
input 17	1	0	0	0	1

每個 bit 的 Hamming distance 為陣列中取兩個元素，滿足兩元素中該 bit 為 [0,1] 或 [1,0] 的組合數量。例如：

1. 第 0 個 bit 觀察 :
   只有 10 的第 0 個 bit 為 0 -> Hamming Distance = (1)*(numsize - 1)
2. 第 1 個 bit 觀察 :
   有兩個 bit 為 0 -> Hamming Distance = (2)*(numsize - 2)

因此，我們可以統整所有元素中每個 bit 為 1 的數量，並計算每個 bit 的 Hamming distance ，最後再加總起來就是 total Hamming distance。
程式碼如下：

int totalHammingDistance(int* nums, int numsSize)
{
    int total = 0;
    for (int i = 0;i < 32;i++)
        int count = 0;
        for (int j = 0; j < numsSize;j++)
             if(nums[j] & (1<<i)){
                 count++;
             } 
        total += count*(numsSize-count);
    return total;
}

測驗 2:

觀察陣列 move_masks ，因為井字遊戲最多只有 9 個可能的選擇，因此可以知道 move_masks 中每一個元素代表井字遊戲的其中一個位置。將九宮格內的直線、橫線與斜線個數相加剛好為 8 條連線，又每條連線為九宮格中的三格連線所形成。

觀察元素內的數值可以發現，相比於直接將座標進行編號， move_masks 的做法是將九宮格中的連線做編號，每 4 個 bits 紀錄一條連線，則 uint32_t 恰好可以記錄 8 條連線。
在紀錄著一條連線的 4 bits 中，每位元代表連線中的其中一個格子，當遊戲的其中一方勝利時，代表 8 條連線中，有至少一條連線的三個格子被遊戲中的一方填滿，此時紀錄著這條連線的 4 bits 為 0111 即 0x7。

static inline uint32_t is_win(uint32_t player_board)
{
    return (player_board + 0x11111111) & 0x88888888;
}

這時只要將記錄著遊戲狀態的變數 player_board 加 0x11111111 即每 4 bits 加 1 ，並觀察是否有其中 4 bits 進位為 1000 即 0x8 就可知道是否達成勝利條件。

井字遊戲中，每一個格在都會影響到不只一條連線，因此 move_masks 的每個元素 set bit 個數至少為三以上，且每 4 bits 只會有一個 set bit。

觀察遊戲的整體流程， boards 負責記錄玩家的遊戲狀態，available_moves 代表目前可以下棋的位置，一開始皆為 9 個，而決定下棋位置方式為，透過 xorshift32() 隨機生成一數字，除 n_moves 並使用函式 fastmod 取餘數，最後取得的數值 i ， available_moves[i] 即為下棋的位置。

因此我們知道函式 fastmod 中的 mod7 為取 7 的餘數， Hacker's Delight 中，函式 rems7 透過

$8^k\equiv 1(mod7)$ 快速計算

$mod7$ 具體程式如下：

int remu7(int n) {
    int r;
    static char table[75] =   {5,6, 0,1,2,3,4,5,6,
     0,1,2,3,4,5,6, 0,1,2,3,4,5,6, 0,1,2,3,4,5,6,
     0,1,2,3,4,5,6, 0,1,2,3,4,5,6, 0,1,2,3,4,5,6,
     0,1,2,3,4,5,6, 0,1,2,3,4,5,6, 0,1,2,3,4,5,6, 0,1,2};
     
    r = (n >> 15) + (n & 0x7FFF); // FFFF0000 to 17FFE. 
    r = (r >> 9) + (r & 0x001FF); // FFFFFF80 to 2BD. 
    r = (r>> 6)+(r&0x0003F); //-2to72(decimal). 
    return table[r];
}

因為

$2^{15}\equiv 1(mod7)$ ，所以我們可以將 n 右移 15 位元並且跟 n 從 lsb 開始計算 15 位元相加，其值取餘數後，與 n 取餘數的值相同。後面的 (r >> 9) 、 (r>> 6) 也是相同的原理。

Hacker's Delight 中提另一種取餘數的方法，利用

$n\mathrm{mod}7=\lfloor \frac{8}{7}n\rfloor \mathrm{mod}8$ 的方法取餘數：

int remu7(unsigned n) {
   n = (0x24924924*n + (n >> 1) + (n >> 4)) >> 29;
   return n & ((int)(n - 7) >> 31);
}

透過將

$n\ast \lfloor \frac{2^{32}}{7}\rfloor$ 之後再往右移 29 位元，即可在省去高為元的同時，取得我們想要的答案。

而井字遊戲中的函式 mod7 則是結合兩者：

1. 使用 x = (x >> 15) + (x & UINT32_C(0x7FFF));縮小為數的計算。
2. 因為誤差的關係，採用
   $n\ast \lceil \frac{2^{32}}{7}\rceil$ 也就是 ((x * UINT32_C(0x24924925)) >> 29) 取得餘數。

測驗 3:

treeint.c 為一個測試程式，分別測試 BST 的插入、搜尋與刪除所花的時間，實作方法為使用結構體 treeint_ops 以函式指標的方式將 treeint_xt.[ch] 所提供的函式製作程 function hook ，並透過 ops 進行函式呼叫。其中，xtree.[ch] 負責處理 xtree 的平衡、新增與刪除，由資料型別 xt_node 作為樹的節點相連接。而 treeint_xt.[ch] 將 xtree.c 中的函式包裝成符合程式所需的資料型別 ，也就是定義了 entry 的資料型別 treeint_st 與比較函式 treeint_xt_cmp 。

treeint_xt.[ch] 提供的 5 個函式，分別透過呼叫 xtree.[ch] 中對應的函式完成對 BST 的操作。而 xtree.[ch] 提供了以下函式：

• struct xt_tree *xt_create(cmp_t *cmp, struct xt_node *(*create_node)(void *key), void (*destroy_node)(struct xt_node *n)):
  作用為初始化 xtree ，並且定義了搜尋、建構或移除節點時所需的函式。
• void xt_destroy(struct xt_tree *tree):
  呼叫函式 __xt_destroy 使用遞迴得方式移除整棵樹。
• int xt_insert(struct xt_tree *tree, void *key):
  透過函式 __xt_find 尋找 key 在 xtree 中插入的位置，並呼叫 __xt_insert 將新節點插入 xtree 中。
• int xt_remove(struct xt_tree *tree, void *key):
  與 xt_insert 相似，透過函式 __xt_find 尋找 key 在 xtree 中的位置，呼叫 __xt_remove 將節點從 xtree 中移除。
• struct xt_node *xt_find(struct xt_tree *tree, void *key):
  透過呼叫 __xt_find2 以遞迴的方式尋找 key 在 xtree 中的位置並回傳節點指標。

xtree 與 AVL tree 、 Red Black tree 相似，三者皆為自平衡樹， xtree 的平衡機制是利用 hint 來評估是否需要做 rotate， xt_node 的 hint 的計算方式是，其左右節點 hint 最大值 +1 並且只有在被呼叫到 xt_update 時才會被更新。

其中：

• xt_update:
  透過呼叫 xt_balance 判斷左右子節點 hint 的差值是否超過 1 ，如果是則 rotate 進行平衡，接著檢查 hint 在平衡後是否改變，如果是則往上對親節點進行平衡。
• xt_rotate_right:
  將節點向右旋轉以平衡 xtree

• xt_rotate_left:
  將節點向左旋轉以平衡 xtree

改進程式：

TODO