Побитовые операции — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вычисление модуля числа без использования условного оператора)
м (rollbackEdits.php mass rollback)
 
(не показано 45 промежуточных версий 7 участников)
Строка 44: Строка 44:
  
 
===Побитовые сдвиги===
 
===Побитовые сдвиги===
Операторы сдвига <tex>\texttt{<<}</tex> и <tex>\texttt{>>}</tex> сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код #Дополнительный код (дополнение до двух) | двоичном дополнительном коде]] и необходимо поддерживать знаковый бит).
+
Операторы сдвига <tex><<</tex> и <tex>{>>}</tex> сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код #Дополнительный код (дополнение до двух) | двоичном дополнительном коде]] и необходимо поддерживать знаковый бит).
  
 
Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.
 
Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.
Строка 55: Строка 55:
 
</code>
 
</code>
  
В языке программирования Java существует также оператор беззнакового битового сдвига вправо <tex>\texttt{>>>}</tex>. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.
+
В языке программирования Java существует также оператор беззнакового битового сдвига вправо <tex>>>></tex>. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.
  
 
<code>
 
<code>
 
  x = 7          <font color = green>// 00000111 (7)</font>
 
  x = 7          <font color = green>// 00000111 (7)</font>
 
  x = x << 5    <font color = green>// 11100000 (-32)</font>
 
  x = x << 5    <font color = green>// 11100000 (-32)</font>
  x = x >> 2     <font color = green>// 00111000 (56)</font>
+
  x = x >>> 2   <font color = green>// 00111000 (56)</font>
 
</code>
 
</code>
  
 
==Применение==
 
==Применение==
 
===Сложные операции===
 
===Сложные операции===
====Нахождение старшего единичного бита====
+
====Определение знака числа====
'''Способ 1'''
+
Пусть дано число <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> разного знака.
  
Рассмотрим некоторое число, представим его как <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> будет число, состоящее только из старшего бита исходного числа.
+
====Вычисление модуля числа без использования условного оператора====
 +
Пусть дано число <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>
  '''int''' power = 1
+
  '''int32''' abs1(x: '''int32'''):
'''for''' i = 1..<tex>\log_2{n}</tex>:   <font color = green>// n {{---}} разрядность числа</font>
+
    mask = x >> 31
     x |= x >> power
+
     '''return''' (x + mask) '''XOR''' mask
     power <<= 1
+
result = x - (x >> 1)
+
'''int32''' abs2(x: '''int32'''):
 +
    mask = x >> 31
 +
     '''return''' (x + mask) '''XOR''' mask
 
</code>
 
</code>
  
'''Способ 2'''
+
====Нахождение минимума и максимума из двух чисел без использования условного оператора====
 
+
Этот способ корректен только если можно утверждать, что величина <tex>(x - y)</tex> лежит между граничными значениями типа int.
Способ основан на [[Целочисленный двоичный поиск | бинпоиске]]. Будем искать максимальную степень двойки, меньшую числа <tex>x</tex>.
 
  
 +
Пусть даны числа <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>
 
<code>
  '''int''' x, m    <font color = green>// x {{---}} исходное число</font>
+
  '''int32''' min(x, y: '''int32'''):
'''int''' l = n    <font color = green>// n {{---}} разрядность числа</font>
+
    '''return''' y + ((x - y) & ((x - y) >> 31))
'''int''' r = -1
+
  '''while''' r < l - 1:
+
  '''int32''' max(x, y: '''int32'''):
    m = (l + r) / 2
+
     '''return''' x - ((x - y) & ((x - y) >> 31))
    '''if''' (1 << m) <tex>\leqslant</tex> x:
 
        r = m
 
     '''else''':
 
        l = m
 
result = r
 
 
</code>
 
</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> равна единице.
  
 
====Нахождение младшего единичного бита====
 
====Нахождение младшего единичного бита====
'''Способ 1'''
+
Пусть дано число <tex>x</tex> и необходимо узнать его младший единичный бит.
  
 
Применим к числу <tex>x</tex> побитовое отрицание, чтобы инвертировать значения всех его бит, а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом <tex>x</tex>, а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа <tex>(x\ \&\ (\sim x + 1))</tex>.
 
Применим к числу <tex>x</tex> побитовое отрицание, чтобы инвертировать значения всех его бит, а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом <tex>x</tex>, а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа <tex>(x\ \&\ (\sim x + 1))</tex>.
Строка 101: Строка 118:
 
К такому же результату можно прийти, если сначала отнять от числа <tex>x</tex> единицу, чтобы обнулить его младший единичный бит, а все последующие разряды обратить в <tex>1</tex>, затем инвертировать результат и применить побитовое И с исходным числом <tex>(x\ \&\ \sim (x - 1))</tex>.
 
К такому же результату можно прийти, если сначала отнять от числа <tex>x</tex> единицу, чтобы обнулить его младший единичный бит, а все последующие разряды обратить в <tex>1</tex>, затем инвертировать результат и применить побитовое И с исходным числом <tex>(x\ \&\ \sim (x - 1))</tex>.
  
'''Способ 2'''
+
====Нахождение старшего единичного бита====
 
+
Пусть дано число <tex>x</tex> и необходимо узнать его старший единичный бит.
Алгоритм аналогичен описанному выше способу нахождения старшего единичного бита и также основан на [[Целочисленный двоичный поиск | бинпоиске]]. Будем искать максимальное число вида <tex>0\dots01\dots1</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>
 
<code>
  '''int''' x, m    <font color = green>// x {{---}} исходное число</font>
+
  '''int32''' greatestBit(x: '''int32'''):
'''int''' l = n    <font color = green>// n {{---}} разрядность числа</font>
+
     power = 1
'''int''' r = -1
+
     '''for''' i = 1 <tex> \ldots\log_2{32}</tex>:
'''while''' r < l - 1:
+
        x |= x >> power
     m = (l + r) / 2
+
         power <<= 1
     '''if''' ((1 << m) - 1) & x == 0:
+
     '''return''' x - (x >> 1)
         r = m
 
     '''else''':
 
        l = m
 
result = r
 
 
</code>
 
</code>
  
====Подсчет количества единичных битов====
+
====Циклический сдвиг====
'''Способ 1'''
+
Пусть дано число <tex>x</tex> и надо совершить циклический сдвиг его битов на величину <tex>d</tex>.
 +
Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на <tex>d</tex> и в противоположном направлении на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.
  
Самый простой способ посчитать количество единичных битов в числе <tex>x</tex> {{---}} сдвигать его на <tex>1</tex> вправо до тех пор, пока оно не станет равно нулю и в процессе смотреть на последний бит.
 
 
<code>
 
<code>
  '''int''' answer = 0
+
  '''int32''' rotateLeft(x, d: '''int32'''):
  '''while''' x != 0:
+
    '''return''' (x << d) | (x >>> (32 - d))
     answer += x & 1
+
    x >> 1
+
  '''int32''' rotateRight(x, d: '''int32'''):
 +
     '''return''' (x >>> d) | (x << (32 - d))
 
</code>
 
</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>
 
<code>
  '''int''' answer = 0
+
<font color = green>// Для чисел других разрядностей необходимо использовать соответствующие константы.</font>
'''while''' x != 0:
+
  '''int16''' setBitsNumber(x: '''int16'''):
     x &= x - 1
+
     x = x - ((x >>> 1) & 0x5555)
     answer++
+
     x = (x & 0x3333) + ((x >>> 2) & 0x3333)
 +
    x = (x + (x >>> 4)) & 0x0F0F
 +
    '''return''' (x * 0x0101) >>> 8
 
</code>
 
</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>.
  
<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>.
'''int''' head, tail
 
head = x << a          <font color = green>// x {{---}} изменяемое число
 
                        // a {{---}} число позиций, на которое хотим выполнить сдвиг</font>
 
'''if''' a != 0:
 
    tail = x >> (n - a)    <font color = green>// n {{---}} разрядность числа x</font>
 
'''else''':
 
    tail = 0
 
result = head | tail
 
</code>
 
  
====Разворот битов====
+
Теперь необходимо просуммировать числа, записанные в блоках по <tex>8</tex> битов, чтобы получить искомую величину. Это можно сделать, домножив результат на <tex>0101_{16}</tex> <tex>(1 00000001_{2})</tex>. Ответ на задачу будет находиться в первых восьми битах произведения. Выполнив сдвиг вправо на <tex>8</tex> (для шестнадцатибитных чисел), мы получим долгожданный ответ.
Чтобы получить биты числа <tex>x</tex>, записанные в обратном порядке, будем снимать значение младшего бита, умножать его на старшую незаписанную степень двойки и сдвигать число вправо на единицу для обработки следующих бит.
 
  
 +
Подведем итог:
 
<code>
 
<code>
  result = 0
+
  '''int16''' setBitsNumber(x: '''int16'''):
position = 1 << (n - 1)    <font color = green>// n {{---}} разрядность числа x</font>
+
     x = (x & 0x5555) + ((x >>> 1) & 0x5555)
'''while''' x != 0:
+
     x = (x & 0x3333) + ((x >>> 2) & 0x3333)
     result += (x & 1) * position
+
    x = (x & 0x0F0F) + ((x >>> 4) & 0x0F0F)
     position >>= 1
+
     '''return''' (x * 0x0101) >>> 8
     x >>= 1
 
 
</code>
 
</code>
  
====Проверка на то, является ли число степенью двойки====
+
Заметим, что операция <tex>x\ \&\ 55_{16} + (x\ \texttt{>>>}\ 1)\ \&\ 55_{16}</tex> равносильна операции <tex>x - (x\ \texttt{>>>}\ 1)\ \&\ 55_{16}</tex>, в чем легко убедиться, рассмотрев все числа из двух бит.
Пусть дано число <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\ \&\ \texttt{0F0F}_{16}) + ((x\ \texttt{>>>}\ 4)\ \&\ \texttt{0F0F}_{16})</tex> можно заменить на <tex>(x + (x\ \texttt{>>>}\ 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>x</tex>, записанные в обратном порядке, применим следующий алгоритм.
коде со сдвигом]] с тем отличием, что у нас знаковый бит принимает значение <tex>1</tex> для отрицательных чисел, а <tex>0</tex> {{---}} для положительных.
 
 
<code>
 
<code>
  <font color = green>// n {{---}} разрядность числа</font>
+
  <font color = green>// Для чисел других разрядностей нужны соответствующие константы.</font>
  mask = x >> n - 1
+
  '''int16''' reverseBits(x: '''int16'''):
   
+
    x = ((x & 0x5555) << 1) | ((x >>> 1) & 0x5555) <font color = green>// Четные и нечетные биты поменялись местами.</font>
abs = (x + mask) <tex>\oplus</tex> mask
+
    x = ((x & 0x3333) << 2) | ((x >>> 2) & 0x3333)  <font color = green>// Биты "перетасовываются" группами по два.</font>
  <font color = green>// другой способ сделать то же самое:</font>
+
    x = ((x & 0x0F0F) << 4) | ((x >>> 4) & 0x0F0F) <font color = green>// Биты "перетасовываются" группами по четыре.</font>
abs = (x <tex>\oplus</tex> mask) - mask
+
    x = ((x & 0x00FF) << 8) | ((x >>> 8) & 0x00FF)  <font color = green>// Биты "перетасовываются" группами по восемь.</font>
 +
    '''return''' x
 
</code>
 
</code>
  
====Нахождение минимума и максимума из двух чисел без использования условного оператора====
+
Более подробно про то, что за константы выбраны для данного алгоритма, можно прочитать в разделе [[Побитовые_операции#Подсчет_количества_единичных_битов | подсчет количества единичных битов]].
Этот способ корректен только если можно утверждать, что величина <tex>(x - y)</tex> лежит между граничными значениями типа int.
 
<code>
 
<font color = green>// n {{---}} разрядность чисел</font>
 
min = y + ((x - y) & ((x - y) >> (n - 1)))
 
max = x - ((x - y) & ((x - y) >> (n - 1)))
 
</code>
 
  
 
===Применение для решения задач===
 
===Применение для решения задач===
Строка 215: Строка 199:
 
====Алгоритм Флойда====
 
====Алгоритм Флойда====
 
{{main|Алгоритм Флойда}}
 
{{main|Алгоритм Флойда}}
 +
'''Алгоритм Флойда–Уоршелла''' (англ. ''the Floyd–Warshall algorithm'') {{---}}  алгоритм для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а если же такой цикл есть, позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма <tex> \Theta(n^3) </tex>, также требует <tex> \Theta(n^2) </tex> памяти.
  
 
====Дерево Фенвика====
 
====Дерево Фенвика====
 
{{main|Дерево Фенвика}}
 
{{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> — функция, которую мы определили ранее.
 +
 +
==См. также==
 +
* [[Определение булевой функции]]
 +
* [[Сумматор]]
 +
* [[Триггеры]]
  
 
==Примечания==
 
==Примечания==
Строка 227: Строка 225:
 
* [https://graphics.stanford.edu/~seander/bithacks.html Bit Twiddling Hacks by Sean Eron Anderson]
 
* [https://graphics.stanford.edu/~seander/bithacks.html Bit Twiddling Hacks by Sean Eron Anderson]
 
* [https://habrahabr.ru/post/93172/ Habrahabr {{---}} Алгоритмы поиска старшего бита]
 
* [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]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Булевы функции ]]

Текущая версия на 19:40, 4 сентября 2022

Побитовые операции (англ. bitwise operations) — операции, производимые над цепочками битов. Выделяют два типа побитовых операций: логические операции и побитовые сдвиги.

Принцип работы

Логические побитовые операции

Битовые операторы И [math](AND,\ \&)[/math], ИЛИ [math](OR,\ \mid)[/math], НЕ [math](NOT,\ \sim)[/math] и исключающее ИЛИ [math](XOR,\ $\textasciicircum$,\ \oplus)[/math] используют те же таблицы истинности, что и их логические эквиваленты.

Побитовое И

Побитовое И используется для выключения битов. Любой бит, установленный в [math]0[/math], вызывает установку соответствующего бита результата также в [math]0[/math].

&
11001010
11100010
11000010

Побитовое ИЛИ

Побитовое ИЛИ используется для включения битов. Любой бит, установленный в [math]1[/math], вызывает установку соответствующего бита результата также в [math]1[/math].

|
11001010
11100010
11101010

Побитовое НЕ

Побитовое НЕ инвертирует состояние каждого бита исходной переменной.

~
11001010
00110101

Побитовое исключающее ИЛИ

Исключающее ИЛИ устанавливает значение бита результата в [math]1[/math], если значения в соответствующих битах исходных переменных различны.

^
11001010
11100010
00101000

Побитовые сдвиги

Операторы сдвига [math]\lt \lt [/math] и [math]{\gt \gt }[/math] сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в двоичном дополнительном коде и необходимо поддерживать знаковый бит).

Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.

x = 7         // 00000111 (7)
x = x >> 1    // 00000011 (3)
x = x << 1    // 00000110 (6)
x = x << 5    // 11000000 (-64)
x = x >> 2    // 11110000 (-16)

В языке программирования Java существует также оператор беззнакового битового сдвига вправо [math]\gt \gt \gt [/math]. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.

x = 7          // 00000111 (7)
x = x << 5     // 11100000 (-32)
x = x >>> 2    // 00111000 (56)

Применение

Сложные операции

Определение знака числа

Пусть дано число [math]x[/math]. Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа [math]x[/math] можно определить, выполнив сдвиг вправо на всю длину переменной:

int32 getSign(x: int32):
    if x != 0:
        mask = 1
    else:
        mask = 0

    return mask | (x >> 31)    // результатом будет -1, 0, или +1 
                               // для отрицательного, равного нулю и положительного числа x соответственно

Используя побитовые операции можно также узнать, различны ли знаки двух переменных [math]x[/math] и [math]y[/math]. Если числа имеют различный знак, то результат операции XOR, произведенной над их знаковыми битами, будет единицей. Поэтому неравенство [math](x \oplus y) \lt 0[/math] будет верно в том случае, если числа [math]x[/math] и [math]y[/math] разного знака.

Вычисление модуля числа без использования условного оператора

Пусть дано число [math]x[/math]. Если [math]x[/math] положительно, то [math]mask = 0[/math], и [math](x + mask) \oplus mask = x[/math]. В случае, если [math]x[/math] отрицательно, [math]mask = -1[/math]. Тогда получается, что мы работаем с числом [math]x[/math] так, как будто оно представлено в коде со сдвигом с тем отличием, что у нас знаковый бит принимает значение [math]1[/math] для отрицательных чисел, а [math]0[/math] — для положительных.

int32 abs1(x: int32):
    mask = x >> 31
    return (x + mask) XOR mask

int32 abs2(x: int32):
    mask = x >> 31
    return (x + mask) XOR mask

Нахождение минимума и максимума из двух чисел без использования условного оператора

Этот способ корректен только если можно утверждать, что величина [math](x - y)[/math] лежит между граничными значениями типа int.

Пусть даны числа [math]x[/math] и [math]y[/math] разрядности [math]n[/math]. Тогда если [math]x \lt y[/math], то [math]((x - y) \gt \gt (n - 1)) = -1[/math], а если [math]x \geqslant y[/math], то [math]((x - y) \gt \gt (n - 1)) = 0[/math]. Выражение [math]((x - y) \& ((x - y) \gt \gt (n - 1))[/math] принимает значение [math]0[/math], если [math]x \geqslant y[/math], и [math](x - y)[/math], если [math]x \lt y[/math].

int32 min(x, y: int32):
    return y + ((x - y) & ((x - y) >> 31))

int32 max(x, y: int32):
    return x - ((x - y) & ((x - y) >> 31))

Проверка на то, является ли число степенью двойки

Пусть дано число [math]x[/math]. Тогда, если результатом выражения [math](x\ \&\&\ !(x\ \&\ (x - 1)))[/math] является единица, то число [math]x[/math] — степень двойки.

Правая часть выражения [math](!(x\ \&\ (x - 1)))[/math] будет равна единице, только если число [math]x[/math] равно [math]0[/math] или является степенью двойки. Если число [math]x[/math] является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: [math]1\underbrace{0\dots0}_{n}[/math], где [math]n[/math] — показатель степени. Соответственно, выражение [math](x - 1)[/math] будет иметь вид [math]\underbrace{1\dots1}_{n}[/math], и [math]x\ \&\ (x - 1)[/math] равно [math]0[/math].

Операция логического И в данном выражении отсекает тот случай, когда [math](x = 0)[/math] и не является степенью двойки, но при этом правая часть [math](!(x\ \&\ (x - 1)))[/math] равна единице.

Нахождение младшего единичного бита

Пусть дано число [math]x[/math] и необходимо узнать его младший единичный бит.

Применим к числу [math]x[/math] побитовое отрицание, чтобы инвертировать значения всех его бит, а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом [math]x[/math], а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа [math](x\ \&\ (\sim x + 1))[/math].

К такому же результату можно прийти, если сначала отнять от числа [math]x[/math] единицу, чтобы обнулить его младший единичный бит, а все последующие разряды обратить в [math]1[/math], затем инвертировать результат и применить побитовое И с исходным числом [math](x\ \&\ \sim (x - 1))[/math].

Нахождение старшего единичного бита

Пусть дано число [math]x[/math] и необходимо узнать его старший единичный бит.

Рассмотрим некоторое число, представим его как [math]0\dots01b \dots b[/math], где [math]b[/math] — любое значение бита. Тогда, если совершить битовый сдвиг этого числа вправо на [math]1[/math] и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим результат [math]0\dots011b \dots b[/math]. Если мы повторим эту последовательность действий над полученным числом, но устроим сдвиг на [math]2[/math], то получим [math]0\dots01111b \dots b[/math]. При каждой следующей операции будем увеличивать модуль сдвига до следующей степени двойки. После некоторого количества таких операций (зависит от разрядности числа) мы получим число вида [math]0\dots01\dots1[/math]. Тогда результатом выполнения действий [math]x - (x \texttt{ \gt \gt }1)[/math] будет число, состоящее только из старшего бита исходного числа.

int32 greatestBit(x: int32):
    power = 1
    for i = 1 [math] \ldots\log_2{32}[/math]:
        x |= x >> power
        power <<= 1
    return x - (x >> 1)

Циклический сдвиг

Пусть дано число [math]x[/math] и надо совершить циклический сдвиг его битов на величину [math]d[/math]. Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на [math]d[/math] и в противоположном направлении на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.

int32 rotateLeft(x, d: int32):
    return (x << d) | (x >>> (32 - d))

int32 rotateRight(x, d: int32):
    return (x >>> d) | (x << (32 - d))

Подсчет количества единичных битов

Для подсчета количества единичных битов в числе [math]x[/math] можно воспользоваться следующим алгоритмом:

// Для чисел других разрядностей необходимо использовать соответствующие константы. 
int16 setBitsNumber(x: int16):
    x = x - ((x >>> 1) & 0x5555)
    x = (x & 0x3333) + ((x >>> 2) & 0x3333)
    x = (x + (x >>> 4)) & 0x0F0F
    return (x * 0x0101) >>> 8

Поскольку [math]5555_{16}[/math] равно [math]01010101 01010101_{2}[/math], результатом операции [math]x\ \&\ 5555_{16}[/math] является число, в котором все нечетные биты соответствуют нечетным битам числа [math]x[/math]. Аналогично, результатом операции [math](x\ \texttt{\gt \gt \gt }\ 1)\ \&\ 5555_{16}[/math] является число, в котором все нечетные биты соответствуют четным битам [math]x[/math]. Четные биты результата в обоих случаях равны нулю.

Мысленно разобьем двоичную запись нашего числа [math]x[/math] на группы по [math]2[/math] бита. Результатом операции [math]x\ \&\ 5555_{16} + (x\ \texttt{\gt \gt \gt }\ 1)\ \&\ 5555_{16}[/math] будет такое число, что если разбить его двоичную запись на группы по два бита, значение каждой группы соответствует количеству единичных битов в соответствующей паре битов числа [math]x[/math].

Аналогично, число [math]3333_{16}[/math] равно [math]00110011 00110011_{2}[/math] и операция [math]x = (x\ \&\ 3333_{16}) + (x\ \texttt{\gt \gt \gt }\ 2\ \&\ 3333_{16})[/math], примененная к результату, полученному на первом этапе, выполняет подсчет количества единичных битов в блоках по [math]4[/math]. В свою очередь, число [math]\texttt{0F0F}_{16}[/math] равно [math]00001111 00001111_{2}[/math] и операция [math]x = (x\ \&\ \texttt{0F0F}_{16}) + (x\ \texttt{\gt \gt \gt }\ 4\ \&\ \texttt{0F0F}_{16})[/math] позволяет подсчитать число единичных бит в блоках по [math]8[/math].

Теперь необходимо просуммировать числа, записанные в блоках по [math]8[/math] битов, чтобы получить искомую величину. Это можно сделать, домножив результат на [math]0101_{16}[/math] [math](1 00000001_{2})[/math]. Ответ на задачу будет находиться в первых восьми битах произведения. Выполнив сдвиг вправо на [math]8[/math] (для шестнадцатибитных чисел), мы получим долгожданный ответ.

Подведем итог:

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

Заметим, что операция [math]x\ \&\ 55_{16} + (x\ \texttt{\gt \gt \gt }\ 1)\ \&\ 55_{16}[/math] равносильна операции [math]x - (x\ \texttt{\gt \gt \gt }\ 1)\ \&\ 55_{16}[/math], в чем легко убедиться, рассмотрев все числа из двух бит.

В свою очередь, операцию [math](x\ \&\ \texttt{0F0F}_{16}) + ((x\ \texttt{\gt \gt \gt }\ 4)\ \&\ \texttt{0F0F}_{16})[/math] можно заменить на [math](x + (x\ \texttt{\gt \gt \gt }\ 4))\ \&\ \texttt{0F0F}_{16}[/math]. Эта замена не повлияет на результат, так как максимальное значение в любой группе из четырех битов данного числа равно четырем, то есть требует только трех битов для записи, и выполнение суммирования не повлечет за собой переполнения и выхода за пределы четверок.

Таким образом, мы получили код, приведенный в начале раздела.

Разворот битов

Чтобы получить биты числа [math]x[/math], записанные в обратном порядке, применим следующий алгоритм.

// Для чисел других разрядностей нужны соответствующие константы.
int16 reverseBits(x: int16):
    x = ((x & 0x5555) << 1) | ((x >>> 1) & 0x5555)  // Четные и нечетные биты поменялись местами.
    x = ((x & 0x3333) << 2) | ((x >>> 2) & 0x3333)  // Биты "перетасовываются" группами по два.
    x = ((x & 0x0F0F) << 4) | ((x >>> 4) & 0x0F0F)  // Биты "перетасовываются" группами по четыре.
    x = ((x & 0x00FF) << 8) | ((x >>> 8) & 0x00FF)  // Биты "перетасовываются" группами по восемь.
    return x

Более подробно про то, что за константы выбраны для данного алгоритма, можно прочитать в разделе подсчет количества единичных битов.

Применение для решения задач

Работа с битовыми масками

Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение [math](\sim mask)[/math], пересечение [math](mask_1\ \&\ mask_2)[/math], объединение [math](mask_1 \mid mask_2)[/math] множеств, установить бит по номеру [math](mask \mid (1\ \texttt{\lt \lt }\ x))[/math], снять бит по номеру [math](mask\ \&\ \sim(1\ \texttt{\lt \lt }\ x))[/math].

Битовые маски используются, например, при решении некоторых задач[1] динамического программирования.

Алгоритм Флойда

Основная статья: Алгоритм Флойда

Алгоритм Флойда–Уоршелла (англ. the Floyd–Warshall algorithm) — алгоритм для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а если же такой цикл есть, позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма [math] \Theta(n^3) [/math], также требует [math] \Theta(n^2) [/math] памяти.

Дерево Фенвика

Основная статья: Дерево Фенвика

Дерево Фенвика (англ. Binary indexed tree) — структура данных, которая может выполнять следующие операции:

Данная структура требует [math] O(n) [/math] памяти, а выполнение каждой операции происходит за [math] O(\log n) [/math] .

Функция, позволяющая делать операции вставки и изменения элемента за [math] O(\log n) [/math], задается следующей формулой [math] F(i) = (i \And (i + 1)) [/math]. Пусть дан массив [math] A = [a_0, a_1, \ldots, a_{n - 1}][/math]. Деревом Фенвика называется массив [math] T [/math] из [math] n [/math] элементов: [math] T_i = \sum\limits_{k = F(i)}^{i} a_k[/math], где [math] i = 0\ldots n - 1 [/math] и [math] F(i) [/math] — функция, которую мы определили ранее.

См. также

Примечания

Источники информации