Побитовые операции и операции битового сдвига в Java и не только

Целью статьи является показать возможности практического применения побитовых операций.

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

В Java существуют следующие виды побитовых операций:

|	ИЛИ (OR)
&	И (AND)
^	ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR)
~	ОТРИЦАНИЕ (NOT)

Так же стоит выделить операции битового сдвига:

<<	сдвиг влево
>>	сдвиг вправо
>>>	беззнаковый сдвиг вправо

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

Применяются к каждой паре битов, которые стоят в одинаковых позициях в двух битовых последовательностях.

Побитовое ИЛИ (OR)

Оператор обозначается символом |

Выставляет значение в 1, если установлен соответствующий бит в первой или во второй последовательности, или вместе

00000000 00000000 00000000 01111011 (123)
|
00000000 00000000 00000001 11001000 (456)
=
00000000 00000000 00000001 11111011 (507)

Побитовое И (AND)

Обозначается символом &

Выставляет значение в 1, если установлены соответствующие биты в первой и второй последовательности одновременно

00000000 00000000 00000000 01111011 (123)
&
00000000 00000000 00000001 11001000 (456)
=
00000000 00000000 00000000 01001000 (57)

ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR)

Обозначается символом ^

Выставляет значение в 1, если установлен соответствующий бит или в первой или во второй во второй последовательности, но не одновременно.

Если используется более двух последовательностей, то в результате будет единица тогда, когда общее количество единиц соответствующей позиции нечетное.

00000000 00000000 00000000 01111011 (123)
^
00000000 00000000 00000001 11001000 (456)
=
00000000 00000000 00000001 10110011 (435)

ПОБИТОВОЕ ОТРИЦАНИЕ (NOT)

Обозначается символом ~

Унарный оператор, т.е. применяется к одной последовательности. Превращает каждый бит в противоположный.

~
00000000 00000000 00000000 01111011 (123)
=
11111111 11111111 11111111 10000100 (-124)

Знаковый оператор сдвига влево <<

Все биты смещаются влево. Число справа дополняется нулем. Операция используется для быстрого умножения на 2. Если оператор применяется к числу, умножение на 2 которого будет больше максимального значения int (2147483647), то в результате будет отрицательное число. Это происходит потому, что краний левый бит, который отвечает за знак числа, выставляется в единицу, что соответствует отрицательным числам.

11111111 11111111 11111111 10000101 (-123)
<<
11111111 11111111 11111111 00001010 (-246)

Знаковый оператор сдвига вправо >>

Все биты смещаются вправо. Число слева дополняется нулем, если число положительное и единицей, если отрицательное. Операция используется для быстрого деления на 2. Если делится нечетное число, то остаток отбрасывается для положительных чисел и сохраняется для отрицательных.

11111111 11111111 11111111 10000101 (-123)
>>
11111111 11111111 11111111 11000010 (-62)

Беззнаковый оператор сдвига >>>

Все биты смещаются вправо, число слева дополняется нулем, даже если операция выполняется с отрицательными числами. Отсюда и название оператора — беззнаковый. В результате применения оператора всегда получается положительное число, т.к. в Java левый бит отвечает за знак числа. Операция так же, как и знаковый оператор сдвига вправо, соответствует делению числа на два за исключением первого сдвига в отрицительном числе.

11111111 11111111 11111111 10000101 (-123)
>>>
01111111 11111111 11111111 11000010 (2147483586)

Применение на практике

Первое, что нам нужно понимать, что за последовательностью битов скрывается какая-то информация, которой мы можем управлять посредством битовых операций, например, это может быть список булевых значений или просто числа, которыми удобнее манипулировать в двоичном представлении

Когда количество сдвигов превышает количество разрядов

При использовании битовых сдвигов важно помнить, что когда количество сдвигов достигает количества разрядов, следующий сдвиг вернет значение в исходное положение. Например, сдвиг влево:

0 -  00000000000000000000000001111011 (123)
1 -  00000000000000000000000011110110 (246)
...
30 - 11000000000000000000000000000000 (-1073741824)
31 - 10000000000000000000000000000000 (-2147483648)
32 - 00000000000000000000000001111011 (123)

Так же имеет смысл заметить, что после 31-го сдвига нет позиции, где все нули.

Приведение чисел к соответствующему типу данных

При использовании побитовых операций с типами данных byte/short, числа сначала приводятся к типу int, а если одно из чисел — long, то к long.

int i = Integer.MAX_VALUE; //1111111111111111111111111111111
long l = Long.MAX_VALUE; //111111111111111111111111111111111111111111111111111111111111111
long r1 = i&l;
long r2 = l&l;

//r1 - 000000000000000000000000000000001111111111111111111111111111111 (2147483647)
//r2 - 111111111111111111111111111111111111111111111111111111111111111 (9223372036854775807)

При сужении типа данных, левая часть битов просто отбрасывается, например:

long l1 = -9223372032559808513L;
int i1 = (int) l1; //2147483647

l1 - 1000000000000000000000000000000011111111111111111111111111111111
r1 - 11111111111111111111111111111111

Использование маски

Одним из приемов работы с битовыми данными является использование маски. Маска позволяет получать значения только определенных битов в последовательности. Например, у нас есть маска 00100100, она позволяет нам получать из последовательности только те биты, которые в ней установлены. В данном случае это 3-й и 7-й разряд. Для этого достаточно выполнить побитовое И с нашей маской и неким числом:

01010101
&
00100100
=
00000100

Битовая маска используется, например, при определении маски подсети в сетевой адресации.

Хранение в одной целочисленной переменной нескольких значений

При помощи битовых сдвигов можно хранить в одной целочисленной переменной несколько значений меньшей длины. Например, в первых нескольких битах можно хранить одно число, в следующих битах — другое. Требуется только знать, на сколько бит выполняется сдвиг и сколько бит занимает хранимое число. Для записи используется логическое ИЛИ, для получения — И.

В следующем примере в одном числе сохраняются три значения — возраст, рост, вес, а затем считываются из него. Недостатком такой системы является необходимость помнить, что хранимые значения не должны превышать количество бит, которые определены для них. Например, если в примере одно из значений будет превышать число 255, то мы получим ошибочный результат.

int age, height, weight, combined, mask;
age = 28; //00011100
height = 185; //10111001
weight = 80; //01010000
combined = (age) | (height << 8) | (weight << 16); //00000000 01010000 10111001 00011100

mask = 0b11111111;

System.out.printf("Age: %d, height: %d, weight: %d", 
        mask & combined, 
        mask & combined >>> 8, 
        mask & combined >>> 16);
//Age: 28, height: 185, weight: 80

Работа с правами доступа

Еще один рапространенный пример применения побитовых операций — работа с правами доступа к папкам и файлам. Принцип следующий. Имеется последовательность из трех битов, где:
001 — первый бит отвечает за права на выполнение
010 — второй — запись
100 — третий — чтение

Имеем следующие константы.

final int EXECUTE = 1; //001
final int WRITE = 2; //010
final int READ = 4; //100

Допустим, нам требуется дать пользователю полный доступ к ресурсу. Для этого должен быть выставлен каждый бит:

int usersAccess = EXECUTE | WRITE | READ; //Получили значение 7 (111)

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

usersAccess = usersAccess ^ EXECUTE //Получили значение 6 (110)

Обмен переменных местами без использования временной переменной

Исключающее ИЛИ может быть использовано для обмена двух переменных без создания временной переменной:

void xorSwap(int x, int y) {
 x = x^y;
 y = y^x;
 x = x^y;
}

Правда, в реальной жизни способ с временной переменной работает быстрее. Данный пример приведен только в познавательных целях.

Шифр Вернама

На основе иключающего ИЛИ работает шифр Вернама, для которого была доказана абсолютная криптографическая стойкость. Шифр был «взломан» в фильме «Пароль «Рыба-меч»»

Быстрое умножение и деление

Операции сдвига рекомендуют использовать для быстрого умножения и деления целых чисел на числа, равные степени двойки. Например, выражение 3 << 4 соответствует умножению тройки на 2 в 4-й степени.

Хранение списка булевых значений и манипуляция ими

Побитовое ИЛИ может быть использовано для установки в 1 необходимых позиций битов в последовательности. Это позволяет, например, хранить список булевых значений в максимально сжатом виде

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

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

С помощью побитовых операций можно за константное время проверить, является ли число степенью двойки:

(x & (x-1)) == 0

Данное выражение работает для всех чисел, кроме 0, а 0 не является степенью двойки. Поэтому конечный вариант должен выглядеть так:

(x != 0) && ((x & (x-1)) == 0)

Как это работает:
В числе 2 в степени n в единицу выставлен только (n+1)-й бит. Все остальные — нули. Например, числа 16 и 32 имеют двоичный вид, соответственно, 10000 и 100000. Т.е. нам необходимо проверить, что в числе выставлен только один бит.
Допустим, число k — два в степени n. В числе k в единицу выставлен (n+1)-й бит. Тогда в числе k-1 в единицу будут выставлены все биты от 1 до n. Если с такими числами выполнить побитовое ИЛИ, то в результате должен получиться 0. Например:

32 & 31 == 0 //true

100000
&
011111
=
000000

Вывод

Вывод простой. Программист должен знать побитовые операции и уметь ими пользоваться. Это в некоторых случаях может упростить ему жизнь.

Вот еще много примеров применения побитовых операций:
Bit Twiddling Hacks
The Aggregate Magic Algorithms
All The Twiddled Bits
Code for the Algorithms in Hacker's Delight book

Ну и домашнее задание напоследок. Почему в HashMap в Java для определения индекса используется логическое И?

static int indexFor(int h, int length) {
    return h & (length-1);
}

Использованная литература:

Bitwise and Bit Shift Operators
Битовые операции в PHP на примерах
Алгоритм обмена при помощи исключающего ИЛИ
Битовые сдвиги и приведения в Java: подводные камни
Битовая маска
Bitwise operation
How to check if a number is a power of 2

Автор: shurik2533

Источник