1632
правки
Изменения
м
rollbackEdits.php mass rollback
===Побитовые сдвиги===
Операторы сдвига <tex>\texttt{<<}</tex> и <tex>\texttt{>>}</tex> сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код #Дополнительный код (дополнение до двух) | двоичном дополнительном коде]] и необходимо поддерживать знаковый бит).
Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.
</code>
В языке программирования Java существует также оператор беззнакового битового сдвига вправо <tex>\texttt{>>>}</tex>. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.
<code>
'''int32''' abs1(x: '''int32'''):
mask = x >> 31
'''return''' (x + mask) <tex>\oplus</tex> '''XOR''' mask
'''int32''' abs2(x: '''int32'''):
mask = x >> 31
'''return''' (x <tex>\oplus</tex> + mask) - '''XOR''' mask
</code>
Этот способ корректен только если можно утверждать, что величина <tex>(x - y)</tex> лежит между граничными значениями типа int.
Пусть даны числа <tex>x</tex> и <tex>y</tex> разрядности <tex>n</tex>. Тогда, если <tex>x < y</tex>, то <tex>((x - y) \texttt{>>} (n - 1)) = -1</tex> , а если <tex>x \geqslant y</tex>, то <tex>((x - y) \texttt{>>} (n - 1)) = 0</tex>. Выражение <tex>((x - y) \& ((x - y) \texttt{>>} (n - 1))</tex> принимает значение <tex>0</tex>, если <tex>x \geqslant y</tex> , и <tex>(x - y)</tex>, если <tex>x < y</tex>.
<code>
'''int32''' min(x, y: '''int32'''):
'''int32''' greatestBit(x: '''int32'''):
power = 1
'''for''' i = 1..<tex>\ldots\log_2{32}</tex>:
x |= x >> power
power <<= 1
====Алгоритм Флойда====
{{main|Алгоритм Флойда}}
'''Алгоритм Флойда–Уоршелла''' (англ. ''the Floyd–Warshall algorithm'') {{---}} алгоритм, разработанный в <tex>1962</tex> году Робертом Флойдом <ref> [https://ru.wikipedia.org/wiki/Флойд_Роберт|Роберт Флойд]</ref> и Стивеном Уоршеллом для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а если же такой цикл есть, позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма <tex> \Theta(n^3) </tex>, также требует <tex> \Theta(n^2) </tex> памяти. В модификации данного алгоритма для [[Алгоритм_Флойда#Построение_транзитивного_замыкания|построения транзитивного замыкания]] можно применить оптимизацию с помощью битовых масок. С помощью неё можно добиться улучшения времени работы. Если обозначить за <tex> k </tex> длину битовой макси, то асимптотическая сложность алгоритма поменяется и станет равна <tex>O\Big(\dfrac{n^3}{k}\Big).</tex>
====Дерево Фенвика====
Функция, позволяющая делать операции вставки и изменения элемента за <tex> O(\log n) </tex>, задается следующей формулой <tex> F(i) = (i \And (i + 1)) </tex>.
Пусть дан массив <tex> A = [a_0, a_1, \ldots, a_{n - 1}]</tex>. Деревом Фенвика называется массив <tex> T </tex> из <tex> n </tex> элементов: <tex> T_i = \sum\limits_{k = F(i)}^{i} a_k</tex>, где <tex> i = 0 .. \ldots n - 1 </tex> и <tex> F(i) </tex> — функция, которую мы определили ранее.
==См. также==
