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

Побитовые операции (англ. 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)

Применение

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

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

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

// в константе CHAR_BIT хранится количество битов в одном байте

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

sign = mask | (x >> (sizeof(int) * CHAR_BIT - 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] разного знака.

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

Способ 1.

Рассмотрим некоторое число, пусть оно представимо как [math]001bbbbb[/math], где [math]b[/math] — любое значение бита. Тогда, если совершить битовый сдвиг этого числа вправо на 1 и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим число [math]0011bbbb[/math]. Если мы повторим эту последовательность действий над полученным числом, но устроим сдвиг на 2, то получим результат [math]001111bb[/math]. Уже на следующем шаге число будет состоять только из нулей и единиц. Результатом выполнения действий [math]x - (x \texttt{ \gt \gt }1)[/math] будет число, состоящее только из старшего бита исходного числа.

x |= x >> 1
x |= x >> 2
x |= x >> 4    // Для восьмибитных чисел будет достаточно такого количества операций
               // если разрядность больше, надо добавить нужное количество следующих степеней двойки
result = x - (x >> 1)

Способ 2.

Способ основан на бинпоиске.

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

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

Пусть дано число [math]x[/math]. Тогда

// в константе CHAR_BIT хранится количество битов в одном байте
mask = x >> sizeof(int) * CHAR_BIT - 1

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

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

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

// в константе CHAR_BIT хранится количество битов в одном байте
min = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))
max = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 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].

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

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

• Онлайн справочник программиста на С и С++
• Побитовые операторы
• Bit Twiddling Hacks by Sean Eron Anderson