# 2024q1 Homework4 (quiz3+4)
contributed by < `kevinzxc1217` >
## 第三週測驗題
### 測驗 1
#### (版本一)
```c
#include <math.h>
int i_sqrt(int N)
{
int msb = (int) log2(N);
int a = 1 << msb;
int result = 0;
while (a != 0) {
if ((result + a) * (result + a) <= N)
result += a;
a >>= 1;
}
return result;
}
```
其核心概念是每個數字皆可以用 2 的冪的多項式去表達。透過對傳入的數值取對數再位移去找到一個接近 `N` 的數值 `a` ，使得 `a` 為最接近且小於 `N` 的 2 的冪，後續再透過相加和位移去逼近可能的開根號值即可。以 N 為 49 為例 :
| 迭帶次數 | a | result | (result + a) * (result + a) <= N) |result+=a|
|:-------------------------:|:-----:|:---------------:|:------------:|:------------:|
| 0 | $2^5$ | 0 | False |0|
| 1 | $2^4$ | 0 | False |0|
| 2 | $2^3$ | 0 | False |0|
| 3 | $2^2$ | 0 | True |$2^2$|
| 4 | $2^1$ | 4 | True |$2^2$+$2^1$|
| 5 | $2^0$ | 6 | True |$2^2$+$2^1$+$2^0$|
#### (版本二)
```c
int i_sqrt(int N)
{
int msb = 0;
int n = N;
while (n > 1) {
n >>= 1;
msb++;
}
int a = 1 << msb;
int result = 0;
while (a != 0) {
if ((result + a) * (result + a) <= N)
result += a;
a >>= 1;
}
return result;
}
```
此方法和 (版本一) 相近，主要是透過位移取代了 `log2()` 的函式。
#### (版本三)
```c
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 >>= 2) {
int b = z + m;
z >>= 1;
if (x >= b)
x -= b, z += m;
}
return z;
}
```
要注意的是 `__builtin_clz` 其功能為找到 x 最高位數前面有幾個 0 ， x 為 0 時，未定義。 `1UL` 是一個代表無符號長整數值1的表示方法。
以下用 x 為 36 代入 :
| 迭帶次數 | m | b=z+m | z>>=1 | (x >= b) | x-=b | z+=m|
|:-------------------------:|:-----:|:--------:|:-------:|:------------:|:------------:|:------------:|
| 0 | 16 | 16 | 0 | True | 20 |16 |
| 1 | 4 | 20 | 8 | True |0 |12 |
| 2 | 1 | 13 | 6 | False |0 | 6 |
#### ffs 取代 __builtin_clz 且提供分支和無分支的實作
> [commit - a99bd9e](https://github.com/kevinzxc1217/linux2024_hw/commit/a99bd9ebcca4a08c74a9d8987bc81a1e58e11e32)
```diff
int i_sqrt(int x)
{
if (x <= 1) /* Assume x is always positive */
return x;
+ int msb;
+ int tmp = x;
+ while(tmp){
+ tmp = tmp >> ffs(x);
+ msb += ffs(x);
+ }
int z = 0;
- for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= 2) {
+ for (int m = 1UL << (((msb - 1) & ~1UL); m; m >>= 2) {
...
}
```
由於 `__builtin_clz` 該函式其功能為找到 x 最高位數前面有幾個 0 ，而 `ffs` 函式其功能為找到 x 的首個 1 位置，透過 `while` 迴圈每次位移 `x` 首個 1 位置的量，到最後 `msb` 即可找出最高位的位置。
而原式 `(31 - __builtin_clz(x))` 表示計算最高位 - 1 的位置，可用 `msb - 1` 代替。
```diff
+ for (int m = 1UL << (((msb - 1) & ~1UL); m; m >>= 2) {
int b = z + m;
z >>= 1;
- if (x >= b)
- x -= b, z += m;
+ int mask = -(x >= b);
+ x -= b & mask;
+ z += m & mask;
}
```
這裡進行無分支的實作，即把回圈內的 `if` 替換掉。主要是將 `if` 的判斷式用 `mask` 取代，若 ` -(x >= b)` 為 TRUE 時，則 `mask` 為 111..11 ；否則為 FALSE 時， `mask` 值是 000..00 。後續在去做 and 運算，即可達到分支效果。
### 測驗 2
本測驗主要是針對正整數在相鄰敘述進行 mod 10 和 div 10 操作，減少運算成本。
當我們要進行除法運算時，若除數是 2 的冪，可以透過位移來處理，但如果不是 2 的冪，比如說 10 含有 5 這個因數，就需要使用其他方法來替代。
在這邊用了 $\dfrac{128}{13} \approx 9.85$ 來代替除數 10 ，`tmp` 代替被除數，所以 `tmp` 除以 10 相當於乘以 $\dfrac{13}{128}$ 。
```c
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 ，可以用 $(\dfrac{1}{8} + \dfrac{1}{2} + 1) * 8$ 代替，即對應程式的 ：
`((tmp >> 3) + (tmp >> 1) + tmp) << 3)`
而分母 128 可以用 $2^7$ 代替，即對應程式的 ：
`>> 7`
```diff
- unsigned d2, d1, d0, q, r;
+ unsigned q, r;
- d0 = q & 0b1;
- d1 = q & 0b11;
- d2 = q & 0b111;
- q = ((((tmp >> 3) + (tmp >> 1) + tmp) << 3) + d0 + d1 + d2) >> 7;
+ q = ((tmp >> 3) + (tmp >> 1) + tmp) >> 4;
```
其中處理分子時，由於往右位移 3 個位元會造成最右邊三個位元資訊損失，所以在往左 shift 後要將最右邊三個位元加回來。不過原程式這裡加完後續馬上又向右位移 7 ，所以加回來的 3 個位元馬上又被移走了，且加上去又位移 7 不會有進位問題，所以可以省略加上三個位元的步驟，且左移 3 可與右移 7 合併成 右移 4 ，即可求出 `q`。
```c
r = tmp - (((q << 2) + q) << 1);
```
餘數 = 被除數 - 除數 * 商，其中除數為 $10$ 。
```c
(((q << 2) + q) << 1)
```
除數 * 商 ：
$10＊q = (q*4 + q)*2$
```c
#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 >> 3);
*mod = in - ((q & ~0x7) + (*div << 1));
}
```
可以打包成以上程式碼
```c
uint32_t x = (in | 1) - (in >> 2);
```
這行程式碼為 $x = in - \dfrac{in3}{4}$ ，所以 $x = \dfrac{in3}{4}$ 。
```c
uint32_t q = (x >> 4) + x;
```
$q = \dfrac{in3}{4*16} + \dfrac{in3}{4} = \dfrac{in51}{64} \approx 0.79in$。
```c
x = q;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
```
而這邊的操作是將 $0.79in$ 逼近至 $0.8in$ ，即 $\dfrac{in8}{10}$。
```c
*div = (q >> 3);
```
$\dfrac{in8}{10}$ * $\dfrac{1}{8}$ 變為 $\dfrac{in}{10}$ ，即為原先我們所希望求的 $in$ 除以 $10$。
```c
*mod = in - ((q & ~0x7) + (*div << 1))
```
其中 `q & ~0x7` 將最低三位清零，因為 `q` 為原先 `*div` 尚未往右 shift 3 的值，所以相當於 `div` 往左 shift 3 位，即為 `*div` 的 8 倍；`*div << 1` 為商數的 2 倍。看成數學公式為：
$div*8+div*2=div*10$
即為商乘上除數。
### 測驗 3
#### (版本一)
```c
int ilog2(int i)
{
int log = -1;
while (i) {
i >>= 1;
log++;
}
return log;
}
```
不斷往右位移直到 `i` 為 0 為止，即不斷的除以 2 ，直到被除數為 0 ，此方會根據原先傳入 `i` 的最高有效位元在第幾位決定要進入迴圈幾次。
| 迭帶次數 | i | i>>1 | log++ |
|:-------------------------:|:-----:|:---------------:|:------------:|
| 0 | 0x100 | 0x10 | 2 |
| 1 | 0x10 | 0x1 | 1 |
| 2 | 0x1 | 0x0 | 0 |
這裡假設傳入的 `i` 為 4 ，即對 4 取 log ，過程如上圖所示。
#### (版本二)
```c
static size_t ilog2(size_t i)
{
size_t result = 0;
while (i >= 65536) {
result += 16;
i >>= 16;
}
while (i >= 256) {
result += 8;
i >>= 8;
}
while (i >= 16) {
result += 4;
i >>= 4;
}
while (i >= 2) {
result += 1;
i >>= 1;
}
return result;
}
```
這裡的改進主要是在於，當傳入的 `i` 值較大時，相較於版本一可以花較少的迴圈次數去處理。例如當傳入的 `i` 為 512 時，只需走進 `while (i >= 256)` 和 `while (i >= 2)` 迴圈各一次即可，尚若使用版本一需花 10 個迴圈進行處理。
#### (版本三)
```c
int ilog32(uint32_t v)
{
return (31 - __builtin_clz(v | 1));
}
```
`__builtin_clz` 為找到 x 最高位數**前面**有幾個 0 ， x 為 0 時，未定義。從前面兩個版本可以得知，如果我們要取一個數的 log ，會需要得知最高有效位元在第幾位數，透過該函式可以得知最高位數前面有幾個 0 ，可以從此反推最高有效位數在第幾位。
假設 `v` 為 10 (0x1010) ，經過 `__builtin_clz` 函式後，會回傳 28 ，最後再用 31 - 28 得到 3 即為答案。其中 `(v | 1)` 是為了避免 `__builtin_clz` 該函式傳入 x 為 0 時，未定義。
### 測驗 4
$S_t = \begin{cases}
Y_0, & t=0 \\
\alpha Y_t + (1-\alpha)\cdot S_{t-1}, & t > 0
\end{cases}$
$S_t = \alpha Y_t + (1- \alpha) \alpha Y_{t - 1} +(1- \alpha)^2 \alpha Y_{t - 2} + ... + (1 - \alpha)^i \alpha Y_{t - i} + ... + (1 - \alpha)^t \alpha Y_0$
本測驗主要是在實作指數加權平均移動 ( EWMA )。
```c
struct ewma {
unsigned long internal;
unsigned long factor;
unsigned long weight;
};
```
$\alpha$ : 表示歷史資料加權降低的程度，從展開式可得知越舊的歷史資料經過平方後加權越低，對應程式碼的 `weight` 。
$S_{t-1}$ : 表示在時間 $t-1$ 時計算出的 EWMA ，對應程式碼的 `internal` 。
$Y_{t}$ : 表示在時間 $t$ 時的資料點，對應程式碼的 `val` 。
```c
struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
avg->internal = avg->internal
? (((avg->internal << avg->weight) - avg->internal) +
(val << avg->factor)) >> avg->weight
: (val << avg->factor);
return avg;
}
```
其中這段程式與公式較不同的地方在於多了個參數 `factor` ，用來縮放資料大小。
$S_t = \begin{cases}
Y_0, & t=0 \\
\alpha Y_t + S_{t-1}-\alpha S_{t-1}, & t > 0
\end{cases}$
可以將程式看成上述公式， $S_{t-1}$ 經合併後就會和原公式一樣了。
### 測驗 5
```c
int ceil_ilog2(uint32_t x)
{
uint32_t r, shift;
x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
return (r | shift | x > 1) + 1;
}
```
其中可以注意的地方是在最後 `return` 時，有個 `+1` 的動作，這裡是為了做向上取整數。而程式前部分的 `x--` 是為了處理當傳入值可以完整取對數時，避免最後 `return` 時不用向上取整數卻多加 1 做的處理。
#### 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
> [commit - 637b1ec](https://github.com/kevinzxc1217/linux2024_hw/commit/637b1ec7a2945700ad68023b17ab49624b633a54)
```diff
int ceil_ilog2(uint32_t x)
{
uint32_t r, shift;
+ int mask = -(x==0);
+ x = (x-1) & (~mask);
- x--;
r = (x > 0xFFFF) << 4;
...
+ return (r | shift | x > 1) + 1 & (~mask);
}
```
新增 `mask` 來處理原先 `x--` 因無號數型態變更大的問題，以及處理 return 時遇到 0 的情形。
## 第四週測驗題
### 測驗 1
本測驗是在推導 `popcount` 是如何計算傳入的數值在二進位表示中含有多少個 1 ， 其主要思路如下 :
假設傳入的 `x` 二進位為 2'b0011_1011 ，即十進位 91 ，肉眼可見共有 2 + 3 個數字 1 ，由 `popcount` 的公式，可以得知在 x[3:0] 範圍內 1 的數量 :
$x - \dfrac{x}{2} - \dfrac{x}{4} - \dfrac{x}{8} = 11 - 5 - 2 - 1 = 3$
證明如下，首先一般我們做位元計算時可以將 $x$ 表示為：
$x = 2^3b_3 + 2^2b_2 + 2^1b_1 +2^0b_0$ ，其中 $b_i = 0$ or $1$ 。
則
$x - \dfrac{x}{2} - \dfrac{x}{4} - \dfrac{x}{8}$ = ($2^3b_3 + 2^2b_2 + 2^1b_1 +2^0b_0) - (2^2b_3 + 2^1b_2 + 2^0b_1) - (2^1b_3 + 2^0b_2) - 2^0b_3$ 。
分別提出 $b_3$、$b_2$、$b_1$、$b_0$ 整理後 :
$(2^3 - 2^2 - 2^1 - 2^0)b_3 + (2^2 - 2^1 - 2^0)b_2 + (2^1 - 2^0)b_1 +(2^0)b_0$
括弧內化簡後可以發現在 $b_3$ 為 1 的時候 $(2^3 - 2^2 - 2^1 - 2^0)b_3$ 也會為 1 ，以此類推。
故可以得知證明可以利用 $x - \dfrac{x}{2} - \dfrac{x}{4} - \dfrac{x}{8}$ 得知 4 位元範圍內 1 的 bits 數量。
```c
unsigned popcount_branchless(unsigned v)
{
unsigned n;
n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
v = (v + (v >> 4)) & 0x0F0F0F0F;
v *= 0x01010101;
return v >> 24;
}
```
接下來我們想要知道當 $x$ 為 32 位元時如何處理，`popcount_branchless` 實作一開始以每 4 個位元 (nibble) 為一個單位計算 1 的個數，底下我們仍然以 $x$ 為 91 (32'b0011_1011) 當例子。
```c
n = (v >> 1) & 0x77777777;
v -= n;
```
上述程式的 `(v >> 1)` 對應上方公式的 $\dfrac{x}{2}$ ，而 `v -= n` 即為 $x - \dfrac{x}{2}$ ，以此類推。其中值得注意的是 `& 0x77777777` 這段主要因為我們計算 1 的數量時，是以每 4 個位元 (nibble) 為一個單位，當 `v >> 1` 時，為了避免因為位移導致上組 nibble 的最後一個位元移到當前這組 nibble ，所以每組 nibble 經位移後都需去 &7(32'b0111) ，使得 mask 每組 nibble 的可能因位移而影響的最高位元。
```
0 0 1 1_1 0 1 1 // v
0 0 0 1_0 1 0 1 // (v >> 1) & 0x77777777
0 0 0 0_0 0 1 0 // (n >> 1) & 0x77777777
- 0 0 0 0_0 0 0 1 // (n >> 1) & 0x77777777
------------------
0 0 1 0_0 0 1 1
```
計算出的值為 `32'b0010_0011` ，以 nibble 為單位來看的話，可以發現有兩組值分別是 2 和 3 ，對應到 $x$ 的二進制表示 `32'b0011_1011` 來看，其 1 的個數在不同的 nibble 組確實也分別為 2 個 1 和 3 個 1 。由此可見，經過上述計算後我們最後僅需將計算後的所有 nibble 內的值相加即可 :
```c
v = (v + (v >> 4)) & 0x0F0F0F0F
```
將每 4 個位元中 set bit 的個數加到 byte 中。
```
B7 B6 B5 B4 B3 B2 B1 B0 // v
0 B7 B6 B5 B4 B3 B2 B1 // (v >> 4)
```
假設 $B_n$ 代表第 n 個 nibble (4 位元) 中的數值
```
B7 (B7+B6) (B6+B5) (B5+B4) (B4+B3) (B3+B2) (B2+B1) (B1+B0) // (v + (v >> 4))
```
使用剛剛計算出的結果 `v = 32'0010_0011` ，經過此式之後為 `32'0010_0101`
```c
0 (B7+B6) 0 (B5+B4) 0 (B3+B2) 0 (B1+B0) // (v + (v >> 4)) & 0x0F0F0F0F
```
最後使用 0x0F0F0F0F 做 mask 可得 `v = 32'0000_0101`
```c
v *= 0x01010101
```
在最後一道敘述中，將 v 乘上 0x01010101。寫成直式如下 :
```c
0 A6 0 A4 0 A2 0 A0
x 0 1 0 1 0 1 0 1
---------------------------------------------------
0 A6 0 A4 0 A2 0 A0
0 A6 0 A4 0 A2 0 A0 0
0 A6 0 A4 0 A2 0 A0 0
0 A6 0 A4 0 A2 0 A0 0
---------------------------------------------------
↑_______________________A6+A4+A2+A0
```
此處的 $A_i$ 為上面剛計算完的 $B_{i+1}+B_i$ ， A6+A4+A2+A0 剛好為所有 nibble 的總和。
```c
return v >> 24
```
可以看到我們所求的數字就位於 v[31:24] 處，故最後將其向右位移 24 即可得到 `32'b0000_0101` ，即為所求， 32'b0011_1011 中含有 5 個數字 1 。
### 測驗2
前面先探討了如何不使用任何除法就算出某數除以另一個數的餘數呢？
以除數為 3 為例，由於 $2^k \equiv
\begin{cases}
1(mod~3), k even \\
-1(mod~3), k odd\\
\end{cases}$ ，
若 n 的二件制表示為 $b_{n-1}b_{n-2}...b_{2}b_{1}b_{0}$，即 $n = \sum_{0}^{n-1} b_i *(2)^i$ ，
根據上述可得 $n \equiv \sum_{0}^{n-1} b_i *(-1)^i (mod~3)$ ，
即如果要計算某數 $mod~3$ ，用某數二進制表示的偶數位元的和減去奇數位元的和即可，用程式表示為：
```c
n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA)
```
其中 5 為 0101 ，而 A 為 1010 ，和 n 做 & 後， n 即可得到對應的位數。
後續來探討 [tictactoe.c](https://gist.github.com/jserv/9088f6f72a35a1fcaaf1c932399a5624) 中的部分函式：
```c
static const uint32_t move_masks[9] = {
0x40040040, 0x20004000, 0x10000404,
0x04020000, 0x02002022,0x01000200,
0x00410001, 0x00201000, 0x00100110,
};
```
`move_masks` 函式中的每項對應九宮格中各座標的位置，如 `0x40040040` 對應九宮格的左上角，`0x00410001` 對應九宮格的左下角。
```c
static inline uint32_t is_win(uint32_t player_board)
{
return (player_board + 0x11111111) & 0x88888888;
}
```
其中倘若我們想要得知 player 是否獲勝，需從棋盤中判定是否有連線。其中在程式上判斷連線的方法，是去判斷該棋盤上各個可能的橫線、直線、斜線分別所代表的座標去做加總，是否存在 `7` 這個數字。
```c
0x40040040 + 0x04020000 + 0x00410001 = 0x44470041
```
舉例來說，如果要判斷最左邊的直排是否連線，需檢查最左排的值全部相加是否滿為 `0x44470041` 。若是即為連線，判斷為獲勝，反之亦然。而在程式碼中，由於我們前面 `move_maks` 的設定，橫線、直線、斜線不管怎麼相加，在時溜進制表示式中並不會有超過 `7` 的值。
```c
0x44470041 + 0x11111111 = 0x55581152
```
於是這裡便透過此特性，將棋盤值加上 `0x11111111` 後，若本身棋盤連線則會在十六進制表示式中出現 `8` 的值，再去和 `0x88888888` 去做 `&` 運算來判斷是否存在 `8` ，即可用來作為勝利條件的判斷。
> [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)
```c
int totalHammingDistance(int* nums, int numsSize)
{
int total = 0;;
for (int i = 0;i < numsSize;i++)
for (int j = 0; j < numsSize;j++)
total += __builtin_popcount(nums[i] ^ nums[j]);
return total >> 1;
}
```
這段程式碼是用來計算給定數組中所有數字兩兩之間的漢明距離總和。漢明距離是指兩個等長字符串之間對應位置上不同字符的個數。在這裡，對於給定的整數數組 nums，兩兩之間的漢明距離總和是指每對數字的二進制表示中，對應位不同的位數之和的總和。
其中最後 `total >> 1` 是因為由於雙迴圈特性，每個數字會重複計算漢明距離總和，所以最後要除以 2 。
#### 不依賴 popcount ，撰寫出更高效的程式碼。
```c
int totalHammingDistance(int* nums, int numsSize)
{
int total = 0;
int tmp = 0;
for (int i = 0;i < 32;i++){
for (int j = 0; j < numsSize;j++){
if((nums[j] >> i) & 1){
tmp += 1;
}
}
total += tmp * (numsSize - tmp);
tmp = 0;
}
return total;
}
```
所有 Number 中從第 0 個 bit 開始計算全部該 bit 的 Hamming Distance ，在全部累加起來就是 Total Hamming Distance 。將第一層迴圈的參數 `i` 用來當作走到幾個 bit ，第二層迴圈的參數 `j` 當作數組內第幾個數字，每次走完一個數組後，就再往下個 bit 去看。
判斷各個 bit 的 Hamming Distance：
Hamming Distance = (各個 bit 數組內 1 的數量) * (numsize - 各個 bit 數組內 1 的數量) 。
### 測驗3
本測驗主要是參考 [XTree](https://gist.github.com/jserv/7374b3e031ec3a81441b1b93b008c5d2) 去做分析與探討。
**xt_remove**
```c
static void __xt_remove(struct xt_node **root, struct xt_node *del)
{
if (xt_right(del)) {
struct xt_node *least = xt_first(xt_right(del));
if (del == *root)
*root = least;
xt_replace_right(del, least);
xt_update(root, xt_right(least));
return;
}
...
}
```
其中這段程式碼主要是在說明 XTree 在 `remove` 元素時，會根據以下定律：
- 當刪除一個節點時，若該節點有右子節點，則將要移除的節點替換為右子樹中遇到的第一個節點，並對新插入節點的右子節點進行更新。
- 如果要刪除的節點沒有右子節點，則替換左子樹中找到的最後一個節點，並對新插入節點的左子節點進行更新。
- 在節點要刪除的情況下沒有子節點的情況下，可以直接從樹中刪除該節點，並對刪除節點的父節點進行更新。
**xt_balance()**
計算 `n` 的左右子數 hint 值差為多少，即計算左右子數相差多少 level 。
**xt_update()**
透過 `xt_balance` 函式計算 `n` 元素的 `hint` 值，若小於負一則進行 `xt_rotate_right` ，若大於一則進行 `xt_rotate_left` 。
**xt_find()**
該函式進行一般我們常看到的二元搜尋法，透過比較當前元素值和欲找元素的大小來進行二元搜尋。
**xt_rotate_right**
```graphviz
digraph structs {
node[shape=circle];
struct0 [label= "p"];
struct1 [label= "n"];
struct3 [label= "r"];
struct5 [label= "rr"];
node[shape=rarrow];
struct6 [label= ""];
node[shape=circle];
struct7 [label= "p"];
struct11 [label= "n"];
struct8 [label= "rr"];
struct9 [label= "r"];
struct0 -> struct1;
struct1 -> struct3;
struct3 -> struct5;
struct7 -> struct9;
struct9 -> struct8;
struct9 -> struct11;
}
```
**xt_rotate_left**
```graphviz
digraph structs {
node[shape=circle];
struct0 [label= "p"];
struct1 [label= "n"];
struct2 [label= "l"];
struct4 [label= "ll"];
node[shape=rarrow];
struct6 [label= ""];
node[shape=circle];
struct7 [label= "p"];
struct11 [label= "ll"];
struct8 [label= "n"];
struct9 [label= "l"];
struct0 -> struct1;
struct1 -> struct2;
struct2 -> struct4;
struct7 -> struct9;
struct9 -> struct8;
struct9 -> struct11;
}
```
Sign in with Wallet
Connect another wallet