Поразрядные операции

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

Каждое число имеет определенное двоичное представление. Например, число 4 в двоичной системе 100, а число 5 - 101 и так далее.

К примеру, возьмем следующие переменные:

byte b = 7;		// 0000 0111
short s = 7;	// 0000 0000 0000 0111

Тип byte занимает 1 байт или 8 бит, соответственно представлен 8 разрядами. Поэтому значение переменной b в двоичном коде будет равно 00000111. Тип short занимает в памяти 2 байта или 16 бит, поэтому число данного типа будет представлено 16 разрядами. И в данном случае переменная s в двоичной системе будет иметь значение 0000 0000 0000 0111.

Для упрощения понимания мы можем использовать двоичную запись чисел. Например:

class Program{

    public static void main(String[] args) {  

        byte b = 0b0000_0111;               // 7
        short s = 0b0000_0000_0000_0111;	// 7
        System.out.println("byte b = " + b);        // byte b = 7
        System.out.println("short s = " + s);       // short s = 7
    }
}

Для записи чисел со знаком в Java применяется дополнительный код (two's complement), при котором старший разряд является знаковым. Если его значение равно 0, то число положительное, и его двоичное представление не отличается от представления беззнакового числа. Например, 0000 0001 в десятичной системе 1.

Если старший разряд равен 1, то мы имеем дело с отрицательным числом. Например, 1111 1111 в десятичной системе представляет -1. Соответственно, 1111 0011 представляет -13.

Рассмотрим следующий пример:

class Program{

    public static void main(String[] args) {  

        int num = 0b1111_1111_1111_1111_1111_1111_1111_1110;               // -2

        System.out.println("num = " + num);        // num = -2
    }
}

Здесь переменная num представляет значение 0b1111_1111_1111_1111_1111_1111_1111_1110 - все единицы, кроме последнего нуля (формальное первого нуля), что представляет -2. Но получим из него положительное число - 2. Сначала инвертируем число - все единицы сделаем нулями, а все нули - единицами:

// ~ - операция инверсии
~ 0b1111_1111_1111_1111_1111_1111_1111_1110
= 
  0b0000_0000_0000_0000_0000_0000_0000_0001

И далее прибавляем 1:

0b0000_0000_0000_0000_0000_0000_0000_0001
+                                       
                                        1
=
0b0000_0000_0000_0000_0000_0000_0000_0010

Число 10₂ в десятичной системе равно 2.

Логические операции

Логические операции над числами представляют поразрядные операции. В данном случае числа рассматриваются в двоичном представлении, например, 2 в двоичной системе равно 10 и имеет два разряда, число 7 - 111 и имеет три разряда.

• & (логическое умножение)

  Умножение производится поразрядно, и если у обоих операндов значения разрядов равно 1, то операция возвращает 1, иначе возвращается число 0. Например:

   int a1 = 2; //010
   int b1 = 5;//101
   System.out.println(a1&b1); // результат 0
              
  int a2 = 4; //100
  int b2 = 5; //101
  System.out.println(a2 & b2); // результат 4
  

  В первом случае у нас два числа 2 и 5. 2 в двоичном виде представляет число 010, а 5 - 101. Поразрядное умножение чисел (0*1, 1*0, 0*1) дает результат 000.

  Во втором случае у нас вместо двойки число 4, у которого в первом разряде 1, так же как и у числа 5, поэтому здесь результатом операции (1*1, 0*0, 0 *1) = 100 будет число 4 в десятичном формате.

• | (логическое сложение)

  Данная операция также производится по двоичным разрядам, но теперь возвращается единица, если хотя бы у одного числа в данном разряде имеется единица (операция "логическое ИЛИ"). Например:

  int a1 = 2; //010
  int b1 = 5;//101
  System.out.println(a1|b1); // результат 7 - 111
  int a2 = 4; //100
  int b2 = 5;//101
  System.out.println(a2 | b2); // результат 5 - 101
  

• ^ (логическое исключающее ИЛИ)

  Также эту операцию называют XOR, нередко ее применяют для простого шифрования:

  int number = 45; // 1001 Значение, которое надо зашифровать - в двоичной форме 101101
  int key = 102; //Ключ шифрования - в двоичной системе 1100110
  int encrypt = number ^ key; //Результатом будет число 1001011 или 75
  System.out.println("Зашифрованное число: " +encrypt);
  
  int decrypt = encrypt ^ key; // Результатом будет исходное число 45
  System.out.println("Расшифрованное число: " + decrypt);
  

  Здесь также производятся поразрядные операции. Если у нас значения текущего разряда у обоих чисел разные, то возвращается 1, иначе возвращается 0. Например, результатом выражения 9^5 будет число 12. А чтобы расшифровать число, мы применяем обратную операцию к результату.

• ~ (логическое отрицание или инверсия)

  Поразрядная операция, которая инвертирует все разряды числа: если значение разряда равно 1, то оно становится равным нулю, и наоборот.

  byte a = 12;                 // 0000 1100     
  System.out.println(~a);		//  1111 0011   или -13
  

Операции сдвига

Операции сдвига также производятся над разрядами чисел. Сдвиг может происходить вправо и влево.

• a<<b - сдвигает число a влево на b разрядов. Например, выражение 4<<1 сдвигает число 4 (которое в двоичном представлении 100) на один разряд влево, в результате получается число 1000 или число 8 в десятичном представлении.

• a>>b - смещает число a вправо на b разрядов. Например, 16>>1 сдвигает число 16 (которое в двоичной системе 10000) на один разряд вправо, то есть в итоге получается 1000 или число 8 в десятичном представлении.

• a>>>b - в отличие от предыдущих типов сдвигов данная операция представляет беззнаковый сдвиг - сдвигает число a вправо на b разрядов. Например, выражение -8>>>2 будет равно 1073741822.

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

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

class Program{

    public static void main(String[] args) {  

        int a = 16; // в двоичной форме 10000
        int b = 2; // в двоичной форме 00010
        int c = a << b; // Сдвиг числа 10000 влево на 2 разряда, равно 1000000 или 64 в десятичной системе
        
        System.out.println("с: " + c);    // 64
        
        int d = a >> b; // Сдвиг числа 10000 вправо на 2 разряда, равно 100 или 4 в десятичной системе
        System.out.println("d: " + d);     // 4
    }
}

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

class Program{

    public static void main(String[] args) {  

        int a = 22; // в двоичной форме 10110
        int b = 2; // в двоичной форме
        int c = a << b; // Сдвиг числа 10110 влево на 2 разряда, равно 1011000 или 88 в десятичной системе

        System.out.println("с: " + c);    // 88

        int d = a >> b; // Сдвиг числа 10110 вправо на 2 разряда, равно 101 или 5 в десятичной системе
        System.out.println("d: " + d);     // 5
    }
}

Пример практического применения операций

Многие недооценивают поразрядные операции, не понимают, для чего они нужны. Тем не менее они могут помочь в решении ряда задач. Прежде всего они позволяют нам манипулировать данными на уровне отдельных битов. Один из примеров. У нас есть три числа, которые находятся в диапазоне от 0 до 3:

int value1 = 3;  // 0b0000_0011
int value2 = 2;  // 0b0000_0010
int value3 = 1;  // 0b0000_0001

Мы знаем, что значения этих чисел не будут больше 3, и нам нужно эти данные максимально сжать. Мы можем три числа сохранить в одно число. И в этом нам помогут поразрядные операции.

class Program{

    public static void main(String[] args) {  

        int value1 = 3;  // 0b0000_0011
        int value2 = 2;  // 0b0000_0010
        int value3 = 1;  // 0b0000_0001
        int result = 0b0000_0000;
        // сохраняем в result значения из value1
        result = result | value1; // 0b0000_0011
        // сдвигаем разряды в result на 2 разряда влево
        result = result << 2;   // 0b0000_1100
        // сохраняем в result значения из value2
        result = result | value2;  // 0b0000_1110
        // сдвигаем разряды в result на 2 разряда влево
        result = result << 2;   // 0b0011_1000
        // сохраняем в result значения из value3
        result = result | value3;  // 0b0011_1001

        System.out.println(result);  // 57
    }
}

Разберем этот код. Сначала определяем все сохраняемые числа value1, value2, value3. Для хранения результата определена переменная result, которая по умолчанию равна 0. Для большей наглядности ей присвоено значение в бинарном формате:

int result = 0b0000_0000;

Сохраняем первое число в result:

result = result | value1; // 0b0000_0011

Здесь мы имеем дело с логической операцией поразрядного сложения - если один из соответствующих разрядов равен 1, то результирующий разряд тоже будет равен 1. То есть фактически

0b0000_0000
+
0b0000_0011
=
0b0000_0011

Итак, первое число сохранили в result. Мы будем сохранять числа по порядку. То есть сначала в result будет идти первое число, затем второе и далее третье. Поэтому сдвигаем число result на два разряда влево (наши числа занимают в памяти не более двух разрядов):

result = result << 2;   // 0b0000_1100

То есть фактически

0b0000_0011 << 2 =
0b0000_1100

Далее повторяем логическую операцию сложения, сохраняем второе число:

result = result | value2;  // 0b0000_1110

что эквивалентно

0b0000_1100
+
0b0000_0010
=
0b0000_1110

Далее повторяем сдвиг на два разряда влево и сохраняем третье число. В итоге мы получим в двоичном представлении число 0b0011_1001. В десятично системе это число равно 57. Но это не имеет значения, потому что нам важны конкретные биты числа. Стоит отметить, что мы сохранили в одно число три числа, и в переменной result еще есть сводобное место. Причем в реальности не важно, сколько именно битов надо сохранить. В данном случае для примера сохраняем лишь два бита.

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

class Program{

    public static void main(String[] args) {  

        int result = 0b0011_1001;
        // обратное получение данных
        int newValue3 = result & 0b000_0011;
        // сдвигаем данные на 2 разряда вправо
        result = result >> 2;
        int newValue2 = result & 0b000_0011;
        // сдвигаем данные на 2 разряда вправо
        result = result >> 2;
        int newValue1 = result & 0b000_0011;
        System.out.println(newValue1);    // 3
        System.out.println(newValue2);   // 2
        System.out.println(newValue3);   // 1
    }
}

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

int newValue3 = result & 0b000_0011;

эквивалентна

0b0011_1001
*
0b0000_0011
=
0b0000_0001

Таким образом, последнее число равно 0b0000_0001 или 1 в десятичной системе

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

result = 0b0011_1001;
int recreatedValue1 = (result & 0b0011_0000) >> 4;
System.out.println(recreatedValue1);

Здесь получаем первое число, которое, как мы знаем, занимает в числе биты 4 и 5. Для этого применяем умножение на битовую маску 0b0011_0000. И затем сдвигаем число на 4 разряда вправо.

0b0011_1001
*
0b0011_0000
=
0b0011_0000
>> 4
=
0b0000_0011

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

class Program{

    public static void main(String[] args) {  

        int value1 = 3;  // 0b0000_0011
        int value2 = 2;  // 0b0000_0010
        int value3 = 1;  // 0b0000_0001
        int result = 0b0000_0000;
        // сохраняем в result значения из value1
        result = result | (value1 << 4);
        // сохраняем в result значения из value2
        result = result | (value2 << 2);
        // сохраняем в result значения из value3
        result = result | value3;  // 0b0011_1001

        System.out.println(result);  // 57
    }
}