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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Циклический сдвиг)
(Применение)
Строка 65: Строка 65:
 
==Применение==
 
==Применение==
 
===Сложные операции===
 
===Сложные операции===
====Проверка на то, является ли число степенью двойки====
 
Пусть дано число <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> можно определить, выполнив сдвиг вправо на всю длину переменной:
 
<code>
 
<font color = green>// в константе '''CHAR_BIT''' хранится количество битов в одном байте</font>
 
 
'''if''' x != 0
 
    mask = 1
 
'''else'''
 
    mask = 0
 
 
sign = mask | (x >> (''sizeof''('''int''') * '''CHAR_BIT''' - 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> разного знака.
 
 
 
====Нахождение старшего единичного бита====
 
====Нахождение старшего единичного бита====
 
'''Способ 1'''
 
'''Способ 1'''
Строка 92: Строка 70:
 
Рассмотрим некоторое число, представим его как <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>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>
  x |= x >> 1
+
  '''int''' power = 1
  x |= x >> 2
+
  '''for''' i = 1..<tex>\log_2{n}</tex>:   <font color = green>// n {{---}} разрядность числа</font>
x |= x >> 4   <font color = green>// Для восьмибитных чисел будет достаточно такого количества операций
+
    x |= x >> power
                // если разрядность больше, надо добавить нужное количество следующих степеней двойки</font>
+
    power <<= 1
 
  result = x - (x >> 1)
 
  result = x - (x >> 1)
 
</code>
 
</code>
Строка 119: Строка 97:
 
'''Способ 1'''
 
'''Способ 1'''
  
Применим к числу <tex>x</tex> побитовое отрицание, чтобы инвертировать значения всех его битов, а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом <tex>x</tex>, а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа <tex>(x\ \&\ (\sim x + 1))</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>1</tex>, затем инвертировать результат и применить побитовое И с исходным числом <tex>(x\ \&\ \sim (x - 1))</tex>.
Строка 140: Строка 118:
 
</code>
 
</code>
  
====Подсчет количества единичных бит====
+
====Подсчет количества единичных битов====
 
'''Способ 1'''
 
'''Способ 1'''
  
Самый простой способ посчитать количество единичных битов в числе <tex>x</tex> {{---}} сдвигать его на <tex>1</tex> вправо до тех пор, пока оно не станет равно нулю и смотреть на последний бит.
+
Самый простой способ посчитать количество единичных битов в числе <tex>x</tex> {{---}} сдвигать его на <tex>1</tex> вправо до тех пор, пока оно не станет равно нулю и в процессе смотреть на последний бит.
 
<code>
 
<code>
 
  '''int''' answer = 0
 
  '''int''' answer = 0
Строка 152: Строка 130:
 
'''Способ 2'''
 
'''Способ 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>. Если вычесть из <tex>x</tex> единицу, то его младший единичный бит обнулится, а все последующие за ним биты примут значение <tex>1</tex>. Если произвести операцию побитового И между <tex>x</tex> и <tex>(x - 1)</tex>, то мы получим число, побитово равное <tex>x</tex> во всех позициях, кроме младшего единичного бита <tex>x</tex> (в результирующем числе он будет нулевым). Таким образом, количество совершенных операций до того момента, как исходное число обратится в ноль, будет равно количеству единичных битов в нём.
  
 
<code>
 
<code>
Строка 160: Строка 138:
 
     answer++
 
     answer++
 
</code>
 
</code>
 +
 
====Циклический сдвиг влево====
 
====Циклический сдвиг влево====
 
Самый простой способ устроить циклический сдвиг числа, это объединить результаты обычных битовых сдвигов влево на необходимую величину и вправо на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.
 
Самый простой способ устроить циклический сдвиг числа, это объединить результаты обычных битовых сдвигов влево на необходимую величину и вправо на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.
Строка 167: Строка 146:
 
  head = x << a          <font color = green>// x {{---}} изменяемое число
 
  head = x << a          <font color = green>// x {{---}} изменяемое число
 
                         // a {{---}} число позиций, на которое хотим выполнить сдвиг</font>
 
                         // a {{---}} число позиций, на которое хотим выполнить сдвиг</font>
  tail = x >> (n - a)    <font color = green>// n {{---}} разрядность числа x</font>
+
  '''if''' a != 0:
 +
    tail = x >> (n - a)    <font color = green>// n {{---}} разрядность числа x</font>
 +
'''else''':
 +
    tail = 0
 
  result = head | tail
 
  result = head | tail
 
</code>
 
</code>
 +
 +
====Разворот битов====
 +
Чтобы получить биты числа <tex>x</tex>, записанные в обратном порядке, будем снимать значение младшего бита, умножать его на старшую незаписанную степень двойки и сдвигать число вправо на единицу для обработки следующих бит.
 +
 +
<code>
 +
result = 0
 +
position = 1 << (n - 1)    <font color = green>// n {{---}} разрядность числа x</font>
 +
'''while''' x != 0:
 +
    result += (x & 1) * position
 +
    position >>= 1
 +
    x >>= 1
 +
</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>. Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа <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>. Тогда  
 
<code>
 
<code>
  <font color = green>// в константе '''CHAR_BIT''' хранится количество битов в одном байте</font>
+
  <font color = green>// n {{---}} разрядность числа</font>
  mask = x >> ''sizeof''('''int''') * '''CHAR_BIT''' - 1
+
  mask = x >> n - 1
 
   
 
   
 
  abs = (x + mask) <tex>\oplus</tex> mask
 
  abs = (x + mask) <tex>\oplus</tex> mask
Строка 185: Строка 201:
 
Этот способ корректен только если можно утверждать, что величина <tex>(x - y)</tex> лежит между граничными значениями типа int.
 
Этот способ корректен только если можно утверждать, что величина <tex>(x - y)</tex> лежит между граничными значениями типа int.
 
<code>
 
<code>
  <font color = green>// в константе '''CHAR_BIT''' хранится количество битов в одном байте</font>
+
  <font color = green>// n {{---}} разрядность чисел</font>
  min = y + ((x - y) & ((x - y) >> (''sizeof''('''int''') * '''CHAR_BIT''' - 1)))
+
  min = y + ((x - y) & ((x - y) >> (n - 1)))
  max = x - ((x - y) & ((x - y) >> (''sizeof''('''int''') * '''CHAR_BIT''' - 1)))
+
  max = x - ((x - y) & ((x - y) >> (n - 1)))
 
</code>
 
</code>
  

Версия 19:11, 13 марта 2016

Побитовые операции (англ. 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]\texttt{\lt \lt }[/math] и [math]\texttt{\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]\texttt{\gt \gt \gt }[/math]. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.

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

Применение

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

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

Способ 1

Рассмотрим некоторое число, представим его как [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] будет число, состоящее только из старшего бита исходного числа.

int power = 1
for i = 1..[math]\log_2{n}[/math]:    // n — разрядность числа
    x |= x >> power
    power <<= 1
result = x - (x >> 1)

Способ 2

Способ основан на бинпоиске. Будем искать максимальную степень двойки, меньшую числа [math]x[/math].

int x, m     // x — исходное число
int l = n    // n — разрядность числа
int r = -1
while r < l - 1:
    m = (l + r) / 2
    if (1 << m) [math]\leqslant[/math] x:
        r = m
    else:
        l = m
result = r

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

Способ 1

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

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

Способ 2

Алгоритм аналогичен описанному выше способу нахождения старшего единичного бита и также основан на бинпоиске. Будем искать максимальное число вида [math]0\dots01\dots1[/math] такое, что его побитовое И с числом [math]x[/math] дает [math]0[/math].

int x, m     // x — исходное число
int l = n    // n — разрядность числа
int r = -1
while r < l - 1:
    m = (l + r) / 2
    if ((1 << m) - 1) & x == 0:
        r = m
    else:
        l = m
result = r

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

Способ 1

Самый простой способ посчитать количество единичных битов в числе [math]x[/math] — сдвигать его на [math]1[/math] вправо до тех пор, пока оно не станет равно нулю и в процессе смотреть на последний бит.

int answer = 0
while x != 0:
    answer += x & 1
    x >> 1

Способ 2

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

int answer = 0
while x != 0:
    x &= x - 1
    answer++

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

Самый простой способ устроить циклический сдвиг числа, это объединить результаты обычных битовых сдвигов влево на необходимую величину и вправо на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.

int head, tail
head = x << a          // x — изменяемое число
                       // a — число позиций, на которое хотим выполнить сдвиг
if a != 0:
    tail = x >> (n - a)    // n — разрядность числа x
else:
    tail = 0
result = head | tail

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

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

result = 0
position = 1 << (n - 1)    // n — разрядность числа x
while x != 0:
    result += (x & 1) * position
    position >>= 1
    x >>= 1

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

Пусть дано число [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] можно определить, выполнив сдвиг вправо на всю длину переменной:

// n — разрядность числа

if x != 0
    mask = 1
else
    mask = 0

sign = mask | (x >> (n - 1))    // результатом будет -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]. Тогда

// n — разрядность числа
mask = x >> n - 1

abs = (x + mask) [math]\oplus[/math] mask
// другой способ сделать то же самое:
abs = (x [math]\oplus[/math] mask) - mask

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

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

// n — разрядность чисел
min = y + ((x - y) & ((x - y) >> (n - 1)))
max = x - ((x - y) & ((x - y) >> (n - 1)))

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

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

Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение [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] динамического программирования.

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

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

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

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

Примечания

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