234
правки
Изменения
→Индекс наиболее значащего бита
==Индекс наиболее значащего бита==
Чтобы найти в w-битном числе ''<tex>x'' </tex> индекс самого старшего бита, содержащего еденицу, разделим ''<tex>x'' </tex> на <tex>\sqrt{w}</tex> блоков по <tex>\sqrt{w}</tex> бит.<tex>x = \underbrace{0101}_{\sqrt{w}}\; \underbrace{0000}_{\sqrt{w}}\; \underbrace{1000}_{\sqrt{w}}\; \underbrace{1101}_{\sqrt{w}}</tex>. Далее найдем первый непустой блок и индекс первого еденичного бита в нем.
'''1)''' Поиск непустых блоков.
'''a. ''' Определим , какие блоки имеют еденицу в первом бите. Применим побитовое ''AND к ''к <tex>x'' </tex> и константой ''константе <tex>F''</tex>.
<tex> $$
\begin{array}{r}
AND
\begin{array}{r}
x = 0101\; 0000\; 1000\; 1101\\
F = 1000\; 1000\; 1000\; 1000\\\end{array} \\\hline\begin{array}{r}t_1 = \underline{0}000\; \underline{0}000\; \underline{1}000\; \underline{1}000\end{array}\end{array}
$$</tex>
'''b.''' Определим, содержат ли остальные биты еденицы. Вычислим <tex>x\; </tex> ''XOR \; '' <tex>t_1</tex>.
<tex>
\end{array}
$$</tex>
Вычтем от <tex>F\; t_2</tex>. Если какой-нибудь бит <tex>F</tex> обнулится, значит, соответствующий блок содержит еденицы.
<tex>
$$</tex>
Чтобы найти блоки, содержащие еденицы, вычислим <tex>t_3\; </tex> ''XOR \; '' <tex>F</tex>.
<tex>
$$</tex>
'''c. ''' Первый бит в каждом блоке <tex>y = t_1\; </tex> ''OR \;'' <tex>t_4</tex> содержит еденицу, если соответствующий блок ''<tex>x'' </tex> ненулевой.
<tex>$$
$$</tex>
'''2)''' Найдем <tex>sketch(y)</tex>, чтобы сместить все нужные биты в один блок. Существенными битами в данном случае будут первые биты каждого блока, поэтому <tex>b_i = \sqrt{w} - 1 + i\sqrt{w}</tex>. Будем использовать <tex>m_j = w - (\sqrt{w}-1) - j\sqrt{w} +j</tex>. Тогда <tex>b_i + m_j = w + (i - j)\sqrt{w} + j</tex>. Все суммы различны при <tex>0\leqslant i, j < \sqrt{w} </tex>. Все <tex>b_i + m_i = w + i</tex> возрастают, и <tex>(b_{\sqrt{w} - 1} + m_{\sqrt{w} - 1}) - (b_0 + m_0) = \sqrt{w} - 1</tex>. Чтобы найти <tex>sketch(y)</tex>, умножим <tex>y </tex> на <tex>m </tex> и сдвинем вправо на <tex>w </tex> бит.
'''3)''' Найдем первый ненулевой блок. Для этого надо найти первую еденицу в <tex>sketch(y)</tex>. Как и при поиске <tex>succ(sketch(q)) </tex> и <tex>pred(sketch(q)) </tex> используем параллельное сравнение <tex>sketch(y) </tex> с <tex>2^0, 2^1 \ldots 2^{\sqrt{w} - 1}</tex>. В результате сравнения получим номер первого ненулевого блока <tex>c</tex>.
'''4) найдем ''' Найдем номер <tex>d</tex> первого еденичного бита в найденном блоке так же как и в предыдущем пункте.
'''5) инедекс ''' Индекс наиболее значащего бита будет равен <tex>c\sqrt{w}+d</tex>.
Каждый шаг выполняется за <tex>O(1)</tex>, поэтому всего потребуется <tex>O(1)</tex> времени, чтобы найти индекс.
