Изменения

'''Побитовые операции''' (англ. ''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>

В языке программирования Java существует также оператор беззнакового битового сдвига вправо <tex>\ggg>>></tex>. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.

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

'''''Java'''''==Применение=====Сложные операции===При ====Определение знака числа====Пусть дано число <tex>x</tex>. Поскольку при сдвиге вправо на количество освобождающиеся позиции устанавливается бит большеезнака, чем разрядность левого операндазнак числа <tex>x</tex> можно определить, происходит неявное сокращение правого операнда (количество бит). ''Примерывыполнив сдвиг вправо на всю длину переменной:''

i '''int32''' getSign(x: '''int32'''): '''if''' x != 0: mask = 1 <font color '''else''': mask = green>//00000000 00000000 00000000 00000001 (1)</font>0 i << 29 <font color = green>//00100000 00000000 00000000 00000000 '''return''' mask | (536870912)</font> i << 30 <font color = greenx >//01000000 00000000 00000000 00000000 (1073741824)</font> i << 31 ) <font color = green>//10000000 00000000 00000000 00000000 (результатом будет -2147483648 / 2147483648)</font>1, 0, или +1 i << 32 <font color = green> //00000000 00000000 00000000 00000001 (1)для отрицательного, равного нулю и положительного числа x соответственно</font>

i = -1 '''int32''' abs1(x: '''int32'''): <font color mask = greenx >>//11111111 11111111 11111111 11111111 31 '''return''' (-1 / 4294967295x + mask)</font>'''XOR''' mask i >>> 1 <font color = green>//01111111 11111111 11111111 11111111 (2147483647)</font> i >>> 30 <font color = green>//00000000 00000000 00000000 00000011 '''int32''' abs2(3x: '''int32''')</font>: i > mask = x >> 31 <font color = green>//00000000 00000000 00000000 00000001 (1)</font> i >>> 32 <font color = green>//11111111 11111111 11111111 11111111 '''return''' (-1 / 4294967295x + mask)</font>'''XOR''' mask

i = -192 <font color = green>//11111111 11111111 11111111 01000000 '''int32''' min(-192 / 4294967104x, y: '''int32''')</font>: i >> 1 <font color = green>//11111111 11111111 11111111 10100000 '''return''' y + ((x - y) & ((x -96 / 4294967200y)</font>> 31)) i >> 30 <font color = green>//11111111 11111111 11111111 11111111 '''int32''' max(-1 / 4294967295x, y: '''int32''')</font>: i >> 31 <font color = green>//11111111 11111111 11111111 11111111 '''return''' x - ((x -1 / 4294967295y)</font> i >> 32 <font color = green>//11111111 11111111 11111111 01000000 & ((x -192 / 4294967104y)</font>> 31))

====Проверка на то, является ли число степенью двойки====Пусть дано число <tex>x</tex>. Тогда, если результатом выражения <tex>(x\ \&\&\ !(x\ \&\ (x - 1)))</tex> является единица, то число <tex>x</tex> {{Acronym | Арифметическое распространение | Приведение меньшего типа данных к большему---}} в Java проводится перед операциями и гарантирует расширение каждого операнда по крайней мере до int степень двойки. Правая часть выражения <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> равна единице.

''Примеры:''<code> '''byte''' b = -127 <font color = green>//10000001 (-127 / 129)</font>==Нахождение младшего единичного бита==== ('''int''')b Пусть дано число <font color = greentex>//11111111 11111111 11111111 10000001 (-127 / 4294967169)x</fonttex>и необходимо узнать его младший единичный бит.

'''int''' i = -127 Применим к числу <font color = greentex>x<//11111111 11111111 11111111 10000001 tex> побитовое отрицание, чтобы инвертировать значения всех его бит, а затем прибавим к полученному числу единицу. У результата первая часть (-127 / 4294967169до младшего единичного бита)не совпадает с исходным числом <tex>x</fonttex> ('''byte''')i , а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа <font color = greentex>//10000001 (-127 / 129x\ \&\ (\sim x + 1))</fonttex>.

'''int''' i = 128 К такому же результату можно прийти, если сначала отнять от числа <font color = greentex>x<//00000000 00000000 00000000 10000000 (128)tex> единицу, чтобы обнулить его младший единичный бит, а все последующие разряды обратить в <tex>1</fonttex> ('''byte''')i , затем инвертировать результат и применить побитовое И с исходным числом <font color = greentex>//10000000 (x\ \&\ \sim (x -128 / 1281))</fonttex>.

'''int''' i = 256 <font color = green>//00000000 00000000 00000001 00000000 (256)</font>==Нахождение старшего единичного бита==== ('''byte''')i Пусть дано число <font color = greentex>//00000000 (0)x</fonttex>и необходимо узнать его старший единичный бит.

'''int''' i = Рассмотрим некоторое число, представим его как <tex>0\dots01b \dots b</tex>, где <tex>b</tex> {{---256 }} любое значение бита. Тогда, если совершить битовый сдвиг этого числа вправо на <tex>1</tex> и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим результат <font color = greentex>0\dots011b \dots b</tex>. Если мы повторим эту последовательность действий над полученным числом, но устроим сдвиг на <tex>2</11111111 11111111 11111111 00000000 tex>, то получим <tex>0\dots01111b \dots b</tex>. При каждой следующей операции будем увеличивать модуль сдвига до следующей степени двойки. После некоторого количества таких операций (зависит от разрядности числа) мы получим число вида <tex>0\dots01\dots1</tex>. Тогда результатом выполнения действий <tex>x -256 / 4294967040(x \texttt{ >> }1)</fonttex> будет число, состоящее только из старшего бита исходного числа.<code> '''int32''' greatestBit(x: '''byteint32'''): power = 1 '''for''' i = 1 <font color tex> \ldots\log_2{32}</tex>: x |= greenx >>//00000000 power power <<= 1 '''return''' x - (0x >> 1)</font>

==Применение для решения задач==Циклический сдвиг====Проверка Пусть дано число <tex>x</tex> и надо совершить циклический сдвиг его битов на величину <tex>d</tex>.Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на <tex>d</tex> и в противоположном направлении на торазность между разрядностью числа и величиной сдвига. Таким образом, является ли число степенью двойки===мы сможем поменять местами начальную и конечную части числа. 

answer = '''int32''' rotateLeft(x && !, d: '''int32'''): '''return''' (x & << d) | (x >>> (32 - 1d)) <font color = green '''int32''' rotateRight(x, d: '''int32'''): '''return''' (x >>>// если answer == 1, то число d) | (x является степенью двойки</font>< (32 - d))

sign = (x != 0) | (x >> (''sizeof''('''int''') * '''CHAR_BIT''' - 1)) <font color = green>// результатом будет -1, 0, или +1 =Подсчет количества единичных битов==== // для отрицательного, равного нулю и положительного числа x соответственноДля подсчета количества единичных битов в числе </fonttex>x</codetex>Используя побитовые операции можно также узнать, различны ли знаки двух переменныхвоспользоваться следующим алгоритмом:

<font color = green>// Для чисел других разрядностей необходимо использовать соответствующие константы.</font> '''int16'''boolsetBitsNumber(x: ''' result int16'''): x = x - ((x <tex>\oplus</tex> y> 1) < 0& 0x5555) <font color x = green(x & 0x3333) + ((x >>>// значение переменной result =2) & 0x3333) x = (x + (x >>> 4)) & 0x0F0F '''return'true'', если знаки переменных (x и y различны</font* 0x0101) >>>8

 Поскольку <tex>5555_{16}</tex> равно <tex>01010101 01010101_{2}</tex>, результатом операции <tex>x\ \&\ 5555_{16}</tex> является число, в котором все нечетные биты соответствуют нечетным битам числа <tex>x</tex>. Аналогично, результатом операции <tex>(x\ \texttt{>>>}\ 1)\ \&\ 5555_{16}</tex> является число, в котором все нечетные биты соответствуют четным битам <tex>x</tex>. Четные биты результата в обоих случаях равны нулю. Мысленно разобьем двоичную запись нашего числа <tex>x</tex> на группы по <tex>2</tex> бита. Результатом операции <tex>x\ \&\ 5555_{16} + (x\ \texttt{>>>}\ 1)\ \&\ 5555_{16}</tex> будет такое число, что если разбить его двоичную запись на группы по два бита, значение каждой группы соответствует количеству единичных битов в соответствующей паре битов числа <tex>x</tex>. Аналогично, число <tex>3333_{16}</tex> равно <tex>00110011 00110011_{2}</tex> и операция <tex>x =(x\ \&\ 3333_{16}) + (x\ \texttt{>>>}\ 2\ \&\ 3333_{16})</tex>, примененная к результату, полученному на первом этапе, выполняет подсчет количества единичных битов в блоках по <tex>4</tex>. В свою очередь, число <tex>\texttt{0F0F}_{16}</tex> равно <tex>00001111 00001111_{2}</tex> и операция <tex>x ==Вычисление модуля (x\ \&\ \texttt{0F0F}_{16}) + (x\ \texttt{>>>}\ 4\ \&\ \texttt{0F0F}_{16})</tex> позволяет подсчитать число единичных бит в блоках по <tex>8</tex>. Теперь необходимо просуммировать числа без использования условного оператора===, записанные в блоках по <tex>8</tex> битов, чтобы получить искомую величину. Это можно сделать, домножив результат на <tex>0101_{16}</tex> <tex>(1 00000001_{2})</tex>. Ответ на задачу будет находиться в первых восьми битах произведения. Выполнив сдвиг вправо на <tex>8</tex> (для шестнадцатибитных чисел), мы получим долгожданный ответ. Подведем итог:

mask = x >> ''sizeof'int16'''setBitsNumber(x: '''intint16''') * '''CHAR_BIT''' - 1: abs x = (x & 0x5555) + mask) <tex((x >>\oplus</tex> mask1) & 0x5555) <font color x = green(x & 0x3333) + ((x >>// другой способ сделать то же самое:</font>2) & 0x3333) abs x = (x <tex& 0x0F0F) + ((x >\oplus</tex> mask> 4) - mask& 0x0F0F) '''return''' (x * 0x0101) >>> 8

 Заметим, что операция <tex>x\ \&\ 55_{16} + (x\ \texttt{>>>}\ 1)\ \&\ 55_{16}</tex> равносильна операции <tex>x - (x\ \texttt{>>>}\ 1)\ \&\ 55_{16}</tex>, в чем легко убедиться, рассмотрев все числа из двух бит. В свою очередь, операцию <tex>(x\ \&\ \texttt{0F0F}_{16}) + ((x\ \texttt{>>>}\ 4)\ \&\ \texttt{0F0F}_{16})</tex> можно заменить на <tex>(x + (x\ \texttt{>>>}\ 4))\ \&\ \texttt{0F0F}_{16}</tex>. Эта замена не повлияет на результат, так как максимальное значение в любой группе из четырех битов данного числа равно четырем, то есть требует только трех битов для записи, и выполнение суммирования не повлечет за собой переполнения и выхода за пределы четверок. Таким образом, мы получили код, приведенный в начале раздела. ===Нахождение минимума и максимума из двух чисел без использования условного оператора=Разворот битов====Этот способ корректен только если можно утверждать, что величина Чтобы получить биты числа <tex>(x - y)</tex> лежит между граничными значениями типа int, записанные в обратном порядке, применим следующий алгоритм.

min <font color = y + ((x - y) & ((x - y) green>// Для чисел других разрядностей нужны соответствующие константы.</font> ( '''int16'sizeof''reverseBits(x: '''intint16''') * '''CHAR_BIT''' - : x = ((x & 0x5555) << 1)| ((x >>> 1)& 0x5555) <font color = green>// Четные и нечетные биты поменялись местами.</font> x = ((x & 0x3333) << 2) | ((x >>> 2) & 0x3333) max <font color = green>// Биты "перетасовываются" группами по два.</font> x - = ((x - y& 0x0F0F) << 4) & | ((x - y>>> 4) & 0x0F0F) <font color = green>// Биты "перетасовываются" группами по четыре.</font> x = ((x & 0x00FF) << 8) | (''sizeof''('''int'''x >>> 8) & 0x00FF) * <font color = green>// Биты "перетасовываются" группами по восемь.</font> '''CHAR_BITreturn''' - 1)))x

Более подробно про то, что за константы выбраны для данного алгоритма, можно прочитать в разделе [[Побитовые_операции#Подсчет_количества_единичных_битов | подсчет количества единичных битов]]. ===Применение для решения задач=======Работа с битовыми масками====Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение <tex>(\sim mask)</tex>, пересечение <tex>(mask_1\ \&\ mask_2)</tex>, объединение <font color = greentex>(mask_1 \mid mask_2)</tex> множеств, установить бит по номеру <tex>(mask \mid (1\ \texttt{<<}\ x))</ функция для расшифровки текстаtex>, снять бит по номеру <tex>(mask\ \&\ \sim(1\ \texttt{<<}\ x))</tex>. Битовые маски используются, например, при решении некоторых задач<ref>[[Гамильтоновы графы #Задача о коммивояжере| Динамическое программирование по подмножествам (по маскам)]]</fontref>[[Динамическое программирование | динамического программирования]]. ====Алгоритм Флойда===={{main|Алгоритм Флойда}} '''functionАлгоритм Флойда–Уоршелла''' decode(secret: англ. '''byte[]'the Floyd–Warshall algorithm'') {{---}} алгоритм для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а если же такой цикл есть, позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма <tex> \Theta(n^3) </tex>, key: '''string'''также требует <tex> \Theta(n^2): '''string'''</tex> памяти.  bkey = key.''getBytes''===Дерево Фенвика==== {{main|Дерево Фенвика}} '''forДерево Фенвика''' i = 0 .. secret(англ.''lengthBinary indexed tree'') {{---}} структура данных, которая может выполнять следующие операции: result* изменять значение любого элемента в массиве,* выполнять некоторую [[iАссоциативная_операция |ассоциативную]], [[Абелева_группа |коммутативную]] = (secret, [[iГруппа |обратимую операцию]] <tex>\opluscirc </tex> bkeyна отрезке <tex> [i % bkey, j] </tex>.''length''] Данная структура требует <tex> O(n) </tex> памяти, а выполнение каждой операции происходит за <tex> O(\log n) ''as'' '''byte'''</tex> . '''return''' result ''as'' '''string'''Функция, позволяющая делать операции вставки и изменения элемента за <tex> O(\log n) </tex>, задается следующей формулой <tex> F(i) = (i \And (i + 1)) </tex>.Пусть дан массив <tex> A = [a_0, a_1, \ldots, a_{n - 1}]</codetex>. Деревом Фенвика называется массив <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> — функция, которую мы определили ранее. ==См. также==* [[Определение булевой функции]]* [[Сумматор]]* [[Триггеры]]

===[[Алгоритм Флойда#Оптимизация с помощью битовых масок | Алгоритм Флойда]]=Примечания=====[[Дерево Фенвика]]===<references/>