Изменения

'''ВНИМАНИЕ, СТАТЬЯ НАХОДИТСЯ В РАЗРАБОТКЕ''' '''Побитовые операции''' (англ. ''bitwise operations'') — операции, производимые над цепочками битов. Выделяют два типа побитовых операций: [[Определение булевой функции | логические операции ]] и побитовые сдвиги.

Битовые операторы И <tex>(AND, \ \&)</tex>, ИЛИ <tex>(OR, \ \mid)</tex>, НЕ <tex>(NOT, \ \sim)</tex> и исключающее ИЛИ <tex>(XOR, \ $\textasciicircum$,\ \oplus)</tex> используют те же таблицы истинности, что и их логические эквиваленты.

Операторы сдвига <tex>\ll<<</tex> и <tex>\gg{>>}</tex> сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код #Дополнительный код (дополнение до двух) | двоичном дополнительном коде]] и необходимо поддерживать знаковый бит). Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.

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>

'''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>

==Применение=====Сложные операции=======Определение знака числа====Пусть дано число <tex>x</tex>. Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа <tex>x</tex> можно определить, выполнив сдвиг вправо на всю длину переменной:<code> '''int32''Java'getSign(x: '''int32'''): '''if''' x != 0: mask = 1 '''else''': mask = 0 '''return''' mask | (x >> 31) <font color = green>// результатом будет -1, 0, или +1 // для отрицательного, равного нулю и положительного числа x соответственно</font></code>Используя побитовые операции можно также узнать, различны ли знаки двух переменных <tex>x</tex> и <tex>y</tex>. Если числа имеют различный знак, то результат операции XOR, произведенной над их знаковыми битами, будет единицей. Поэтому неравенство <tex>(x \oplus y) < 0</tex> будет верно в том случае, если числа <tex>x</tex> и <tex>y</tex> разного знака.

В языке программирования Java существует также оператор беззнакового битового сдвига вправо ====Вычисление модуля числа без использования условного оператора====Пусть дано число <tex>\gggx</tex>. При использовании этого оператора на освободившиеся позиции всегда устанавливаются Если <tex>x</tex> положительно, то <tex>mask = 0</tex>, тогда как при использовании и <tex>(x + mask) \ggoplus mask = x</tex> на освободившиеся позиции устанавливается бит знака.При использовании битовых сдвигов есть некоторое отличие от целочисленного деления на В случае, если <tex>2x</tex>: если сдвигать отрицательное число вправоотрицательно, то сначала это аналогично целочисленному делению на <tex>2mask = -1</tex>. Тогда получается, но когда останется что мы работаем с числом <tex>-1x</tex>так, то при следующих сдвигах результат меняться не будет. То есть происходит округление не к нулюкак будто оно представлено в [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код #Код со сдвигом |коде со сдвигом]] с тем отличием, как при целочисленном делениичто у нас знаковый бит принимает значение <tex>1</tex> для отрицательных чисел, а к <tex>-10</tex>{{---}} для положительных.<code> '''int32''' abs1(x: '''int32'''): mask = x >> 31 '''return''' (x + mask) '''XOR''' mask '''int32''' abs2(x: '''int32'''): mask = x >> 31 '''return''' (x + mask) '''XOR''' mask</code>

Также нельзя сдвинуть число на количество бит большее====Нахождение минимума и максимума из двух чисел без использования условного оператора====Этот способ корректен только если можно утверждать, чем разрядность операнда. При этом происходит неявное сокращение правого что величина <tex>(количество битx - y) операнда</tex> лежит между граничными значениями типа int.

i = 1 '''int32''' min(x, y: '''int32'''): <font color = green>//00000000 00000000 00000000 00000001 '''return''' y + ((x - y) & ((1x - y)</font>> 31)) i << 29 <font color = green>//00100000 00000000 00000000 00000000 '''int32''' max(536870912x, y: '''int32''')</font>: i << 30 <font color = green>//01000000 00000000 00000000 00000000 '''return''' x - ((1073741824x - y)</font> i << 31 <font color = green>//10000000 00000000 00000000 00000000 & ((x -2147483648 / 2147483648y)</font> i << 32 <font color = green>//00000000 00000000 00000000 00000001 (131))</font>

i = -1 '''int32''' greatestBit(x: '''int32'''): <font color power = green>//11111111 11111111 11111111 11111111 (-1 / 4294967295)</font> '''for''' i >>> = 1 <font color = greentex>//01111111 11111111 11111111 11111111 (2147483647)\ldots\log_2{32}</fonttex>: i >>> 30 <font color x |= greenx >//00000000 00000000 00000000 00000011 (3)</font>power i >>> 31 power <<font color = green>//00000000 00000000 00000000 00000001 (1)</font> i '''return''' x - (x >>> 32 <font color = green>//11111111 11111111 11111111 11111111 (-1 / 4294967295)</font>

i = -192 <font color = green>//11111111 11111111 11111111 01000000 '''int32''' rotateLeft(-192 / 4294967104x, d: '''int32'''): '''return''' (x </font< d) | (x > i >> 1 <font color = green>//11111111 11111111 11111111 10100000 (32 -96 / 4294967200d)</font>) i >> 30 <font color = green>//11111111 11111111 11111111 11111111 '''int32''' rotateRight(-1 / 4294967295x, d: '''int32''')</font>: i '''return''' (x >> 31 <font color = green>//11111111 11111111 11111111 11111111 d) | (-1 / 4294967295)x </font> i >> 32 <font color = green>//11111111 11111111 11111111 01000000 (32 -192 / 4294967104d))</font>

Арифметическое распространение ====Подсчет количества единичных битов====Для подсчета количества единичных битов в Java проводится перед операциями и гарантирует расширение каждого операнда по крайней мере до int числе <tex>x</tex> можно воспользоваться следующим алгоритмом:<code> <font color = green>// Для чисел других разрядностей необходимо использовать соответствующие константы.</font> '''int16''' setBitsNumber(x: '''int16'''): x = x - ((x >>> 1) & 0x5555) x = (или, если один из операндов имеет больший тип, то до негоx & 0x3333). Расширение происходит знаково, ввиду чего результат может быть не таким, как ожидалось; при приведении типа к меньшему лишние байты отбрасываются.+ ((x >>> 2) & 0x3333) x = (x + (x >>> 4)) & 0x0F0F '''return''' (x * 0x0101) >>> 8</code>

''Примеры:''Поскольку <codetex> '''byte''' b = -127 5555_{16}<font color = green/tex> равно <tex>01010101 01010101_{2}</tex>, результатом операции <tex>x\ \&\ 5555_{16}</tex> является число, в котором все нечетные биты соответствуют нечетным битам числа <tex>x</10000001 tex>. Аналогично, результатом операции <tex>(-127 / 129x\ \texttt{>>>}\ 1)\ \&\ 5555_{16}</fonttex> ('''int''')b является число, в котором все нечетные биты соответствуют четным битам <font color = greentex>//11111111 11111111 11111111 10000001 (-127 / 4294967169)x</fonttex>. Четные биты результата в обоих случаях равны нулю.

'''int''' i = -127 Мысленно разобьем двоичную запись нашего числа <font color = greentex>x</tex> на группы по <tex>2</11111111 11111111 11111111 10000001 tex> бита. Результатом операции <tex>x\ \&\ 5555_{16} + (-127 / 4294967169x\ \texttt{>>>}\ 1)\ \&\ 5555_{16}</fonttex> ('''byte''')i будет такое число, что если разбить его двоичную запись на группы по два бита, значение каждой группы соответствует количеству единичных битов в соответствующей паре битов числа <font color = greentex>//10000001 (-127 / 129)x</fonttex>.

'''int''' i = 128 Аналогично, число <font color = greentex>3333_{16}</tex> равно <tex>00110011 00110011_{2}</00000000 00000000 00000000 10000000 tex> и операция <tex>x = (x\ \&\ 3333_{16}) + (128x\ \texttt{>>>}\ 2\ \&\ 3333_{16})</fonttex> ('''byte''')i , примененная к результату, полученному на первом этапе, выполняет подсчет количества единичных битов в блоках по <tex>4</tex>. В свою очередь, число <font color = greentex>\texttt{0F0F}_{16}</tex> равно <tex>00001111 00001111_{2}</10000000 tex> и операция <tex>x = (x\ \&\ \texttt{0F0F}_{16}) + (-128 x\ \texttt{>>>}\ 4\ \&\ \texttt{0F0F}_{16})</ 128)tex> позволяет подсчитать число единичных бит в блоках по <tex>8</fonttex>.

'''int''' i = 256 Теперь необходимо просуммировать числа, записанные в блоках по <font color = greentex>8</tex> битов, чтобы получить искомую величину. Это можно сделать, домножив результат на <tex>0101_{16}</00000000 00000000 00000001 00000000 tex> <tex>(2561 00000001_{2})</fonttex> ('''byte''')i . Ответ на задачу будет находиться в первых восьми битах произведения. Выполнив сдвиг вправо на <font color = greentex>8<//00000000 tex> (0для шестнадцатибитных чисел)</font>, мы получим долгожданный ответ.

Подведем итог:<code> '''intint16''' i setBitsNumber(x: '''int16'''): x = -256 <font color (x & 0x5555) + ((x >>> 1) & 0x5555) x = green(x & 0x3333) + ((x >//11111111 11111111 11111111 00000000 >> 2) & 0x3333) x = (-256 / 4294967040x & 0x0F0F)</font+ ((x >>>4) & 0x0F0F) ( '''bytereturn'''(x * 0x0101)i <font color = green>//00000000 (0)</font>> 8

==Применение для решения задач==*'''''Проверка на тоЗаметим, является ли число степенью двойки'''''*:Если выражение что операция <tex>(x\ \&\ 55_{16} + (x - \ \texttt{>>>}\ 1))\ \&\ 55_{16}</tex> равно нулю, то число равносильна операции <tex>x</tex> является степенью двойки <tex>- (x \not= 0)</tex\texttt{>>.*'''''Проверка на то, что в битовой записи числа нет двух единиц, идущих подряд'''''*:Если выражение <tex>(x}\ 1)\ \&\ (x \ll 1))55_{16}</tex> равно нулю, то в битовой записи чем легко убедиться, рассмотрев все числа <tex>x</tex> нет из двух единиц, идущих подрядбит.*'''''Номер младшего единичного бита'''''*:ЧислоВ свою очередь, полученное в результате операции операцию <tex>(x\ \&\ (\sim x texttt{0F0F}_{16}) + 1)</tex> будет равно номеру младшего единичного бита в числе <tex>((x</tex\ \texttt{>.*'''''Работа с битовыми масками'''''*:Храним подмножества множества из <tex>32, 64</tex> или <tex>128</tex> фиксированных элементов. Значение каждого бита позволяет понять, включен элемент в множество или нет. Тогда легко сделать следующее: найти дополнение <tex>(}\sim4)</tex>, пересечение <tex>(\ \&\ \texttt{0F0F}_{16})</tex>, объединение можно заменить на <tex>(x + (x\ \mid)</textexttt{>> множеств, установить бит по номеру <tex>(}\ 4))\ \&\mid 1 \ll x)texttt{0F0F}_{16}</tex>. Эта замена не повлияет на результат, снять бит по номеру так как максимальное значение в любой группе из четырех битов данного числа равно четырем, то есть требует только трех битов для записи, и выполнение суммирования не повлечет за собой переполнения и выхода за пределы четверок. Таким образом, мы получили код, приведенный в начале раздела. ====Разворот битов====Чтобы получить биты числа <tex>(\& \sim(1 \ll x))</tex>, записанные в обратном порядке, применим следующий алгоритм.*'''''Определение знака числа'''''

sign <font color = green>// Для чисел других разрядностей нужны соответствующие константы.</font> '''int16''' reverseBits(v !x: '''int16'''): x = 0) | -(int(x & 0x5555)((unsigned int<< 1)| ((intx >>> 1)v& 0x5555) <font color = green>// Четные и нечетные биты поменялись местами.</font> x = (sizeof(intx & 0x3333) * CHAR_BIT - 1<< 2) | ((x >>> 2)& 0x3333); <font color = green>//Биты "перетасовываются" группами по два.</ Or, for more speed but less portability:font>sign x = (v != 0(x & 0x0F0F) << 4) | (v (x >> (sizeof(int) * CHAR_BIT - 1> 4)& 0x0F0F); <font color = green>//Биты "перетасовываются" группами по четыре.</ -1, 0, or +1font>// Or, for portability, brevity, and x = ((perhapsx & 0x00FF) speed:sign = << 8) | ((v x > 0>> 8) - (v & 0x00FF) < 0); font color = green>//Биты "перетасовываются" группами по восемь.</ -1, 0, or +1font> '''return''' x

*Более подробно про то, что за константы выбраны для данного алгоритма, можно прочитать в разделе [[Побитовые_операции#Подсчет_количества_единичных_битов | подсчет количества единичных битов]]. ===Применение для решения задач=======Работа с битовыми масками====Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение <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>. Битовые маски используются, например, при решении некоторых задач<ref>[[Гамильтоновы графы #Задача о коммивояжере| Динамическое программирование по подмножествам (по маскам)]]</ref> [[Динамическое программирование | динамического программирования]]. ====Алгоритм Флойда===={{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(\Biglog n) </tex>, задается следующей формулой <tex> F(i) = (i \dfracAnd (i + 1)) </tex>.Пусть дан массив <tex> A = [a_0, a_1, \ldots, a_{n^3- 1}]</tex>. Деревом Фенвика называется массив <tex> T </tex> из <tex> n </tex> элементов: <tex> T_i = \sum\limits_{k= F(i)}^{i} a_k</tex>, где <tex> i = 0\Bigldots n - 1 </tex> и <tex> F(i)</tex>— функция, которую мы определили ранее. ==См. также==* [[Определение булевой функции]]* [[Сумматор]]*'''''[[Дерево ФенвикаТриггеры]]''''' ==Примечания==<references/>

* [http://www.c-cpp.ru/books/bitovye-operatory| Онлайн справочник программиста на С и С++]* [http://developer.alexanderklimov.ru/android/java/bitwise.php Побитовые операторы]* [https://msdngraphics.stanford.microsoftedu/~seander/bithacks.comhtml Bit Twiddling Hacks by Sean Eron Anderson]* [https://habrahabr.ru/post/93172/ Habrahabr {{-ru--}} Алгоритмы поиска старшего бита]* [https:/library/336xbhczyesteapea.wordpress.aspx| MSDN: Операторы сдвигов влево и вправо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]

[http[Категория://dark-barker.blogspot.ru/2012/03/bit-operations-java-pitfalls.html| Битовые сдвиги Дискретная математика и приведения в Javaалгоритмы]][[Категория: подводные камниБулевы функции ]]