Изменения
→Побитовые сдвиги, поправлены символы операторов
===Побитовые сдвиги===
Операторы сдвига <tex>\texttt{<<}</tex> и <tex>\texttt{>>}</tex> сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код #Дополнительный код (дополнение до двух) | двоичном дополнительном коде]] и необходимо поддерживать знаковый бит).
Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.
</code>
В языке программирования Java существует также оператор беззнакового битового сдвига вправо <tex>\texttt{>>>}</tex>. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.
<code>
Пусть дано число <tex>x</tex>. Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа <tex>x</tex> можно определить, выполнив сдвиг вправо на всю длину переменной:
<code>
</code>
Используя побитовые операции можно также узнать, различны ли знаки двух переменных <tex>x</tex> и <tex>y</tex>. Если числа имеют различный знак, то результат операции XOR, произведенной над их знаковыми битами, будет единицей. Поэтому неравенство <tex>((x \oplus y) < 0</tex> будет верно в том случае, если числа <tex>x</tex> и <tex>y</tex> разного знака.
====Вычисление модуля числа без использования условного оператора====
коде со сдвигом]] с тем отличием, что у нас знаковый бит принимает значение <tex>1</tex> для отрицательных чисел, а <tex>0</tex> {{---}} для положительных.
<code>
</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>
</code>
Пусть дано число <tex>x</tex>. Тогда, если результатом выражения <tex>(x\ \&\&\ !(x\ \&\ (x - 1)))</tex> является единица, то число <tex>x</tex> {{---}} степень двойки.
Правая часть выражения <tex>(!(x\ \&\ (x - 1)))</tex> будет равна единице , только если число <tex>x</tex> равно <tex>0</tex> или является степенью двойки. Если число <tex>x</tex> является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: <tex>1\underbrace{0\dots0}_{n}</tex>, где <tex>n</tex> {{---}} показатель степени. Соответственно, выражение <tex>(x - 1)</tex> будет иметь вид <tex>\underbrace{1\dots1}_{n}</tex>, и <tex>x\ \&\ (x - 1)</tex> равно <tex>0</tex>.
Операция логического И в данном выражении отсекает тот случай, когда <tex>(x = 0)</tex> и не является степенью двойки, но при этом правая часть <tex>(!(x\ \&\ (x - 1)))</tex> равна единице.
Рассмотрим некоторое число, представим его как <tex>0\dots01b \dots b</tex>, где <tex>b</tex> {{---}} любое значение бита. Тогда, если совершить битовый сдвиг этого числа вправо на <tex>1</tex> и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим результат <tex>0\dots011b \dots b</tex>. Если мы повторим эту последовательность действий над полученным числом, но устроим сдвиг на <tex>2</tex>, то получим <tex>0\dots01111b \dots b</tex>. При каждой следующей операции будем увеличивать модуль сдвига до следующей степени двойки. После некоторого количества таких операций (зависит от разрядности числа) мы получим число вида <tex>0\dots01\dots1</tex>. Тогда результатом выполнения действий <tex>x - (x \texttt{ >> }1)</tex> будет число, состоящее только из старшего бита исходного числа.
<code>
'''intint32''' greatestBit(x: '''int32'''): power = 1 '''for''' i = 1..<tex>\ldots\log_2{n32}</tex>: x |= x >> power power <<font color = green1 '''return''' x - (x >> 1)</code> ====Циклический сдвиг====Пусть дано число <tex>x</ n {{---}} разрядность tex> и надо совершить циклический сдвиг его битов на величину <tex>d</tex>.Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на <tex>d</fonttex>и в противоположном направлении на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа. <code> '''int32''' rotateLeft(x, d: '''int32'''): '''return''' (x << d) |= (x >> power> (32 - d)) power <<= 1 result = '''int32''' rotateRight(x - , d: '''int32'''): '''return''' (x >> 1> d) | (x << (32 - d))
</code>
Для подсчета количества единичных битов в числе <tex>x</tex> можно воспользоваться следующим алгоритмом:
<code>
<font color = green>// Пример приведен для 16-ти битных чисел. // Для чисел большей разрядности других разрядностей необходимо использовать соответствующие константы.</font> '''int16''' setBitsNumber(x: '''int16'''): x = x - ((x >>> 1) & 0x5555) x = (x & 0x3333) + ((x >>> 2) & 0x3333) x = (x + (x >>> 4)) & 0x0F0F answer = '''return''' (x * 0x0101) >>> 8
</code>
Подведем итог:
<code>
'''int16''' setBitsNumber(x: '''int16'''): x = (x & 0x5555) + ((x >>> 1) & 0x5555) x = (x & 0x3333) + ((x >>> 2) & 0x3333) x = (x & 0x0F0F) + ((x >>> 4) & 0x0F0F) answer = '''return''' (x * 0x0101) >>> 8
</code>
Таким образом, мы получили код, приведенный в начале раздела.
====Разворот битов====
Чтобы получить биты числа <tex>x</tex>, записанные в обратном порядке, применим следующий алгоритм.
<code>
<font color = green>// Пример приведен для 16-ти битных чисел. // Для чисел других разрядностей нужны соответствующие константы.</font> '''int16''' reverseBits(x: '''int16'''): x = ((x & 0x5555) << 1) | ((x >>> 1) & 0x5555) <font color = green>// Четные и нечетные биты поменялись местами.</font> x = ((x & 0x3333) << 2) | ((x >>> 2) & 0x3333) <font color = green>// Биты "перетасовываются" группами по два.</font> x = ((x & 0x0F0F) << 4) | ((x >>> 4) & 0x0F0F) <font color = green>// Биты "перетасовываются" группами по четыре.</font> x = ((x & 0x00FF) << 8) | ((x >>> 8) & 0x00FF) <font color = green>// Биты "перетасовываются" группами по восемь.</font> '''return''' x
</code>
Более подробно про то, что за константы выбраны для данного алгоритма, можно прочитать в разделе [[Побитовые_операции#Подсчет_количества_единичных_битов | Подсчет подсчет количества единичных битов]].
===Применение для решения задач===
====Алгоритм Флойда====
{{main|Алгоритм Флойда}}
'''Алгоритм Флойда–Уоршелла''' (англ. ''the Floyd–Warshall algorithm'') {{---}} алгоритм для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а если же такой цикл есть, позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма <tex> \Theta(n^3) </tex>, также требует <tex> \Theta(n^2) </tex> памяти.
====Дерево Фенвика====
{{main|Дерево Фенвика}}
'''Дерево Фенвика''' (англ. ''Binary indexed tree'') {{---}} структура данных, которая может выполнять следующие операции:
* изменять значение любого элемента в массиве,
* выполнять некоторую [[Ассоциативная_операция |ассоциативную]], [[Абелева_группа |коммутативную]], [[Группа |обратимую операцию]] <tex> \circ </tex> на отрезке <tex> [i, j] </tex>.
Данная структура требует <tex> O(n) </tex> памяти, а выполнение каждой операции происходит за <tex> O(\log n) </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> — функция, которую мы определили ранее.
==См. также==
* [[Определение булевой функции]]
* [[Сумматор]]
* [[Триггеры]]
==Примечания==
* [https://habrahabr.ru/post/93172/ Habrahabr {{---}} Алгоритмы поиска старшего бита]
* [https://yesteapea.wordpress.com/2013/03/03/counting-the-number-of-set-bits-in-an-integer/ STP's blog {{---}} Counting the number of set bits in an integer]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции ]]
