Изменения
Битовые операции в tex
Пусть <tex>\left \{ a_1,a_2\ldots a_k\right \}</tex> {{---}} множество ключей узла, отсортированных по возрастанию, <tex>q</tex> {{---}} ключ искомой вершины, <tex>l</tex> {{---}} количество бит в <tex>sketch(q)</tex>. Сначала найдем такой ключ <tex>a_i</tex>, что <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>. Но положение <tex>sketch(q)</tex> среди <tex>sketch(a_j)</tex> не всегда эквивалентно положению <tex>q</tex> среди <tex>a_j</tex>, поэтому, зная соседние элементы <tex>sketch(q)</tex>, найдем <tex>succ(q)</tex> и <tex>pred(q)</tex>.
===Параллельное сравнение===
Найдем <tex>succ(sketch(q))</tex> и <tex>pred(sketch(q))</tex>. Определим <tex>sketch(node)</tex> как число, составленное из единиц и <tex>sketch(a_i)</tex>, то есть <tex>sketch(node) = 1sketch(a_1)1sketch(a_2)\ldots 1sketch(a_k)</tex>. Вычтем из <tex>sketch(node)</tex> число <tex>sketch(q) \times \underbrace{\overbrace{00\ldots 1}^{l + 1 bits}\overbrace{00\ldots 1}^{l + 1 bits}\ldots \overbrace{00\ldots 1}^{l + 1 bits}}_{k(l + 1) bits} = 0sketch(q)\ldots 0sketch(q)</tex>. В начале каждого блока, где <tex>sketch(a_i) \geqslant sketch(q)</tex>, сохранятся единицы. Применим к получившемуся побитовое ''AND'' <tex>\land</tex> c <tex>\displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}</tex>, чтобы убрать лишние биты.
<tex>L = (1sketch(a_1)\ldots 1sketch(a_k) - 0sketch(q)\ldots 0sketch(q))</tex> ''AND'' <tex>\land \displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}=\overbrace{c_10\ldots0}^{l+1 bits} \ldots \overbrace{c_k0\ldots0}^{l+1 bits}</tex>
Если <tex>sketch(a_i)< sketch(q)</tex>, то <tex>c_i = 0</tex>, в противном случае <tex>c_i = 1</tex>.
* если <tex>q<a_j</tex> {{---}} найдем <tex>succ(e)</tex>, <tex>e = p10\ldots 00</tex>. Это будет <tex>succ(q)</tex>.
Длина наибольшего общего префикса двух ''w''-битных чисел <tex>a</tex> и <tex>b</tex> может быть вычислена с помощью нахождения индекса наиболее значащего бита в побитовом ''XOR'' \oplus <tex>a</tex> и <tex>b</tex>.
==Вычисление sketch(x)==
Чтобы найти sketch за константное время, будем вычислять <tex>sketch(x)</tex>, имеющий все существенные биты в нужном порядке, но содержащий лишние нули.
1) уберем все несущественные биты <tex>x' = x</tex> ''AND'' <tex>\land</tex> <tex>\displaystyle \sum_{i=0}^{r-1}2^{b_i}</tex>;
2) умножением на некоторое заранее вычисленное число <tex>M = \displaystyle\sum_{i=0}^{r-1}2^{m_i}</tex> сместим все существенные биты в блок меньшего размера.
<tex>x'\times M = \displaystyle(\sum_{i=0}^{r-1}x_{b_i}2^{b_i})(\sum_{i=0}^{r-1}2^{m_i}) = \sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j}</tex>;
3) применив побитовое ''AND''<tex>\land</tex>, уберем лишние биты, появившиеся в результате умножения;
<tex>\displaystyle\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j}</tex> ''AND'' <tex>\land</tex> <tex>\displaystyle\sum_{i=0}^{r-1}2^{b_i+m_i} = \sum_{i=0}^{r-1}x_{b_i}2^{b_i+m_i}</tex>;
4) сделаем сдвиг вправо на <tex>m_0 + b_0</tex> бит.
'''1)''' Поиск непустых блоков.
'''a.''' Определим, какие блоки имеют единицу в первом бите. Применим побитовое ''AND'' <tex>\land</tex> к <tex>x</tex> и константе <tex>F</tex>.
<tex>$$
\begin{array}{r}
\begin{array}{r}
x = 0101\; 0000\; 1000\; 1101\\
$$
\begin{array}{r}
\begin{array}{r}
t_1 = 0000\; 0000\; 1000\; 1000\\
$$
\begin{array}{r}
\begin{array}{r}
F = 1000\; 1000\; 1000\; 1000\\
'''c.''' Первый бит в каждом блоке <tex>y = t_1</tex> ''OR'' <tex>\lor t_4</tex> содержит единицу, если соответствующий блок <tex>x</tex> ненулевой.
<tex>$$
\begin{array}{r}
\begin{array}{r}
t_1 = \underline{0}000\; \underline{0}000\; \underline{1}000\; \underline{1}000\\
