Побитовые операции
Побитовые операции (англ. 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 хранится количество битов в одном байте sign = x >> (sizeof(int) * CHAR_BIT - 1) // если x < 0, результатом будет -1, иначе 0
sign = (x != 0) | (x >> (sizeof(int) * CHAR_BIT - 1)) // результатом будет -1, 0, или +1
// для отрицательного, равного нулю и положительного числа x соответственно
Используя побитовые операции можно также узнать, различны ли знаки двух переменных:
bool result = ((x y) < 0) // значение переменной result == true, если знаки переменных x и y различны
Вычисление модуля числа без использования условного оператора
mask = x >> sizeof(int) * CHAR_BIT - 1 abs = (x + mask) mask // другой способ сделать то же самое: abs = (x mask) - mask
Нахождение минимума и максимума из двух чисел без использования условного оператора
Этот способ корректен только если можно утверждать, что величина лежит между граничными значениями типа int.
min = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))) max = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))
Применение для решения задач
Работа с битовыми масками
Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение , пересечение , объединение множеств, установить бит по номеру , снять бит по номеру .
Битовые маски используются, например, при решении некоторых задач[1] динамического программирования.
