317
правок
Изменения
→Параллельное сравнение
Длина наибольшего общего префикса двух <tex>w</tex>-битных чисел <tex>a</tex> и <tex>b</tex> может быть вычислена с помощью нахождения индекса наиболее значащего бита в побитовом <tex>\oplus a</tex> и <tex>b</tex>.
===Параллельное сравнениеСравнение значений sketch двух чисел===Найдем В предыдущем абзаце мы научились считать <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>, сохранятся единицы. Применим к получившемуся побитовое <tex>\&</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)) \& \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>
