Изменения

Перейти к: навигация, поиск

Побитовые операции

10 860 байт добавлено, 19:40, 4 сентября 2022
м
rollbackEdits.php mass rollback
'''Побитовые операции''' (англ. ''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>\ll<<</tex> и <tex>\gg{>>}</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>\ggg>>></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'''''==Применение=====Сложные операции===При ====Определение знака числа====Пусть дано число <tex>x</tex>. Поскольку при сдвиге вправо на количество освобождающиеся позиции устанавливается бит большеезнака, чем разрядность левого операндазнак числа <tex>x</tex> можно определить, происходит неявное сокращение правого операнда (количество бит). ''Примерывыполнив сдвиг вправо на всю длину переменной:''
<code>
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>
</code>
Используя побитовые операции можно также узнать, различны ли знаки двух переменных <tex>x</tex> и <tex>y</tex>. Если числа имеют различный знак, то результат операции XOR, произведенной над их знаковыми битами, будет единицей. Поэтому неравенство <tex>(x \oplus y) < 0</tex> будет верно в том случае, если числа <tex>x</tex> и <tex>y</tex> разного знака.
====Вычисление модуля числа без использования условного оператора====
Пусть дано число <tex>x</tex>. Если <tex>x</tex> положительно, то <tex>mask = 0</tex>, и <tex>(x + mask) \oplus mask = x</tex>. В случае, если <tex>x</tex> отрицательно, <tex>mask = -1</tex>. Тогда получается, что мы работаем с числом <tex>x</tex> так, как будто оно представлено в [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код #Код со сдвигом |
коде со сдвигом]] с тем отличием, что у нас знаковый бит принимает значение <tex>1</tex> для отрицательных чисел, а <tex>0</tex> {{---}} для положительных.
<code>
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
</code>
====Нахождение минимума и максимума из двух чисел без использования условного оператора====
Этот способ корректен только если можно утверждать, что величина <tex>(x - y)</tex> лежит между граничными значениями типа int.
 
Пусть даны числа <tex>x</tex> и <tex>y</tex> разрядности <tex>n</tex>. Тогда если <tex>x < y</tex>, то <tex>((x - y) >> (n - 1)) = -1</tex>, а если <tex>x \geqslant y</tex>, то <tex>((x - y) >> (n - 1)) = 0</tex>. Выражение <tex>((x - y) \& ((x - y) >> (n - 1))</tex> принимает значение <tex>0</tex>, если <tex>x \geqslant y</tex>, и <tex>(x - y)</tex>, если <tex>x < y</tex>.
<code>
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))
</code>
====Проверка на то, является ли число степенью двойки====Пусть дано число <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>
</code>
==Применение для решения задач==Циклический сдвиг====Проверка Пусть дано число <tex>x</tex> и надо совершить циклический сдвиг его битов на величину <tex>d</tex>.Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на <tex>d</tex> и в противоположном направлении на торазность между разрядностью числа и величиной сдвига. Таким образом, является ли число степенью двойки===мы сможем поменять местами начальную и конечную части числа. 
<code>
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))
</code>
===Работа с битовыми масками===
Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение <tex>(\sim mask)</tex>, пересечение <tex>(mask_1\ \&\ mask_2)</tex>, объединение <tex>(mask_1 \mid mask_2)</tex> множеств, установить бит по номеру <tex>(mask \mid (1 \ll x))</tex>, снять бит по номеру <tex>(mask\ \&\ \sim(1 \ll x))</tex>.
===Определение знака числа===
Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа можно определить следующим образом:
<code>
<font color = green>// в этом и следующих примерах в константе '''CHAR_BIT''' хранится количество битов в одном байте</font>
sign = x >> (''sizeof''('''int''') * '''CHAR_BIT''' - 1) <font color = green>// если x < 0, результатом будет -1, иначе 0 </font>
sign = (x != 0) | (x >> (''sizeof''('''int''') * '''CHAR_BIT''' - 1)) <font color = green>// результатом будет -1, 0, или +1 =Подсчет количества единичных битов==== // для отрицательного, равного нулю и положительного числа x соответственноДля подсчета количества единичных битов в числе </fonttex>x</codetex>Используя побитовые операции можно также узнать, различны ли знаки двух переменныхвоспользоваться следующим алгоритмом:
<code>
<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
</code>
 Поскольку <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> (для шестнадцатибитных чисел), мы получим долгожданный ответ. Подведем итог:
<code>
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
</code>
 Заметим, что операция <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, записанные в обратном порядке, применим следующий алгоритм.
<code>
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
</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'':
result[i] = (btxt[i] <tex>\oplus</tex> bkey[i % bkey.''length'']) ''as'' '''byte'''
'''return''' result
Более подробно про то, что за константы выбраны для данного алгоритма, можно прочитать в разделе [[Побитовые_операции#Подсчет_количества_единичных_битов | подсчет количества единичных битов]]. ===Применение для решения задач=======Работа с битовыми масками====Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение <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/>
==Источники информации==
* [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]
* [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]
 
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции ]]
1632
правки

Навигация