234
правки
Изменения
→Succ(q) и pred(q)
Теперь надо найти количество едениц в ''L''. Умножим ''L'' на <tex>\underbrace{0\ldots 01}_{l + 1 bits}\ldots \underbrace{0\ldots 01}_{l+1 bits}</tex>, тогда все еденицы сложатся в первом блоке результата, и, чтобы получить количество едениц, сдвинем его вправо.
===Succ(q) и pred(q)===
Пусть <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>. {{Утверждение|id=prefix. |author=|about=|statement=Среди всех ключей наибольший общий префикс с <tex>q</tex> будет иметь или <tex>a_i</tex> или <tex>a_{i+1}</tex>. |proof=Педположим, что <tex>y</tex> имеет наибольший общий префикс с <tex>q</tex>. Тогда <tex>sketch(q)</tex> будет иметь больше общих битов со <tex>sketch(y)</tex>. Значит, <tex>sketch(y)</tex> ближе по значению к <tex>sketch(q)</tex>, чем <tex>sketch(a_i)</tex> или <tex>sketch(a_{i+1})</tex>, что приводит к противоречию.}}Сравнивая <tex>a\;</tex> ''XOR\;'' <tex>q</tex> и <tex>b\;</tex> ''XOR\;'' <tex>q</tex>, найдем какой из ключей имеет наибольший общий префикс с <tex>q</tex> (наименьшнее значение соответствует наибольшей длине).
Предположим, что <tex>p</tex> - наибольший общий перфикс, а <tex>y</tex> его длина, <tex>a_j</tex> - ключ, имеющий наибольший общий префикс с <tex>q</tex> (<tex>j = i</tex> или <tex>i+1</tex>).
* если <tex>q>a_j</tex>, то <tex>y + 1</tex> бит <tex>q</tex> равен еденице, а <tex>y + 1</tex> бит <tex>a_j</tex> равен 0нулю. Так как общий префикс <tex>a_j</tex> и <tex>q</tex> является наибольшим, то не существет ключа с префиксом <tex>p1</tex>.Значит, <tex>q</tex> больше всех ключей с префиксом меньшим либо равным <tex>p</tex>. Найдем <tex>pred(e)</tex> , <tex>e = p01\ldots 11</tex>, который одновременно будет <tex>равен pred(q)</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'' <tex>XORa</tex> ''a'' и ''<tex>b''</tex>.
==Вычисление sketch(x)==
