1632
правки
Изменения
м
x В языке программирования Java существует также оператор беззнакового битового сдвига вправо <tex>>>>< 1; //00001110tex>. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.
#include <iostream '''int32''' abs1(x: '''int32'''): mask = x >> 31 '''return''' (x + mask) '''XOR''' mask '''int32''' abs2(x: '''int32'''): mask = x >>31 '''return''' (x + mask) '''XOR''' mask#include <bitset/code>using namespace std;
int main====Нахождение минимума и максимума из двух чисел без использования условного оператора====Этот способ корректен только если можно утверждать, что величина <tex>(x - y) {</tex> лежит между граничными значениями типа int. short short1 = 16384; bitsetПусть даны числа <tex>x<16/tex> bitset1{short2}; cout и <tex>y< bitset1 /tex> разрядности <tex>n< endl; /tex>. Тогда если <tex>x < y</ 0100000000000000 tex>, то <tex>((x - y) >> (n - 1)) = -1<br/tex> short short3 = short1 , а если <tex>x \geqslant y< 1; bitset/tex>, то <16tex>((x - y) >> bitset3{short3}; // 16384 left(n -shifted by 1 )) = 0</tex>. Выражение <tex>((x - y) \& ((x - y) >> (n -32768 cout 1))</tex> принимает значение <tex>0< bitset3 /tex>, если <tex>x \geqslant y< endl; /tex>, и <tex>(x - y)</ 100000000000000 tex>, если <br/tex> short short4 = short1 x <y< 14;/tex>. bitset<16code> bitset4{short4}; // 4 left'''int32''' min(x, y: '''int32'''): '''return''' y + ((x - y) & ((x -shifted by 14 = 0y) >> 31)) cout << bitset4 << endl; // 000000000000000 '''int32''' max(x, y: '''int32'''):} '''return''' x - ((x - y) & ((x - y) >> 31))
'''''Java'''''====Проверка на то, является ли число степенью двойки====В языке программирования Java существует также оператор беззнакового битового сдвига вправо Пусть дано число <tex>x</tex>. Тогда, если результатом выражения <tex>(x\ \&\&\ !(x\ \&\ (x - 1)))</tex>является единица, то число <tex>x</tex>{{---}} степень двойки. При использовании этого оператора на освободившиеся позиции всегда устанавливаются Правая часть выражения <tex>0(!(x\ \&\ (x - 1)))</tex>будет равна единице, тогда как при использовании только если число <tex>x</tex>равно <tex>0</tex> на освободившиеся позиции устанавливается бит знакаили является степенью двойки.При использовании битовых сдвигов есть некоторое отличие от целочисленного деления на Если число <tex>2x</tex>является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: если сдвигать отрицательное число вправо<tex>1\underbrace{0\dots0}_{n}</tex>, где <tex>n</tex> {{---}} показатель степени. Соответственно, то сначала это аналогично целочисленному делению на выражение <tex>(x - 1)</tex> будет иметь вид <tex>2\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> и необходимо узнать его старший единичный бит.
i 00000000000000000000000000000001 '''int32''' greatestBit(x: '''int32'''): power = 1) <br/> '''for''' i= 1 <tex> \ldots\log_2{32}<29 00100000000000000000000000000000 (536870912) <br/tex>:i<<30 01000000000000000000000000000000 (1073741824) <br/ x |= x >>poweri power <<31 10000000000000000000000000000000 = 1 '''return''' x - (-2147483648/2147483648) <br/x >>i<<32 00000000000000000000000000000001 (1)
i 11111111111111111111111111111111 '''int32''' rotateLeft(-1/4294967295x, d: '''int32''') : '''return''' (x <br/>i< d) | (x >>>1 01111111111111111111111111111111 (214748364732 - d) <br/>) i>>>30 00000000000000000000000000000011 '''int32''' rotateRight(3x, d: '''int32''') <br/>:i '''return''' (x >>>31 00000000000000000000000000000001 d) | (1) x <<br/>i>>>(32 11111111111111111111111111111111 (-1/4294967295d))
i 11111111111111111111111101000000 (-192 <font color = green>//4294967104) Для чисел других разрядностей необходимо использовать соответствующие константы.<br/font>i '''int16''' setBitsNumber(x: '''int16'''): x = x - ((x >>>1 11111111111111111111111110100000 ) & 0x5555) x = (-96/4294967200x & 0x3333) <br/+ ((x >i>>30 11111111111111111111111111111111 2) & 0x3333) x = (x + (-1/4294967295) <br/x >i>>31 11111111111111111111111111111111 4)) & 0x0F0F '''return''' (-1/4294967295x * 0x0101) <br/>i>>32 11111111111111111111111101000000 (-192/4294967104)8
Арифметическое распространение Поскольку <tex>5555_{16}</tex> равно <tex>01010101 01010101_{2}</tex>, результатом операции <tex>x\ \&\ 5555_{16}</tex> является число, в Java проводится перед операциями и гарантирует расширение каждого операнда по крайней мере до intкотором все нечетные биты соответствуют нечетным битам числа <tex>x</tex>. Если же один из операндов longАналогично, то до long. Если сдвигаемая переменная по разрядности меньшерезультатом операции <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>.
byte b <font color = -127; <brgreen>/>b 10000001 (-127/129) Для чисел других разрядностей нужны соответствующие константы.<br/font>(int)b 11111111 11111111 11111111 10000001 '''int16''' reverseBits(-127/4294967169x: '''int16''') <br/>:int i x = -127; <br/>i 11111111 11111111 11111111 10000001 (-127/4294967169(x & 0x5555) <br/< 1) | ((x >>>(byte1)i 10000001 (-127/129& 0x5555) <brfont color = green>//>int i = 128; Четные и нечетные биты поменялись местами.<br/font>i 00000000 00000000 00000000 10000000 x = ((128x & 0x3333) <br/< 2) | ((x >>>(byte2)i 10000000 (-128/128& 0x3333) <brfont color = green>//>int i = 256; Биты "перетасовываются" группами по два.<br/font>i 00000000 00000000 00000001 00000000 x = (256(x & 0x0F0F) <br/< 4) | ((x >>>(byte4)i 00000000 (0& 0x0F0F) <brfont color = green>//>int i = -256; Биты "перетасовываются" группами по четыре.<br/font>i 11111111 11111111 11111111 00000000 x = ((-256/4294967040x & 0x00FF) <br/< 8) | ((x >>>(byte8)i 00000000 (0& 0x00FF) <font color = green>// Биты "перетасовываются" группами по восемь.<br/font> '''return''' x
rollbackEdits.php mass rollback
'''ВНИМАНИЕ, СТАТЬЯ НАХОДИТСЯ В РАЗРАБОТКЕПобитовые операции''' ''(англ. 'Побитовые операции'bitwise operations'' ) — операции, производимые над цепочками битов. Выделяют два типа побитовых операций: [[Определение булевой функции | логические операции ]] и побитовые сдвиги.
==Принцип работы==
===Логические побитовые операции===
Битовые операторы И <tex>(AND, \ \&)</tex>, ИЛИ <tex>(OR, \ \mid)</tex>, НЕ <tex>(NOT, \ \sim)</tex> и исключающее ИЛИ <tex>(XOR,</tex> ^<tex>\ $\textasciicircum$,\ \oplus)</tex> используют те же таблицы истинности, что и их логические эквиваленты.
====Побитовое И====
Побитовое И используется для выключения битов. Любой бит, установленный в <tex>0</tex>, вызывает установку соответствующего бита результата также в <tex>0</tex>.
|||00101000
|}
===Побитовые сдвиги===
Операторы сдвига <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>// 00000110 (6)</font> x = x << 5 <font color = green>// 11000000 (-64)</font> x = x >> 2 <font color = green>// 11110000 (-16)</font></code>
<code> x = 7 <font color = green>// 00000111 (7)</font> x = x << 5; <font color = green>// 11100000 (-32)</font> x = x >>> 2 <font color = green>//1100000000111000 (56)</font></code>
==Применение=====Сложные операции=======Определение знака числа====Пусть дано число <tex>x </tex>. Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа <tex> 2; x</tex> можно определить, выполнив сдвиг вправо на всю длину переменной:<code> '''int32''' getSign(x: '''int32'''): '''if''' x != 0: mask = 1 '''else''': mask = 0 '''return''' mask | (x >> 31) <font color = green>// результатом будет -1, 0, или +1 // для отрицательного, равного нулю и положительного числа x соответственно</00110000font>
</code>
Используя побитовые операции можно также узнать, различны ли знаки двух переменных <tex>x</tex> и <tex>y</tex>. Если числа имеют различный знак, то результат операции XOR, произведенной над их знаковыми битами, будет единицей. Поэтому неравенство <tex>(x \oplus y) < 0</tex> будет верно в том случае, если числа <tex>x</tex> и <tex>y</tex> разного знака.
====ОграниченияВычисление модуля числа без использования условного оператора===='''''C++ Visual Studio 15'''''Пусть дано число <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>
</code>
Рассмотрим некоторое число, представим его как <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> будет число, состоящее только из старшего бита исходного числа.
<code>
</code>
====Циклический сдвиг====
Пусть дано число <tex>x</tex> и надо совершить циклический сдвиг его битов на величину <tex>d</tex>.
Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на <tex>d</tex> и в противоположном направлении на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.
<code>
</code>
====Подсчет количества единичных битов====
Для подсчета количества единичных битов в числе <tex>x</tex> можно воспользоваться следующим алгоритмом:
<code>
</code>
Аналогично, число <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>
'''int16''' setBitsNumber(x: '''int16'''):
x = (x & 0x5555) + ((x >>> 1) & 0x5555)
x = (x & 0x3333) + ((x >>> 2) & 0x3333)
x = (x & 0x0F0F) + ((x >>> 4) & 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</tex>, записанные в обратном порядке, применим следующий алгоритм.
<code>
</code>
Более подробно про то, что за константы выбраны для данного алгоритма, можно прочитать в разделе [[Побитовые_операции#Подсчет_количества_единичных_битов | подсчет количества единичных битов]]. ===Применение для решения задач===*'''''Проверка на то, является ли число степенью двойки====Работа с битовыми масками====Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее:'''''найти дополнение <tex>(\sim mask)<br/tex>Если выражение , пересечение <tex>(xmask_1\ \&\ (x - 1)mask_2)</tex> равно нулю, то число объединение <tex>x(mask_1 \mid mask_2)</tex> является степенью двойки множеств, установить бит по номеру <tex>(mask \mid (1\ \texttt{<<}\ x \not= 0))</tex>.*'''''Проверка на то, что в битовой записи числа нет двух единиц, идущих подряд:'''''<br/>Если выражение снять бит по номеру <tex>(xmask\ \&\ \sim(1\ \texttt{<<}\ x \ll 1))</tex> равно нулю. Битовые маски используются, например, то в битовой записи числа при решении некоторых задач<texref>x[[Гамильтоновы графы #Задача о коммивояжере| Динамическое программирование по подмножествам (по маскам)]]</texref> нет двух единиц, идущих подряд[[Динамическое программирование | динамического программирования]].*====Алгоритм Флойда===={{main|Алгоритм Флойда}}'''Алгоритм Флойда–Уоршелла''Номер младшего единичного бита:'(англ. ''the Floyd–Warshall algorithm''<br/>Число) {{---}} алгоритм для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, полученное если в результате операции графе нет циклов отрицательной величины, а если же такой цикл есть, позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма <tex>x\ \&\ Theta(\sim x + 1n^3)</tex> будет равно номеру младшего единичного бита в числе , также требует <tex>x\Theta(n^2) </tex>памяти.*====Дерево Фенвика===={{main|Дерево Фенвика}}'''Дерево Фенвика''Работа с битовыми масками:'(англ. ''Binary indexed tree''<br/>Храним подмножества множества из ) {{---}} структура данных, которая может выполнять следующие операции:* изменять значение любого элемента в массиве,* выполнять некоторую [[Ассоциативная_операция |ассоциативную]], [[Абелева_группа |коммутативную]], [[Группа |обратимую операцию]] <tex>32, 64\circ </tex> или на отрезке <tex>128[i, j] </tex> фиксированных элементов. Значение каждого бита позволяет понять, включен элемент в множество или нет. Тогда легко сделать следующее: найти дополнение Данная структура требует <tex>O(\simn)</tex>памяти, пересечение а выполнение каждой операции происходит за <tex>O(\&log n)</tex>. Функция, объединение позволяющая делать операции вставки и изменения элемента за <tex>O(\midlog n)</tex> множеств, установить бит по номеру задается следующей формулой <tex>F(i) = (i \mid And (i + 1 \ll x))</tex>, снять бит по номеру .Пусть дан массив <tex>(A = [a_0, a_1, \& \sim(ldots, a_{n - 1 \ll x))}]</tex>.*'''''[[Алгоритм Флойда]]''''': Деревом Фенвика называется массив <tex> T </tex> из <tex> n <br/tex>Оптимизация с помощью битовых масок. Время работы элементов: <tex>OT_i = \Big(sum\dfraclimits_{nk = F(i)}^3}{ki}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алгоритмы]][[Категория: подводные камниБулевы функции ]]
