Изменения

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

Битовые операторы И <tex>(AND, \ \&)</tex>, ИЛИ <tex>(OR, \ \mid)</tex>, НЕ <tex>(NOT, \ \sim)</tex> и исключающее ИЛИ <tex>(XOR,</tex> ^<tex>\ $\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>. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули. <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)</font></code> ==Применение=====Сложные операции=======Определение знака числа====Пусть дано число <tex>x</tex>. Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа <tex>x</tex> можно определить, выполнив сдвиг вправо на всю длину переменной:

'''int32''' getSign(x : '''int32'''): '''if''' x != 7; 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</00000111tex> разного знака.

====Вычисление модуля числа без использования условного оператора====Пусть дано число <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</00001110code>

====Нахождение минимума и максимума из двух чисел без использования условного оператора====Этот способ корректен только если можно утверждать, что величина <tex>(x - y)<< 5; //11000000tex> лежит между граничными значениями типа int.

Пусть даны числа <tex>x</tex> и <tex>y</tex> разрядности <tex>n</tex>. Тогда если <tex>x < y</tex>, то <tex>((x - y) >> 2; (n - 1)) = -1</tex>, а если <tex>x \geqslant y</00110000tex>, то <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> '''int32''' min(x, y: '''int32'''): '''return''' y + ((x - y) & ((x - y) >> 31)) '''int32''' max(x, y: '''int32'''): '''return''' x - ((x - y) & ((x - y) >> 31))

C++ Visual Studio 15====Проверка на то, является ли число степенью двойки====Пусть дано число <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> будет число, состоящее только из старшего бита исходного числа.

#include '''int32''' greatestBit(x: '''int32'''): power = 1 '''for''' i = 1 <tex> \ldots\log_2{32}</tex>: x |= x >> power power <<= 1 '''return''' x - (x >> 1)<iostream/code>#include ====Циклический сдвиг====Пусть дано число <tex>x</tex> и надо совершить циклический сдвиг его битов на величину <tex>d<bitset/tex>.using namespace std;Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на <tex>d</tex> и в противоположном направлении на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.

int main() { short short1 = 16384; bitset<16code> bitset1{short2}; cout << bitset1 << endl; // 0100000000000000 <br/>'''int32''' rotateLeft(x, d: '''int32'''): short short3 = short1 '''return''' (x << 1; bitset<16d) | (x >>> bitset3{short3}; // 16384 left(32 -shifted by 1 = -32768d)) cout << bitset3 << endl; // 100000000000000 <br/> short short4 = short1 << 14; '''int32''' rotateRight(x, d: '''int32'''): bitset<16 '''return''' (x >>> bitset4{short4}; // 4 left-shifted by 14 = 0 cout d) | (x << bitset4 << endl; // 000000000000000 }(32 - d))

==Применение для решения задач==Подсчет количества единичных битов====Для подсчета количества единичных битов в числе <tex>x</tex> можно воспользоваться следующим алгоритмом:<code> <font color = green>// Для чисел других разрядностей необходимо использовать соответствующие константы.</font> * '''int16'''Проверка на то, является ли число степенью двойкиsetBitsNumber(x:'''int16'''): x = x - ((x >>> 1) & 0x5555) x = (x & 0x3333) + ((x >>> 2) & 0x3333) x = (x + (x >>> 4)) & 0x0F0F '''return''' (x * 0x0101) >>> 8</code> Поскольку <tex>5555_{16}</tex> равно <tex>01010101 01010101_{2}</tex>, результатом операции <tex>x\ \&\ 5555_{16}</tex> является число, в котором все нечетные биты соответствуют нечетным битам числа <tex>x<br/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>x\texttt{0F0F}_{16}</tex> равно <tex>00001111 00001111_{2}</tex> является степенью двойки и операция <tex>x = (x\ \&\ \texttt{0F0F}_{16}) + (x \not= 0\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<br/code>Если выражение  Заметим, что операция <tex>x\ \&\ 55_{16} + (x\ \texttt{>>>}\ 1)\ \&\ 55_{16}</tex> равносильна операции <tex>x - (x \ll \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> <font color = green>// Для чисел других разрядностей нужны соответствующие константы.</font>* '''int16''' reverseBits(x: '''int16'''Номер младшего единичного бита): x = ((x & 0x5555) << 1) | ((x >>> 1) & 0x5555) <font color = green>// Четные и нечетные биты поменялись местами.</font> x = ((x & 0x3333) << 2) | ((x >>> 2) & 0x3333) <font color = green>// Биты "перетасовываются" группами по два.</font> x = ((x & 0x0F0F) << 4) | ((x >>> 4) & 0x0F0F) <font color = green>// Биты "перетасовываются" группами по четыре.</font> x = ((x & 0x00FF) << 8) | ((x >>> 8) & 0x00FF) <font color = green>// Биты "перетасовываются" группами по восемь.</font> '''return'''x<br/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{<<}\sim x ))</tex>. Битовые маски используются, например, при решении некоторых задач<ref>[[Гамильтоновы графы #Задача о коммивояжере| Динамическое программирование по подмножествам (по маскам)]]</ref> [[Динамическое программирование | динамического программирования]]. ====Алгоритм Флойда===={{main|Алгоритм Флойда}}'''Алгоритм Флойда–Уоршелла''' (англ. ''the Floyd–Warshall algorithm'') {{---}} алгоритм для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а если же такой цикл есть, позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма <tex> \Theta(n^3) </tex>, также требует <tex> \Theta(n^2) </tex> памяти. ====Дерево Фенвика===={{main|Дерево Фенвика}}'''Дерево Фенвика''' (англ. ''Binary indexed tree'') {{---}} структура данных, которая может выполнять следующие операции:* изменять значение любого элемента в массиве,* выполнять некоторую [[Ассоциативная_операция |ассоциативную]], [[Абелева_группа |коммутативную]], [[Группа |обратимую операцию]] <tex> \circ </tex> на отрезке <tex> [i, j] </tex>. Данная структура требует <tex> O(n) </tex> памяти, а выполнение каждой операции происходит за <tex> O(\log n) </tex> . Функция, позволяющая делать операции вставки и изменения элемента за <tex> O(\log n) </tex>, задается следующей формулой <tex> F(i) = (i \And (i + 1)) </tex>.Пусть дан массив <tex> A = [a_0, a_1, \ldots, a_{n - 1}]</tex> будет равно номеру младшего единичного бита в числе . Деревом Фенвика называется массив <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>xF(i) </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]

[https[Категория://msdn.microsoft.com/ru-ru/library/336xbhcz.aspx| MSDNДискретная математика и алгоритмы]][[Категория: Операторы сдвигов влево и вправоБулевы функции ]]