Побитовые операции
Побитовые операции (англ. bitwise operations) — операции, производимые над цепочками битов. Выделяют два типа побитовых операций: логические операции и побитовые сдвиги.
Принцип работы
Логические побитовые операции
Битовые операторы И , ИЛИ , НЕ и исключающее ИЛИ используют те же таблицы истинности, что и их логические эквиваленты.
Побитовое И
Побитовое И используется для выключения битов. Любой бит, установленный в , вызывает установку соответствующего бита результата также в .
| & | |
|---|---|
| 11001010 11100010 | |
| 11000010 |
Побитовое ИЛИ
Побитовое ИЛИ используется для включения битов. Любой бит, установленный в , вызывает установку соответствующего бита результата также в .
| | | |
|---|---|
| 11001010 11100010 | |
| 11101010 |
Побитовое НЕ
Побитовое НЕ инвертирует состояние каждого бита исходной переменной.
| ~ | |
|---|---|
| 11001010 | |
| 00110101 |
Побитовое исключающее ИЛИ
Исключающее ИЛИ устанавливает значение бита результата в , если значения в соответствующих битах исходных переменных различны.
| ^ | |
|---|---|
| 11001010 11100010 | |
| 00101000 |
Побитовые сдвиги
Операторы сдвига и сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в двоичном дополнительном коде и необходимо поддерживать знаковый бит).
Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.
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 существует также оператор беззнакового битового сдвига вправо . При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.
x = 7 // 00000111 (7) x = x << 5 // 11100000 (-32) x = x >> 2 // 00111000 (56)
Применение
Сложные операции
Проверка на то, является ли число степенью двойки
Пусть дано число . Тогда, если результатом выражения является единица, то число — степень двойки.
Правая часть выражения будет равна единице только если число равно или является степенью двойки. Если число является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: , где — показатель степени. Соответственно, выражение будет иметь вид , и равно .
Операция логического И в данном выражении отсекает тот случай, когда и не является степенью двойки, но при этом правая часть равна единице.
Определение знака числа
Пусть дано число . Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа можно определить, выполнив сдвиг вправо на всю длину переменной:
// в константе CHAR_BIT хранится количество битов в одном байте
if x != 0
mask = 1
else
mask = 0
sign = mask | (x >> (sizeof(int) * CHAR_BIT - 1)) // результатом будет -1, 0, или +1
// для отрицательного, равного нулю и положительного числа x соответственно
Используя побитовые операции можно также узнать, различны ли знаки двух переменных и . Если числа имеют различный знак, то результат операции XOR, произведенной над их знаковыми битами, будет единицей. Поэтому неравенство будет верно в том случае, если числа и разного знака.
Нахождение старшего единичного бита
Способ 1
Рассмотрим некоторое число, представим его как , где — любое значение бита. Тогда, если совершить битовый сдвиг этого числа вправо на и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим результат . Если мы повторим эту последовательность действий над полученным числом, но устроим сдвиг на , то получим . При каждой следующей операции будем увеличивать модуль сдвига до следующей степени двойки. После некоторого количества таких операций (зависит от разрядности числа) мы получим число вида . Тогда результатом выполнения действий будет число, состоящее только из старшего бита исходного числа.
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
Нахождение младшего единичного бита
Способ 1
Применим к числу побитовое отрицание, чтобы инвертировать значения всех его битов, а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом , а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа .
К такому же результату можно прийти, если сначала отнять от числа единицу, чтобы обнулить его младший единичный бит, а все последующие разряды обратить в , затем инвертировать результат и применить побитовое И с исходным числом .
Способ 2
Алгоритм аналогичен описанному выше способу нахождения старшего единичного бита и также основан на бинпоиске. Будем искать максимальное число вида такое, что его побитовое И с числом дает .
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
Самый простой способ посчитать количество единичных битов в числе — сдвигать его на вправо до тех пор, пока оно не станет равно нулю и смотреть на последний бит.
int answer = 0
while x != 0:
answer += x & 1
x >> 1
Способ 2
Пусть мы хотим посчитать количество единичных бит в числе . Если вычесть из единицу, то его младший единичный бит обнулится, а все последующие за ним биты примут значение . Если произвести операцию побитового И между и , то мы получим число, побитово равное во всех позициях, кроме младшего единичного бита (в результирующем числе он будет нулевым). Таким образом, количество совершенных операций до того момента, как исходное число обратится в ноль, будет равно количеству единичных бит в нём.
int answer = 0
while x != 0:
x &= x - 1
answer++
Циклический сдвиг
Самый простой способ устроить циклический сдвиг числа, это объединить результаты обычных битовых сдвигов влево и вправо на соответствующие величины. Таким образом, мы сможем поменять местами начальную и конечную части числа.
Сдвиг влево
int head, tail
head = x << a // x — изменяемое число
// a — число позиций, на которое хотим выполнить сдвиг
tail = x >> (n - a) // n — разрядность числа x
result = head | tail
Сдвиг вправо
int head, tail
head = x << (n - a) // x — изменяемое число
// a — число позиций, на которое хотим выполнить сдвиг
tail = x >> a // n — разрядность числа x
result = head | tail
Вычисление модуля числа без использования условного оператора
Пусть дано число . Тогда
// в константе CHAR_BIT хранится количество битов в одном байте mask = x >> sizeof(int) * CHAR_BIT - 1 abs = (x + mask) mask // другой способ сделать то же самое: abs = (x mask) - mask
Нахождение минимума и максимума из двух чисел без использования условного оператора
Этот способ корректен только если можно утверждать, что величина лежит между граничными значениями типа 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)))
Применение для решения задач
Работа с битовыми масками
Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение , пересечение , объединение множеств, установить бит по номеру , снять бит по номеру .
Битовые маски используются, например, при решении некоторых задач[1] динамического программирования.
