Изменения

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

Битовые операторы И <tex>(AND, \ \&)</tex>, ИЛИ <tex>(OR, \ \mid)</tex>, НЕ <tex>(NOT, \ \sim)</tex> и исключающее ИЛИ <tex>(XOR, \ $\textasciicircum$, \ \oplus)</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>// 00000110 (6)</font> x = x << 5 <font color = green>// 11000000 (-64)</font> x = x >> 2 <font color = green>// 11110000 (-16)</font></code> В языке программирования Java существует также оператор беззнакового битового сдвига вправо <tex>>>></tex>. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули. 

x = 7 <font color = green>//00000111(7)</font> x = x << 1 5 <font color = green>//0000111011100000 (-32)</font> x << 5 = x >>> 2 <font color = green>//1100000000111000 (56)</font></code> ==Применение=====Сложные операции=======Определение знака числа====Пусть дано число <tex>x</tex>. Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа <tex>x</tex> можно определить, выполнив сдвиг вправо на всю длину переменной:<code> '''int32''' getSign(x: '''int32'''): '''if''' x != 0: mask = 1 '''else''': mask = 0 '''return''' mask | (x >> 2 31) <font color = green>//00110000результатом будет -1, 0, или +1 // для отрицательного, равного нулю и положительного числа x соответственно</font>

====ОграниченияВычисление модуля числа без использования условного оператора====Пусть дано число <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: ''C'int32'''): mask = x >> 31 '''return''' (x +mask) '''XOR''' mask '''int32''' abs2(x: '''int32'''): mask = x >> 31 '''return''' (x + Visual Studio 15mask) '''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>.

'''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> равна единице.

В языке программирования Java существует также оператор беззнакового битового сдвига вправо ====Нахождение младшего единичного бита====Пусть дано число <tex>\gggx</tex>. При использовании этого оператора на освободившиеся позиции всегда устанавливаются <tex>0</tex>, тогда как при использовании <tex>\gg</tex> на освободившиеся позиции устанавливается и необходимо узнать его младший единичный бит знака.

При использовании битовых сдвигов есть некоторое отличие от целочисленного деления на Применим к числу <tex>2x</tex>: если сдвигать отрицательное число вправопобитовое отрицание, то сначала это аналогично целочисленному делению на <tex>2</tex>чтобы инвертировать значения всех его бит, но когда останется а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом <tex>-1x</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>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>. Четные биты результата в Java проводится перед операциями и гарантирует расширение каждого операнда обоих случаях равны нулю. Мысленно разобьем двоичную запись нашего числа <tex>x</tex> на группы по крайней мере до int <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> (для шестнадцатибитных чисел), мы получим долгожданный ответ. Подведем итог:''

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

'''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>. Эта замена не повлияет на результат, так как максимальное значение в любой группе из четырех битов данного числа равно четырем, то есть требует только трех битов для записи, и выполнение суммирования не повлечет за собой переполнения и выхода за пределы четверок.

====Разворот битов====Чтобы получить биты числа <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

Более подробно про то, что за константы выбраны для данного алгоритма, можно прочитать в разделе [[Побитовые_операции#Подсчет_количества_единичных_битов | подсчет количества единичных битов]]. ===Применение для решения задач===*'''''Проверка на то, является ли число степенью двойки'''''*:Если выражение <tex>(x\ \&\ (x - 1))</tex> равно нулю, то число <tex>x</tex> является степенью двойки <tex>(x \not= 0)</tex>.*'''''Проверка на то, что в битовой записи числа нет двух единиц, идущих подряд'''''*:Если выражение <tex>(x\ \&\ (x \ll 1))</tex> равно нулю, то в битовой записи числа <tex>x</tex> нет двух единиц, идущих подряд.*'''''Номер младшего единичного бита'''''*:Число, полученное в результате операции <tex>x\ \&\ (\sim x + 1)</tex> будет равно номеру младшего единичного бита в числе <tex>x</tex>.*'''''===Работа с битовыми масками'''''====*:Храним подмножества множества из <tex>32, 64</tex> или <tex>128</tex> фиксированных элементовДля работы с подмножествами удобно использовать битовые маски. Значение каждого бита позволяет понять, включен элемент в множество или нет. Тогда Применяя побитовые операции легко сделать следующее: найти дополнение <tex>(\sim mask)</tex>, пересечение <tex>(mask_1\ \&\ mask_2)</tex>, объединение <tex>(mask_1 \mid mask_2)</tex> множеств, установить бит по номеру <tex>(mask \mid (1 \ll \texttt{<<}\ x))</tex>, снять бит по номеру <tex>(mask\ \&\ \sim(1 \ll \texttt{<<}\ x))</tex>.*'''''Определение знака числа'''''Битовые маски используются, например, при решении некоторых задач<coderef> sign = (v != 0) [[Гамильтоновы графы #Задача о коммивояжере| -Динамическое программирование по подмножествам ('''int''')(('''unsigned int''')(('''int''')vпо маскам) ]]</ref>> (''sizeof''('''int''') * CHAR_BIT - 1));[[Динамическое программирование | динамического программирования]]. // Or, for more speed but less portability: sign = (v != 0) ==Алгоритм Флойда===={{main| (v >> (Алгоритм Флойда}}''sizeof'Алгоритм Флойда–Уоршелла'(''(англ. 'int'the Floyd–Warshall algorithm'') * CHAR_BIT {{-- 1)); // -1, 0, or +1}} // Orалгоритм для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, for portabilityесли в графе нет циклов отрицательной величины, brevityа если же такой цикл есть, and (perhaps) speed: sign = (v позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма <tex> 0) - \Theta(v < 0n^3); // -1, 0, or +1</codetex>*'''''Кодирование информации''''', также требует <codetex> \Theta(n^2) <font color = green>// метод для шифровки текста с помощью XOR</fonttex>памяти. '''function''' encode(secret: '''string''', key: '''string'''): '''byte[]''' btxt = secret.''getBytes'' bkey = key.''getBytes''==Дерево Фенвика==== {{main|Дерево Фенвика}} '''forДерево Фенвика''' i = 0 .. btxt(англ.''lengthBinary indexed tree'') {{---}} структура данных, которая может выполнять следующие операции: result* изменять значение любого элемента в массиве,* выполнять некоторую [[Ассоциативная_операция |ассоциативную]], [i[Абелева_группа |коммутативную]] = (btxt, [[iГруппа |обратимую операцию]] <tex>\opluscirc </tex> bkeyна отрезке <tex> [i % bkey, j] </tex>.''length'']) ''as'' '''byte''' Данная структура требует '''return''' result<tex> O(n) </tex> памяти, а выполнение каждой операции происходит за <tex> O(\log n) </tex> .

Функция, позволяющая делать операции вставки и изменения элемента за <font color = greentex>O(\log n) <// метод для расшифровки текстаtex>, задается следующей формулой </fonttex> '''function''' decodeF(secret: '''byte[]''', key: '''string'''i): '''string''' bkey = key(i \And (i + 1)) </tex>.''getBytes'' '''for''' i Пусть дан массив <tex> A = 0 [a_0, a_1, \ldots, a_{n - 1}]</tex>.. secret.''length'' Деревом Фенвика называется массив <tex> T </tex> из <tex> n </tex> элементов: result[i] <tex> T_i = \sum\limits_{k = F(secret[i] )}^{i} a_k</tex>, где <tex>i = 0\oplusldots n - 1 </tex> bkey[и <tex> F(i % bkey.''length'']) ''as'' '''byte''' '''return''' result ''as'' '''string'''</codetex>*'''''[[Алгоритм Флойда]]'''''*:Оптимизация с помощью битовых масок— функция, которую мы определили ранее.*'''''[[Дерево Фенвика]]'''''

* [[Определение булевой функции]]* [[Сумматор]]* [[Триггеры]] ==Примечания==<references/>

* [http://www.c-cpp.ru/books/bitovye-operatory Онлайн справочник программиста на С и С++]* [http://developer.alexanderklimov.ru/android/java/bitwise.php Побитовые операторы]* [https://msdngraphics.microsoftstanford.comedu/~seander/bithacks.html Bit Twiddling Hacks by Sean Eron Anderson]* [https://habrahabr.ru-ru/librarypost/93172/336xbhcz.aspx MSDN: Операторы сдвигов влево и вправоHabrahabr {{---}} Алгоритмы поиска старшего бита] * [httphttps://dark-barkeryesteapea.blogspotwordpress.rucom/2013/201203/03/bitcounting-the-number-of-set-bits-in-an-integer/ STP's blog {{-operations-java-pitfalls.html Битовые сдвиги и приведения в Java: подводные камни}} Counting the number of set bits in an integer]

[http[Категория://developer.alexanderklimov.ru/android/java/bitwise.php Побитовые операторыДискретная математика и алгоритмы]][[Категория: Булевы функции ]]