Побитовые операции
Побитовые операции (англ. bitwise operations) — операции, производимые над цепочками битов. Выделяют два типа побитовых операций: логические операции и побитовые сдвиги.
Принцип работы
Логические побитовые операции
Битовые операторы И , ИЛИ , НЕ и исключающее ИЛИ используют те же таблицы истинности, что и их логические эквиваленты.
Побитовое И
Побитовое И используется для выключения битов. Любой бит, установленный в , вызывает установку соответствующего бита результата также в .
| & | |
|---|---|
| 11001010 11100010 | |
| 11000010 |
Побитовое ИЛИ
Побитовое ИЛИ используется для включения битов. Любой бит, установленный в , вызывает установку соответствующего бита результата также в .
| | | |
|---|---|
| 11001010 11100010 | |
| 11101010 |
Побитовое НЕ
Побитовое НЕ инвертирует состояние каждого бита исходной переменной.
| ~ | |
|---|---|
| 11001010 | |
| 00110101 |
Побитовое исключающее ИЛИ
Исключающее ИЛИ устанавливает значение бита результата в , если значения в соответствующих битах исходных переменных различны.
| ^ | |
|---|---|
| 11001010 11100010 | |
| 00101000 |
Побитовые сдвиги
Операторы сдвига и сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как поддерживается знаковый бит).
Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.
x = 7 //00000111 x << 1 //00001110 x << 5 //11000000 x >> 2 //00110000
В языке программирования Java существует также оператор беззнакового битового сдвига вправо . При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.
Ограничения
При использовании битовых сдвигов для отрицательных чисел округление происходит к .
C++ Visual Studio 15
Если выполняется сдвиг влево числа со знаком и при этом затрагивается бит знака, результат не определен.
Результат сдвига вправо отрицательного числа со знаком зависит от реализации.
Результат операции сдвига также не определен, если число, на которое нужно сдвинуть биты, имеет отрицательное значение, или если оно больше или равно количеству битов в исходном числе.
short x = 16384 // 01000000 00000000
short y = x << 1 // 10000000 00000000
// 16384 left-shifted by 1 = -32768
Java
При сдвиге на количество бит большее, чем разрядность левого операнда, происходит неявное сокращение правого операнда (количество бит).
Примеры:
i = 1 //00000000 00000000 00000000 00000001 (1) i << 29 //00100000 00000000 00000000 00000000 (536870912) i << 30 //01000000 00000000 00000000 00000000 (1073741824) i << 31 //10000000 00000000 00000000 00000000 (-2147483648 / 2147483648) i << 32 //00000000 00000000 00000000 00000001 (1)
i = -1 //11111111 11111111 11111111 11111111 (-1 / 4294967295) i >>> 1 //01111111 11111111 11111111 11111111 (2147483647) i >>> 30 //00000000 00000000 00000000 00000011 (3) i >>> 31 //00000000 00000000 00000000 00000001 (1) i >>> 32 //11111111 11111111 11111111 11111111 (-1 / 4294967295)
i = -192 //11111111 11111111 11111111 01000000 (-192 / 4294967104) i >> 1 //11111111 11111111 11111111 10100000 (-96 / 4294967200) i >> 30 //11111111 11111111 11111111 11111111 (-1 / 4294967295) i >> 31 //11111111 11111111 11111111 11111111 (-1 / 4294967295) i >> 32 //11111111 11111111 11111111 01000000 (-192 / 4294967104)
Арифметическое распространение в Java проводится перед операциями и гарантирует расширение каждого операнда по крайней мере до int (или, если один из операндов имеет больший тип, то до него). Расширение происходит знаково, ввиду чего результат может быть не таким, как ожидалось; при приведении типа к меньшему лишние байты отбрасываются.
Примеры:
byte b = -127 //10000001 (-127 / 129) (int)b //11111111 11111111 11111111 10000001 (-127 / 4294967169)
int i = -127 //11111111 11111111 11111111 10000001 (-127 / 4294967169) (byte)i //10000001 (-127 / 129)
int i = 128 //00000000 00000000 00000000 10000000 (128) (byte)i //10000000 (-128 / 128)
int i = 256 //00000000 00000000 00000001 00000000 (256) (byte)i //00000000 (0)
int i = -256 //11111111 11111111 11111111 00000000 (-256 / 4294967040) (byte)i //00000000 (0)
Применение для решения задач
Проверка на то, является ли число степенью двойки
answer = x and not(x & (x - 1)) // если answer == 1, то число x является степенью двойки
Работа с битовыми масками
Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение , пересечение , объединение множеств, установить бит по номеру , снять бит по номеру .
Определение знака числа
Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа можно определить следующим образом:
// в этом и следующих примерах в константе 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)))
Кодирование информации
// функция для шифровки текста с помощью XOR
function encode(secret: string, key: string): byte[]
btxt = secret.getBytes
bkey = key.getBytes
for i = 0 .. btxt.length - 1:
result[i] = (btxt[i] bkey[i % bkey.length]) as byte
return result
// функция для расшифровки текста
function decode(secret: byte[], key: string): string
bkey = key.getBytes
for i = 0 .. secret.length - 1:
result[i] = (secret[i] bkey[i % bkey.length]) as byte
return result as string
