1632
правки
Изменения
м
Результат сдвига вправо отрицательного числа со знаком зависит от реализации====Нахождение минимума и максимума из двух чисел без использования условного оператора====Этот способ корректен только если можно утверждать, что величина <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>.
'''shortint32''' min(x = 16384 <font color = green>// 01000000 00000000</font>, y: '''int32'''): '''shortreturn''' y = + ((x - y) & ((x << 1 <font color = green- y) >// 10000000 00000000</font>31)) '''int32''' max(x, y: '''int32'''): <font color = green>// 16384 left '''return''' x - ((x -shifted by 1 = y) & ((x -32768</fonty) >>31))
'''''Java'''''====Проверка на то, является ли число степенью двойки====Пусть дано число <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>x</tex> и необходимо узнать его младший единичный бит. Применим к числу <tex>x</tex> побитовое отрицание, чтобы инвертировать значения всех его бит, а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом <tex>x</tex>, а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа <tex>(x\ \&\ (\sim x + 1))</tex>. К такому же результату можно прийти, если сначала отнять от числа <tex>x</tex> единицу, чтобы обнулить его младший единичный бит, а все последующие разряды обратить в <tex>1</tex>, затем инвертировать результат и применить побитовое И с исходным числом <tex>(x\ \&\ \sim (x - 1))</tex>. ====Нахождение старшего единичного бита====Пусть дано число <tex>x</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> будет число, состоящее только из старшего бита исходного числа.
i '''int32''' greatestBit(x: '''int32'''): power = 1 <font color '''for''' i = green>//00000000 00000000 00000000 00000001 (1)</fonttex> i << 29 <font color = green>//00100000 00000000 00000000 00000000 (536870912)\ldots\log_2{32}</fonttex>: i << 30 <font color x |= greenx >//01000000 00000000 00000000 00000000 (1073741824)</font>power i < power < 31 <font color = green>//10000000 00000000 00000000 00000000 1 '''return''' x - (-2147483648 / 2147483648)</fontx > i << 32 <font color = green>//00000000 00000000 00000000 00000001 (1)</font>
i = -1 '''int32''' rotateLeft(x, d: '''int32'''): '''return''' (x <font color = green< d) | (x >>>//11111111 11111111 11111111 11111111 (32 -1 / 4294967295d))</font> i >>> 1 <font color = green>//01111111 11111111 11111111 11111111 (2147483647)</font> i >>> 30 <font color = green>//00000000 00000000 00000000 00000011 '''int32''' rotateRight(3x, d: '''int32''')</font>: i '''return''' (x >>> 31 <font color = green>//00000000 00000000 00000000 00000001 d) | (1)x </font> i >>> 32 <font color = green>//11111111 11111111 11111111 11111111 (32 -1 / 4294967295d))</font>
i = -192 <font color = green>//11111111 11111111 11111111 01000000 (-192 / 4294967104)Для чисел других разрядностей необходимо использовать соответствующие константы.</font> i '''int16''' setBitsNumber(x: '''int16'''): x = x - ((x >>> 1 ) & 0x5555) <font color x = green>//11111111 11111111 11111111 10100000 (-96 / 4294967200x & 0x3333)</font+ ((x > i >> 30 <font color 2) & 0x3333) x = green>//11111111 11111111 11111111 11111111 (-1 / 4294967295)</fontx + (x > i >> 31 <font color = green>//11111111 11111111 11111111 11111111 4)) & 0x0F0F '''return''' (-1 / 4294967295x * 0x0101)</font> i >> 32 <font color = green>//11111111 11111111 11111111 01000000 (-192 / 4294967104)</font>8
''ПримерыМысленно разобьем двоичную запись нашего числа <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> (для шестнадцатибитных чисел), мы получим долгожданный ответ. Подведем итог:''
'''int''' i = -127 Заметим, что операция <font color = greentex>//11111111 11111111 11111111 10000001 x\ \&\ 55_{16} + (-127 / 4294967169x\ \texttt{>>>}\ 1)\ \&\ 55_{16}</fonttex> ('''byte''')i равносильна операции <font color = greentex>//10000001 x - (-127 / 129x\ \texttt{>>>}\ 1)\ \&\ 55_{16}</fonttex>, в чем легко убедиться, рассмотрев все числа из двух бит.
'''int''' i = 128 В свою очередь, операцию <font color = greentex>//00000000 00000000 00000000 10000000 (128x\ \&\ \texttt{0F0F}_{16}) + ((x\ \texttt{>>>}\ 4)\ \&\ \texttt{0F0F}_{16})</fonttex> ('''byte''')i можно заменить на <font color = greentex>//10000000 (-128 / 128x + (x\ \texttt{>>>}\ 4))\ \&\ \texttt{0F0F}_{16}</fonttex>. Эта замена не повлияет на результат, так как максимальное значение в любой группе из четырех битов данного числа равно четырем, то есть требует только трех битов для записи, и выполнение суммирования не повлечет за собой переполнения и выхода за пределы четверок.
'''int''' i = 256 <font color = green>//00000000 00000000 00000001 00000000 (256)</font> ('''byte''')i <font color = green>//00000000 (0)</font>Таким образом, мы получили код, приведенный в начале раздела.
===Определение знака числа===
Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа можно определить следующим образом:
<code>
<font color = green>// в этом и следующих примерах в константе '''CHAR_BIT''' хранится количество битов в одном байте</font>
sign = x >> (''sizeof''('''int''') * '''CHAR_BIT''' - 1) <font color = green>// если x < 0, результатом будет -1, иначе 0 </font>
sign Битовые маски используются, например, при решении некоторых задач<ref>[[Гамильтоновы графы #Задача о коммивояжере| Динамическое программирование по подмножествам (по маскам)]]</ref> [[Динамическое программирование | динамического программирования]]. ====Алгоритм Флойда=== (x != 0) {{main| (x >> (Алгоритм Флойда}}''sizeof'Алгоритм Флойда–Уоршелла'(''(англ. 'int'the Floyd–Warshall algorithm'') * '''CHAR_BIT''' {{-- 1)) <font color = green>// результатом будет -1}} алгоритм для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, 0если в графе нет циклов отрицательной величины, или +1 // для отрицательногоа если же такой цикл есть, равного нулю и положительного числа x соответственнопозволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма </fonttex>\Theta(n^3) </codetex>Используя побитовые операции можно , также узнать, различны ли знаки двух переменных:<code> '''bool''' result = ((x требует <tex>\oplusTheta(n^2) </tex> y) < 0) <font color памяти. = green>// значение переменной result == ''true'', если знаки переменных x и y различны</font></code>==Дерево Фенвика=Вычисление модуля числа без использования условного оператора===<code>{{main|Дерево Фенвика}} mask = x >> ''sizeof'Дерево Фенвика'(''(англ. 'int'Binary indexed tree'') * '''CHAR_BIT''' {{--- 1}} структура данных, которая может выполнять следующие операции: * изменять значение любого элемента в массиве, abs = (x + mask) * выполнять некоторую [[Ассоциативная_операция |ассоциативную]], [[Абелева_группа |коммутативную]], [[Группа |обратимую операцию]] <tex>\opluscirc </tex> mask на отрезке <font color = greentex>// другой способ сделать то же самое:[i, j] </fonttex>. Данная структура требует abs = <tex> O(x n) </tex>\oplusпамяти, а выполнение каждой операции происходит за </tex> maskO(\log n) - mask</codetex>.===Нахождение минимума и максимума из двух чисел без использования условного оператора===Этот способ корректен только если можно утверждатьФункция, что величина позволяющая делать операции вставки и изменения элемента за <tex>O(x - y\log n)</tex> лежит между граничными значениями типа int., задается следующей формулой <codetex> min = y + F((x - yi) & ((x - y) >> (''sizeof''('''int''') * '''CHAR_BIT''' - 1))) max = x - (i \And (x - y) & ((x - y) >> (''sizeof''('''int''') * '''CHAR_BIT''' - i + 1)))</codetex>.Пусть дан массив <tex> A ===Кодирование информации===[a_0, a_1, \ldots, a_{n - 1}]<code/tex>. Деревом Фенвика называется массив <font color = greentex>T <// функция для шифровки текста с помощью XORtex> из <tex> n </fonttex> '''function''' encode(secretэлементов: '''string''', key: '''string'''): '''byte[]''' btxt <tex> T_i = secret.''getBytes'' bkey \sum\limits_{k = key.''getBytes'' '''for''' F(i)}^{i} a_k</tex>, где <tex> i = 0 .. btxt.''length'' \ldots n - 1: result[i] = (btxt[i] </tex> и <tex>\oplusF(i) </tex> bkey[i % bkey— функция, которую мы определили ранее.''length'']) '''as''' '''byte''' '''return''' result
<font color = green>// функция для расшифровки текста</font> '''function''' decode(secret: '''byte[]''', key: '''string'''): '''string''' bkey = keyСм.''getBytes'' '''for''' i также== 0 .. secret.''length'' - 1: result* [i[Определение булевой функции] = (secret]* [[iСумматор]] <tex>\oplus</tex> bkey* [i % bkey.''length''[Триггеры]]) '''as''' '''byte''' '''return''' result '''as''' '''string'''</code>
* [https://msdn.microsoft.com/ru-ru/library/336xbhcz.aspx MSDN: Операторы сдвигов влево и вправо]
* [http://dark-barker.blogspot.ru/2012/03/bit-operations-java-pitfalls.html Битовые сдвиги и приведения в Java: подводные камни]
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>\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>. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.
<code> x =7 <font color =green>// 00000111 (7)</font> x =x << 5 <font color =Ограниченияgreen>// 11100000 (-32)</font> x =x >>> 2 <font color ===При использовании битовых сдвигов для отрицательных чисел округление происходит к green>// 00111000 (56)<tex/font>-\infty</texcode>.
==Применение=====Сложные операции=======Определение знака числа====Пусть дано число <tex>x</tex>. Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа <tex>x</tex> можно определить, выполнив сдвиг вправо на всю длину переменной:<code> '''int32''C++ Visual Studio 15' 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> разного знака.
====Вычисление модуля числа без использования условного оператора====Пусть дано число <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> '''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>
<code>
</code>
<code>
</code>
====Циклический сдвиг====
Пусть дано число <tex>x</tex> и надо совершить циклический сдвиг его битов на величину <tex>d</tex>.
Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на <tex>d</tex> и в противоположном направлении на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.
<code>
</code>
====Подсчет количества единичных битов====
Для подсчета количества единичных битов в числе <tex>x</tex> можно воспользоваться следующим алгоритмом:
<code>
</code>
Поскольку <tex>5555_{16}</tex> равно <tex>01010101 01010101_{Acronym | Арифметическое распространение | Приведение меньшего типа данных к большему2}</tex>, результатом операции <tex>x\ \&\ 5555_{16} </tex> является число, в Java проводится перед операциями и гарантирует расширение каждого операнда по крайней мере до int котором все нечетные биты соответствуют нечетным битам числа <tex>x</tex>. Аналогично, результатом операции <tex>(илиx\ \texttt{>>>}\ 1)\ \&\ 5555_{16}</tex> является число, если один из операндов имеет больший тип, то до него)в котором все нечетные биты соответствуют четным битам <tex>x</tex>. Расширение происходит знаково, ввиду чего результат может быть не таким, как ожидалось; при приведении типа к меньшему лишние байты отбрасываютсяЧетные биты результата в обоих случаях равны нулю.
<code>
'''byteint16''' b setBitsNumber(x: '''int16'''): x = -127 <font color (x & 0x5555) + ((x >>> 1) & 0x5555) x = green(x & 0x3333) + ((x >>//10000001 > 2) & 0x3333) x = (-127 / 129x & 0x0F0F)</font+ ((x >>>4) & 0x0F0F) ( '''intreturn'''(x * 0x0101)b <font color = green>//11111111 11111111 11111111 10000001 (-127 / 4294967169)>> 8</fontcode>
====Разворот битов====Чтобы получить биты числа <tex>x</tex>, записанные в обратном порядке, применим следующий алгоритм.<code> <font color = green>// Для чисел других разрядностей нужны соответствующие константы.</font> '''int16'''intreverseBits(x: ''' i int16'''): x = -256 ((x & 0x5555) << 1) | ((x >>> 1) & 0x5555) <font color = green>//11111111 11111111 11111111 00000000 Четные и нечетные биты поменялись местами.</font> x = ((x & 0x3333) << 2) | (-256 (x >>> 2) & 0x3333) <font color = green>// 4294967040)Биты "перетасовываются" группами по два.</font> x = ((x & 0x0F0F) << 4) | (('''byte'''x >>> 4) & 0x0F0F)i <font color = green>//00000000 Биты "перетасовываются" группами по четыре.</font> x = ((0x & 0x00FF)<< 8) | ((x >>> 8) & 0x00FF) <font color = green>// Биты "перетасовываются" группами по восемь.</font> '''return''' x
</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>.
===[[Алгоритм Флойда#Оптимизация с помощью битовых масок | Алгоритм Флойда]]=Примечания=====[[Дерево Фенвика]]===<references/>
==Источники информации==
* [http://www.c-cpp.ru/books/bitovye-operatory Онлайн справочник программиста на С и С++]
* [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]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции ]]
