Изменения

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

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

4194 байта добавлено, 16:13, 3 января 2019
→‎Нахождение минимума и максимума из двух чисел без использования условного оператора
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> можно определить, выполнив сдвиг вправо на всю длину переменной:<code> '''int32''' 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> разного знака.
'''Способ 1'''====Вычисление модуля числа без использования условного оператора====Рассмотрим некоторое Пусть дано число, представим его как <tex>0\dots01b \dots bx</tex>, где . Если <tex>bx</tex> {{---}} любое значение бита. Тогдаположительно, если совершить битовый сдвиг этого числа вправо на то <tex>1mask = 0</tex> , и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим результат <tex>0(x + mask) \dots011b \dots boplus mask = x</tex>. Если мы повторим эту последовательность действий над полученным числомВ случае, но устроим сдвиг на если <tex>2x</tex>отрицательно, то получим <tex>0\dots01111b \dots bmask = -1</tex>. При каждой следующей операции будем увеличивать модуль сдвига до следующей степени двойки. После некоторого количества таких операций (зависит от разрядности числа) Тогда получается, что мы получим число вида работаем с числом <tex>0\dots01\dots1x</tex>. Тогда результатом выполнения действий так, как будто оно представлено в [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код #Код со сдвигом |коде со сдвигом]] с тем отличием, что у нас знаковый бит принимает значение <tex>x - (x \texttt{ 1</tex>для отрицательных чисел, а <tex> }1)0</tex> будет число, состоящее только из старшего бита исходного числа{{---}} для положительных.
<code>
'''intint32''' power = 1 abs1(x: '''forint32''' i = 1..<tex>\log_2{n}</tex>): <font color mask = greenx >// n {{---}} разрядность числа</font>31 '''return''' (x |+ mask) '''XOR''' mask '''int32''' abs2(x: '''int32'''): mask = x >> power31 power <<= 1 result = x - '''return''' (x >> 1+ mask)'''XOR''' mask
</code>
'''Способ 2'''====Нахождение минимума и максимума из двух чисел без использования условного оператора==== Способ основан на [[Целочисленный двоичный поиск | бинпоиске]]. Будем искать максимальную степень двойкиЭтот способ корректен только если можно утверждать, меньшую числа что величина <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>
'''intint32''' min(x, m <font color = green>// x {{---}} исходное число</font> y: '''intint32''' l = n <font color = green>// n {{---}} разрядность числа</font>): '''intreturn''' r = y + ((x - y) & ((x -1y) >> 31)) '''whileint32''' r < l - 1max(x, y: m = (l + r) / 2 '''ifint32''' (1 << m) <tex>\leqslant</tex> x: r = m '''elsereturn''': l = m result = rx - ((x - y) & ((x - y) >> 31))
</code>
 
====Проверка на то, является ли число степенью двойки====
Пусть дано число <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> и необходимо узнать его младший единичный бит. Задачу можно решить несколькими способами. '''Способ 1'''
Применим к числу <tex>x</tex> побитовое отрицание, чтобы инвертировать значения всех его бит, а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом <tex>x</tex>, а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа <tex>(x\ \&\ (\sim x + 1))</tex>.
К такому же результату можно прийти, если сначала отнять от числа <tex>x</tex> единицу, чтобы обнулить его младший единичный бит, а все последующие разряды обратить в <tex>1</tex>, затем инвертировать результат и применить побитовое И с исходным числом <tex>(x\ \&\ \sim (x - 1))</tex>.
'''Способ 2''' Алгоритм аналогичен описанному выше способу нахождения ====Нахождение старшего единичного бита и также основан на [[Целочисленный двоичный поиск | бинпоиске]]. Будем искать максимальное ====Пусть дано число вида <tex>0\dots01\dots1x</tex> такое, что и необходимо узнать его побитовое И с числом <tex>x</tex> дает <tex>0</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> будет число, состоящее только из старшего бита исходного числа.
<code>
'''intint32''' greatestBit(x, m <font color = green>// x {{---}} исходное число</font> : '''intint32''' l = n <font color = green>// n {{---}} разрядность числа</font> '''int''' r = -1 '''while''' r < l - 1): m power = (l + r) / 21 '''iffor''' ((i = 1 <tex> \ldots\log_2{32}< m) - 1) & /tex>: x |== 0:x >> power r power <<= m1 '''elsereturn''': l = m result = rx - (x >> 1)
</code>
====Подсчет количества единичных битовЦиклический сдвиг===='''Способ 1'''Пусть дано число <tex>x</tex> и надо совершить циклический сдвиг его битов на величину <tex>d</tex>.Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на <tex>d</tex> и в противоположном направлении на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.
Самый простой способ посчитать количество единичных битов в числе <tex>x</tex> {{---}} сдвигать его на <tex>1</tex> вправо до тех пор, пока оно не станет равно нулю и в процессе смотреть на последний бит.
<code>
'''intint32''' answer = 0rotateLeft(x, d: '''int32'''): '''return''' (x << d) | (x >>> (32 - d)) '''whileint32''' rotateRight(x != 0, d: '''int32'''): answer += x & 1 '''return''' (x >> 1> d) | (x << (32 - d))
</code>
'''Способ 2'''
 
Пусть мы хотим посчитать количество единичных битов в числе <tex>x</tex>. Если вычесть из <tex>x</tex> единицу, то его младший единичный бит обнулится, а все последующие за ним биты примут значение <tex>1</tex>. Если произвести операцию побитового И между <tex>x</tex> и <tex>(x - 1)</tex>, то мы получим число, побитово равное <tex>x</tex> во всех позициях, кроме младшего единичного бита <tex>x</tex> (в результирующем числе он будет нулевым). Таким образом, количество совершенных операций до того момента, как исходное число обратится в ноль, будет равно количеству единичных битов в нём.
====Подсчет количества единичных битов====
Для подсчета количества единичных битов в числе <tex>x</tex> можно воспользоваться следующим алгоритмом:
<code>
<font color = green>// Для чисел других разрядностей необходимо использовать соответствующие константы.</font> '''intint16''' answer = 0 setBitsNumber(x: '''whileint16''' x != 0): x &= x - ((x >>> 1) & 0x5555) answerx = (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</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>.
Аналогично, число <codetex> '''int''' head, tail head = x 3333_{16}</tex> равно < a tex>00110011 00110011_{2}<font color /tex> и операция <tex>x = green>// (x \ \&\ 3333_{16}) + (x\ \texttt{--->>>}\ 2\ \&\ 3333_{16} изменяемое число )</tex>, примененная к результату, полученному на первом этапе, выполняет подсчет количества единичных битов в блоках по <tex>4</ a tex>. В свою очередь, число <tex>\texttt{0F0F}_{---16}</tex> равно <tex>00001111 00001111_{2} число позиций, на которое хотим выполнить сдвиг</fonttex> '''if''' a != 0: tail и операция <tex>x = (x\ \&\ \texttt{0F0F}_{16}) + (x \ \texttt{>> (n - a) <font color = green>// n }\ 4\ \&\ \texttt{0F0F}_{---16}} разрядность числа x)</fonttex> '''else''': tail = 0 result = head | tailпозволяет подсчитать число единичных бит в блоках по <tex>8</codetex>.
====Разворот битов====Чтобы получить биты Теперь необходимо просуммировать числа , записанные в блоках по <tex>x8</tex>битов, записанные в обратном порядкечтобы получить искомую величину. Это можно сделать, будем снимать значение младшего бита, умножать его домножив результат на <tex>0101_{16}</tex> <tex>(1 00000001_{2})</tex>. Ответ на старшую незаписанную степень двойки и сдвигать число задачу будет находиться в первых восьми битах произведения. Выполнив сдвиг вправо на единицу <tex>8</tex> (для обработки следующих битшестнадцатибитных чисел), мы получим долгожданный ответ.
Подведем итог:
<code>
result = 0 position = 1 << '''int16''' setBitsNumber(n - 1) <font color = green>// n {{---}} разрядность числа x</font> : '''whileint16''' x != 0): result +x = (x & 0x5555) + ((x >>> 1) * position& 0x5555) position x = (x & 0x3333) + ((x >>>2) & 0x3333) x = 1(x & 0x0F0F) + ((x >>> 4) & 0x0F0F) '''return''' (x * 0x0101) >>>= 18
</code>
====Проверка на тоЗаметим, является ли число степенью двойки====Пусть дано число что операция <tex>x</tex>. Тогда, если результатом выражения <tex>(x\ \&\&\ !55_{16} + (x\ \&\ (x - 1)))</textexttt{> является единица, то число <tex>x</tex> {{---}} степень двойки. Правая часть выражения <tex>(!(x\ 1)\ \&\ (x - 1)))55_{16}</tex> будет равна единице только если число равносильна операции <tex>x</tex> равно <tex>0</tex> или является степенью двойки. Если число <tex>- (x</tex> является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: <tex>1\underbrace{0\dots0}_texttt{n}</tex>, где <tex>n</tex> {{---}} показатель степени. Соответственно, выражение <tex>(x - \ 1)</tex> будет иметь вид <tex>\underbrace{1\dots1}_&\ 55_{n16}</tex>, и <tex>x\ \&\ (x - 1)</tex> равно <tex>0</tex>в чем легко убедиться, рассмотрев все числа из двух бит.
Операция логического И в данном выражении отсекает тот случайВ свою очередь, когда операцию <tex>(x = 0\ \&\ \texttt{0F0F}_{16}) + ((x\ \texttt{>>>}\ 4)\ \&\ \texttt{0F0F}_{16})</tex> и не является степенью двойки, но при этом правая часть можно заменить на <tex>(!x + (x\ \&texttt{>>>}\ (x - 1)4))\ \&\ \texttt{0F0F}_{16}</tex> равна единице. Эта замена не повлияет на результат, так как максимальное значение в любой группе из четырех битов данного числа равно четырем, то есть требует только трех битов для записи, и выполнение суммирования не повлечет за собой переполнения и выхода за пределы четверок.
====Определение знака числа====Пусть дано число <tex>x</tex>. Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знакаТаким образом, знак числа <tex>x</tex> можно определитьмы получили код, выполнив сдвиг вправо на всю длину переменной:<code> <font color = green>// n {{---}} разрядность числа</font> '''if''' x != 0 mask = 1 '''else''' mask = 0 sign = mask | (x >> (n - 1)) <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>
<font color = green>// n {{---}} разрядность числаДля чисел других разрядностей нужны соответствующие константы.</font> mask '''int16''' reverseBits(x: '''int16'''): x = ((x & 0x5555) << 1) | ((x >> n - > 1) & 0x5555) <font color = green>// Четные и нечетные биты поменялись местами.</font> abs x = ((x + mask& 0x3333) <tex< 2) | ((x >>\oplus> 2) & 0x3333) <font color = green>// Биты "перетасовываются" группами по два.</texfont> mask x = ((x & 0x0F0F) << 4) | ((x >>> 4) & 0x0F0F) <font color = green>// другой способ сделать то же самое:Биты "перетасовываются" группами по четыре.</font> abs x = ((x & 0x00FF) << 8) | ((x >>> 8) & 0x00FF) <texfont color = green>\oplus// Биты "перетасовываются" группами по восемь.</texfont> mask) - mask '''return''' x
</code>
====Нахождение минимума и максимума из двух чисел без использования условного оператора====Этот способ корректен только если можно утверждатьБолее подробно про то, что величина <tex>(x - y)</tex> лежит между граничными значениями типа int. Пусть даны числа <tex>x</tex> и <tex>y</tex>. Тогдаза константы выбраны для данного алгоритма, если <tex>x < y</tex>, то <tex>((x - y) \texttt{>>} (n - 1)) = -1</tex> а если <tex>x \geqslant y</tex>, то <tex>((x - y) \texttt{>>} (n - 1)) = 0</tex>. Выражение <tex>((x - y) \& ((x - y) \texttt{>>} (n - 1))</tex> принимает значение <tex>0</tex>, если <tex>x \geqslant y</tex> и <tex>(x - y)</tex>, если <tex>x < y</tex>можно прочитать в разделе [[Побитовые_операции#Подсчет_количества_единичных_битов | подсчет количества единичных битов]].<code> <font color = green>// n {{---}} разрядность чисел</font> min = y + ((x - y) & ((x - y) >> (n - 1))) max = x - ((x - y) & ((x - y) >> (n - 1)))</code>
===Применение для решения задач===
====Алгоритм Флойда====
{{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> F(i) </tex> — функция, которую мы определили ранее.
 
==См. также==
* [[Определение булевой функции]]
* [[Сумматор]]
* [[Триггеры]]
==Примечания==
* [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]
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Булевы функции ]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/52613...68141»

Навигация