'''Побитовые операции''' (англ. ''bitwise operations'') — операции, производимые над цепочками битов. Выделяют два типа побитовых операций: [[Определение булевой функции | логические операции ]] и побитовые сдвиги.
==Принцип работы==
===Логические побитовые операции===
Битовые операторы И <tex>(AND, \ \&)</tex>, ИЛИ <tex>(OR, \ \mid)</tex>, НЕ <tex>(NOT, \ \sim)</tex> и исключающее ИЛИ <tex>(XOR, \ $\textasciicircum$, \ \oplus)</tex> используют те же таблицы истинности, что и их логические эквиваленты.
====Побитовое И====
Побитовое И используется для выключения битов. Любой бит, установленный в <tex>0</tex>, вызывает установку соответствующего бита результата также в <tex>0</tex>.
===Побитовые сдвиги===
Операторы сдвига <tex>\texttt{<<}</tex> и <tex>\texttt{>>}</tex> сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как поддерживается числа представляются в [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код #Дополнительный код (дополнение до двух) | двоичном дополнительном коде]] и необходимо поддерживать знаковый бит).
Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.
<code>
x = 7 <font color = green>//00000111(7)</font> x = x >> 1 <font color = green>// 00000011 (3)</font> x = x << 1 <font color = green>//0000111000000110 (6)</font> x = x << 5 <font color = green>//11000000(-64)</font> x = x >> 2 <font color = green>//0011000011110000 (-16)</font>
</code>
В языке программирования Java существует также оператор беззнакового битового сдвига вправо <tex>\texttt{>>>}</tex>. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.
====Ограничения====
При использовании битовых сдвигов для отрицательных чисел округление происходит к <tex>-\infty</tex>.
'''''C++ Visual Studio 15'''''
Если выполняется сдвиг влево числа со знаком и при этом затрагивается бит знака, результат не определен.
Результат сдвига вправо отрицательного числа со знаком зависит от реализации.
Результат операции сдвига также не определен, если число, на которое нужно сдвинуть биты, имеет отрицательное значение, или если оно больше или равно количеству битов в исходном числе.
<code>
'''short''' x = 16384 7 <font color = green>// 01000000 0000000000000111 (7)</font> '''short''' y x = x << 1 5 <font color = green>// 10000000 0000000011100000 (-32)</font> x = x >>> 2 <font color = green>// 16384 left-shifted by 1 = -3276800111000 (56)</font>
</code>
'''''Java'''''==Применение=====Сложные операции=======Проверка на то, является ли число степенью двойки====
При сдвиге на количество бит большее, чем разрядность левого операнда, происходит неявное сокращение правого операнда (количество бит).
''Примеры:''
<code>
i answer = 1 <font color = green>//00000000 00000000 00000000 00000001 (1)</font> i << 29 <font color = green>//00100000 00000000 00000000 00000000 (536870912)</font> i << 30 <font color = green>//01000000 00000000 00000000 00000000 (1073741824)</font> i << 31 <font color = green>//10000000 00000000 00000000 00000000 (-2147483648 / 2147483648)</font> i << 32 <font color = green>//00000000 00000000 00000000 00000001 (1)</font></code> <code> i = -1 <font color = green>//11111111 11111111 11111111 11111111 (-1 / 4294967295)</font> i >>> 1 <font color = green>//01111111 11111111 11111111 11111111 (2147483647)</font> i >>> 30 <font color = green>//00000000 00000000 00000000 00000011 (3)</font> i >>> 31 <font color = green>//00000000 00000000 00000000 00000001 (1)</font> i >>> 32 <font color = green>//11111111 11111111 11111111 11111111 (-1 / 4294967295)</font></code> <code> i = -192 <font color = green>//11111111 11111111 11111111 01000000 (-192 / 4294967104)</font> i >> 1 <font color = green>//11111111 11111111 11111111 10100000 (-96 / 4294967200)</font> i >> 30 <font color = green>//11111111 11111111 11111111 11111111 (-1 / 4294967295)</font> i >> 31 <font color = green>//11111111 11111111 11111111 11111111 (-1 / 4294967295)</font> i >> 32 <font color = green>//11111111 11111111 11111111 01000000 (-192 / 4294967104)</font></code> {{Acronym | Арифметическое распространение | Приведение меньшего типа данных к большему}} в Java проводится перед операциями и гарантирует расширение каждого операнда по крайней мере до int (или, если один из операндов имеет больший тип, то до него). Расширение происходит знаково, ввиду чего результат может быть не таким, как ожидалось; при приведении типа к меньшему лишние байты отбрасываются. x ''Примеры:'and'<code> '''byte''not' b = -127 <font color = green>//10000001 (-127 / 129)</font> ('''int''')b <font color = green>//11111111 11111111 11111111 10000001 (-127 / 4294967169)</font> '''int''' i = -127 <font color = green>//11111111 11111111 11111111 10000001 x & (x -127 / 42949671691)</font> ('''byte''')i <font color = green>//10000001 (-127 / 129)</font> '''int''' i если answer = 128 <font color = green>//00000000 00000000 00000000 10000000 (128)</font> ('''byte''')i <font color = green>//10000000 (-128 / 128)</font> '''int''' i = 256 <font color = green>//00000000 00000000 00000001 00000000 (256)</font> ('''byte''')i <font color = green>//00000000 (0)</font> '''int''' i = -256 <font color = green>//11111111 11111111 11111111 00000000 (-256 / 4294967040)</font> ('''byte''')i <font color = green>//00000000 (0)1, то число x является степенью двойки</font>
</code>
==Применение для решения задач=====Проверка на то, является ли число степенью двойки===<code> answer = x '''and''' '''not'''(x & (x - 1)) <font color = green>// если answer == 1, то число x является степенью двойки</font></code>===Работа с битовыми масками===Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение <tex>(\sim mask)</tex>, пересечение <tex>(mask_1\ \&\ mask_2)</tex>, объединение <tex>(mask_1 \mid mask_2)</tex> множеств, установить бит по номеру <tex>(mask \mid (1\ \texttt{<<}\ x))</tex>, снять бит по номеру <tex>(mask\ \&\ \sim(1\ \texttt{<<}\ x))</tex>.===Определение знака числа====
Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа можно определить следующим образом:
<code>
'''bool''' result = ((x <tex>\oplus</tex> y) < 0) <font color = green>// значение переменной result == ''true'', если знаки переменных x и y различны</font>
</code>
====Вычисление модуля числа без использования условного оператора====
<code>
mask = x >> ''sizeof''('''int''') * '''CHAR_BIT''' - 1
abs = (x <tex>\oplus</tex> mask) - mask
</code>
====Нахождение минимума и максимума из двух чисел без использования условного оператора====
Этот способ корректен только если можно утверждать, что величина <tex>(x - y)</tex> лежит между граничными значениями типа int.
<code>
max = x - ((x - y) & ((x - y) >> (''sizeof''('''int''') * '''CHAR_BIT''' - 1)))
</code>
===Кодирование информации===
<code>
<font color = green>// функция для шифровки текста с помощью XOR</font>
'''function''' encode(secret: '''string''', key: '''string'''): '''byte[]'''
btxt = secret.''getBytes''
bkey = key.''getBytes''
'''for''' i = 0 .. btxt.''length'' - 1:
result[i] = (btxt[i] <tex>\oplus</tex> bkey[i % bkey.''length'']) '''as''' '''byte'''
'''return''' result
===Применение для решения задач=======Работа с битовыми масками====Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение <font color = greentex>(\sim mask)</tex>, пересечение <tex>(mask_1\ \&\ mask_2)</ функция для расшифровки текстаtex>, объединение <tex>(mask_1 \mid mask_2)</fonttex> '''function''' decodeмножеств, установить бит по номеру <tex>(mask \mid (secret: '''byte[]'''1\ \texttt{<<}\ x))</tex>, key: '''string'''снять бит по номеру <tex>(mask\ \&\ \sim(1\ \texttt{<<}\ x)): '''string''' bkey = key</tex>.''getBytes'' '''for''' i = 0 .. secret.''length'' - 1: resultБитовые маски используются, например, при решении некоторых задач<ref>[[iГамильтоновы графы #Задача о коммивояжере| Динамическое программирование по подмножествам (по маскам)] = (secret[i] <tex>\oplus</texref> bkey[i % bkey[Динамическое программирование | динамического программирования]].''length'']) '''as''' '''byte''' '''return''' result '''as''' '''string'''====Алгоритм Флойда===={{main|Алгоритм Флойда}} </code>====Дерево Фенвика===={{main|Дерево Фенвика}}
===[[Алгоритм Флойда#Оптимизация с помощью битовых масок | Алгоритм Флойда]]=Примечания=====[[Дерево Фенвика]]===<references/>
==Источники информации==
* [http://www.c-cpp.ru/books/bitovye-operatory Онлайн справочник программиста на С и С++]
* [https://msdn.microsoft.com/ru-ru/library/336xbhcz.aspx MSDN: Операторы сдвигов влево и вправо]
* [http://dark-barker.blogspot.ru/2012/03/bit-operations-java-pitfalls.html Битовые сдвиги и приведения в Java: подводные камни]
* [http://developer.alexanderklimov.ru/android/java/bitwise.php Побитовые операторы]
* [https://graphics.stanford.edu/~seander/bithacks.html Bit Twiddling Hacks by Sean Eron Anderson]
