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

Побитовые (поразрядные) операции работают не с числом целиком, а с каждым его двоичным разрядом по отдельности. Java предоставляет четыре логические побитовые операции — & (И), | (ИЛИ), ^ (исключающее ИЛИ) и ~ (НЕ), — а также три битовых сдвига: <<, >> и >>>. На них построены маски битовых флагов, быстрая арифметика и даже простейшее шифрование — всё это разберём на примерах.

1. Побитовые операции: AND, OR, XOR, NOT

В следующей таблице перечислены побитовые операции языка Java:

Побитовые операторы применяются к целочисленным типам long, int, short, byte и char — к каждому отдельному биту каждого операнда. Операторы &, | и ^ можно применять и к boolean, но тогда они работают как логические операторы без короткого замыкания.

Результаты выполнения побитовых логических операций для каждой пары битов:

1.1. Побитовое ИЛИ (OR, |)

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

  00101010   42
| 00001111   15
  --------------
  00101111   47

1.2. Побитовое И (AND, &)

Значение бита, полученное в результате выполнения побитового оператора AND, &, равно 1, если соответствующие биты в обоих операндах также равны 1. Во всех остальных случаях значение результирующего бита равно 0:

  00101010   42
& 00001111   15
  --------------
  00001010   10

1.3. Побитовое исключающее ИЛИ (XOR, ^)

Результирующий бит, полученный в результате выполнения оператора XOR, ^, равен 1, если соответствующий бит только в одном из операндов равен 1. Во всех других случаях результирующий бит равен 0:

  00101010   42
^ 00001111   15
  --------------
  00100101   37

1.4. Побитовое НЕ (NOT, ~)

Унарный оператор NOT (НЕ), ~, называемый также побитовым дополнением, инвертирует все биты операнда:

~ 00101010   42
  --------------
  11010101

Обратите внимание: здесь для наглядности показаны только младшие восемь бит. В типе int инвертируются все 32 бита, включая знаковый, поэтому ~42 равно -43 — для любого числа справедлива формула ~x == -x - 1. Почему так получается, объясняет дополнительный код.

Рассмотрим теперь применение побитовых операций в программе. В следующем примере также показан метод Integer.toBinaryString(), который возвращает двоичную запись десятичного значения:

public class BitwiseExample1 {
    public static void main(String[] args) {
        int a = 3;
        int b = 6;
        int c = a | b;
        int d = a & b;
        int e = a ^ b;
        int f = ~b;
        System.out.println("a = " + Integer.toBinaryString(a));
        System.out.println("b = " + Integer.toBinaryString(b));
        System.out.println("a | b = " + Integer.toBinaryString(c));
        System.out.println("a & b = " + Integer.toBinaryString(d));
        System.out.println("a ^ b = " + Integer.toBinaryString(e));
        System.out.println("~ b = " + Integer.toBinaryString(f));
    }
}

Вывод программы (метод toBinaryString() не печатает ведущие нули):

a = 11
b = 110
a | b = 111
a & b = 10
a ^ b = 101
~ b = 11111111111111111111111111111001

2. Битовые сдвиги: >>, >>> и <<

Битовые сдвиги смещают все двоичные разряды значения на указанное количество позиций:

Общая форма:

значение << количество

Например:

34<<3, 56>>2, 78>>>1

Для того чтобы понять, как происходит сдвиг, лучше рассмотреть его на примере двоичных чисел:

0001<<1 = 0010
0100>>1 = 0010

При сдвиге отрицательных чисел проявляется разница между операторами >> и >>>. Операция >> распространяет знаковый (левый) бит направо, а >>> заполняет освободившиеся разряды нулями. У положительных чисел результат обеих операций одинаков (отрицательные числа в примере записаны в дополнительном коде):

int i = 192;
i       00000000 00000000 00000000 11000000 (192)
i<<1    00000000 00000000 00000001 10000000 (384)
i>>1    00000000 00000000 00000000 01100000 (96)
i>>>1   00000000 00000000 00000000 01100000 (96)

int i = -192; (двоичная запись в доп. коде)
i       11111111 11111111 11111111 01000000 (-192)
i<<1    11111111 11111111 11111110 10000000 (-384)
i>>1    11111111 11111111 11111111 10100000 (-96)
i>>>1   01111111 11111111 11111111 10100000 (2147483552)

Типы byte и short продвигаются к типу int при вычислении выражения. Следующий пример показывает, к чему это приводит:

public class BitwiseExample2 {
    public static void main(String[] args) {
        byte a = 64; //0100 0000
        byte b;
        int i = a << 2; // 1 0000 0000
        b = (byte) (a << 2); //0000 0000
        System.out.println("a = " + a);
        System.out.println("i = " + i);
        System.out.println("b = " + b);
    }
}

Вывод программы:

a = 64
i = 256
b = 0

3. Побитовые операции с присваиванием

Каждой побитовой операции соответствует составная операция с присваиванием:

Есть один нюанс: составное присваивание выполняет неявное приведение к типу переменной. Поэтому byte b = 64; b <<= 2; компилируется (и по правилам из предыдущего раздела даёт 0), хотя b = b << 2; — ошибка компиляции.

4. Практическое применение побитовых операций

Побитовые операции имеют довольно широкое практическое применение. Рассмотрим некоторые случаи.

4.1. Чётность числа

Выражение x & 1 проверяет чётность числа: у чётного числа младший бит равен 0, у нечётного — 1. Поэтому результат равен 0, если число чётное, и 1, если нечётное. В условии скобки обязательны — (x & 1) == 0: из-за более низкого приоритета & запись без скобок была бы разобрана как x & (1 == 0) и не скомпилировалась.

4.2. Умножение и деление на два сдвигами

• x<<1 – умножение на 2;
• x>>1 – деление на два с отбрасыванием любого остатка.

Каждая дополнительная позиция сдвига — ещё одно умножение или деление на 2: x<<3 умножает на 8. Для отрицательных чисел x>>1 округляет вниз, а не к нулю, поэтому результат может отличаться от x/2: -5 >> 1 равно -3, тогда как -5/2 равно -2.

4.3. Шифрование числа

Операция XOR при применении два раза к одному и тому же битовому массиву восстанавливает его исходное значение. Это можно использовать при шифровании данных для передачи по сети:

C = A ^ B
A = C ^ B

Представьте, что необходимо отправить в сообщении число 560 — пин-код от банковской карты. Если злоумышленник перехватит сообщение, то узнает пин-код и сможет воспользоваться им. Чтобы этого не произошло, придумаем какое-то число — маску — и сообщим его получателю заранее. Перед отправкой зашифруем пин-код побитовой операцией XOR: message ^ mask — и отправим результат. Даже если злоумышленник перехватит сообщение, он не будет знать, как его расшифровать. Адресат же восстанавливает пин-код с помощью имеющейся маски: codedMessage ^ mask.

Следующий код иллюстрирует этот пример:

public class BitwiseExample3 {
    public static void main(String[] args) {
        int message = 560;
        int mask = 67;
        int codedMessage = message ^ mask;
        int receivedMessage = codedMessage ^ mask;
        System.out.println("message = " + message);
        System.out.println("message = " + Integer.toBinaryString(message));
        System.out.println("codedMessage = " + codedMessage);
        System.out.println("codedMessage = " + Integer.toBinaryString(codedMessage));
        System.out.println("receivedMessage = " + receivedMessage);
        System.out.println("receivedMessage = " + Integer.toBinaryString(receivedMessage));
    }
}

Вывод программы — после повторного XOR с той же маской получатель видит исходные 560:

message = 560
message = 1000110000
codedMessage = 627
codedMessage = 1001110011
receivedMessage = 560
receivedMessage = 1000110000

4.4. Наложение маски

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

  001010101
& 000100100
  --------------
  000000100

Презентацию с видео можно скачать на Patreon.