Изменения

Перейти к: навигация, поиск

Алгоритм Shift-And

14 байт добавлено, 20:14, 8 июня 2014
Алгоритм
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex>
Определим <tex>Bit-Shift(M[j])</tex> как вектор, полученный сдвигом вектора для столбца <tex>M[j]</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. То есть <tex>Bit-Shift(M[j])</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>M[j]</tex>.
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex>
Из определения, нулевой столбец <tex>M</tex> состоит из нулей. Элементы любого другого столбца <tex>M[j], j > 0</tex> получаются из столбца <tex>M[j - 1]</tex> и вектора <tex>U</tex> для символа <tex>t[j]</tex>. А именно, вектор для столбца <tex>j</tex> получается операцией побитового логического умножения <tex>and</tex> вектора <tex>Bit-Shift(M[j - 1])</tex> и вектора <tex>U(t[j])</tex>.
<tex>M[j] = Bit-Shift(M[j - 1]) \ and \ U(t[j])</tex>
Например, …
Анонимный участник

Навигация