Битовые операции в Java.

Автор: Андрей Самойлов


Bit stream

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

Система счисления - символический метод записи чисел, представление чисел с помощью письменных знаков. Количество цифр, используемых в системе счисления, называется её «основанием».

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

Двоичная система счисления - позиционная система счисления с основанием 2. В двоичной системе счисления числа записываются с помощью двух символов (0 и 1).

Двоичная арифметика.

Таблица сложения

+ 0 1
0 0 1
1 1 10(перенос
в старший
разряд)

Таблица вычитания

- 0 1
0 0 д
1 (заём из
старшего
разряда) 1
0

Пример сложения «столбиком» (1410 + 510 = 1910 или 11102 + 1012 = 100112):

+ 1 1 1 0
1 0 1
1 0 0 1 1

Таблица умножения

× 0 1
0 0 0
1 0 1

Пример умножения «столбиком» (1410 * 510 = 7010 или 11102 * 1012 = 10001102):

× 1 1 1 0
1 0 1
+ 1 1 1 0
1 1 1 0
1 0 0 0 1 1 0

Эти операции работают с целочисленными типами данных

Тип Размер (бит) Диапазон
byte 8 бит от -128 до 127
short 16 бит от -32768 до 32767
char 16 бит от 0 до 65535
int 32 бит от -2147483648 до 2147483647
long 64 бит от -9223372036854775808
до +9223372036854775807

Таблица истинности побитовых операций выглядит следующим образом

A B A & B A | B A ^ B
1 0 0 1 1
0 1 0 1 1
1 1 1 1 0
0 0 0 0 0

Первые четыре оператора представляют собой применение битовых масок к аргументу в соответствие с логическими функциями. Например, оператор & применяется для поиска элемента в HashMap по формуле h & (length -1), где h - хэшкод элемента, а length - длина массива

Наибольший интерес представляют операторы сдвига. Первым операндом оператора сдвига является число, которое нужно обработать, а вторым - количество бит, на которое следует выполнить сдвиг. Результатом операции сдвига является двоичное представление числа, сдвинутое в заданном направлении. Знаковые сдвиги также называют арифметическими, а беззнаковые - логическими.


Представление отрицательных чисел в Java.

Для хранения отрицательных чисел используется дополнительный код или второе дополнение (two's complement). Положительное число преобразуется в отрицательное число путём инвертирования его бит с добавлением единицы.

Пример: Преобразование 32-битного числа 5 = 101:

Исходное число:   0000 0000 0000 0000 0000 0000 0000 0101
Инвертируем:         1111 1111 1111 1111 1111 1111 1111 1010
Прибавляем 1:       0000 0000 0000 0000 0000 0000 0000 0001
Результат:               1111 1111 1111 1111 1111 1111 1111 1011


Знаковый сдвиг влево (<<)

Сдвигает двоичное представление первого операнда влево на количество бит, заданное во втором операнде, знак числа сохраняется. Младшие(крайние правые) биты при этом заполняются нулями. Соответствует умножению на 2.

Примеры:

27 (11011) << 1 = 54 (110110)
-5 (11111111111111111111111111111011) << 1 = 11111111111111111111111111111011


Если число выходит за границы диапазона типа int, крайний бит теряется:

2 147 483 647 (1111111111111111111111111111111) << 1 = -2 (11111111111111111111111111111110)

Почему не существует беззнакового(логического) сдвига влево? Потому что такой сдвиг не оказывает влияния на старший значащий бит(MSB) - крайний левый бит числа, изменяются только крайние правые биты. Кроме того, в процессорах семейства 8086 арифметический и логический сдвиг выполняют одну и ту же операцию.


Знаковый сдвиг вправо (>>)

Сдвигает двоичное представление первого операнда вправо на количество бит, заданное во втором операнде, знак числа сохраняется. Старшие(крайние левые биты) заполняются нулями. Соответствует делению на 2:

24 (11000) >> 1 = 12 (1100)
-4 (11111111111111111111111111111100) >> 1 = -2 (11111111111111111111111111111110)


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

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

24 (11000) >>> 1 = 12 (1100)
-24 (1111 1111 1111 1111 1111 1111 1110 1000) >>> 1 = 2147483636 (0111 1111 1111 1111 1111 1111 1111 0100)

Можно увидеть, что знаковый бит был заменён нулём


Особенности работы операторов сдвига

Операторы сдвига всегда возвращают тип int, даже если аргумент типа, например, byte. поэтому следующий код вернёт ошибку:

byte n = 27;
n = n << 1;

java: possible loss of precision
  required: byte
  ound: int

Устранить ошибку можно путём приведения к типу byte:
n = (byte) (n << 1);

Нельзя сдвинуть на количество бит, большее, чем разрядность операнда. При этом происходит неявное сокращение правого (кол-во бит) операнда.

Пример:

Если сдвинуть данное число на 32 бита, по идее, результат должен состоять из одних нулей, но на самом деле это не так:

-1 (11111111111111111111111111111111) >> 32 = -1 (11111111111111111111111111111111)
-1(11111111111111111111111111111111) >>> 32 = -1 (11111111111111111111111111111111)


Примеры применения битовых операций

  • Ускорение операций умножения и деления чисел на два. Примеры можно увидеть в стандартной библиотеке jdk.
  • Битовые поля(флаги). Пример пусть есть права на доступ - чтение, запись, выполнение. Их удобнее хранить не в трёх разных переменных, а в одной, устанавливая соответствующие биты.
  • Алгоритмы шифрования и сжатия (например, Шифр Вернама построен на XOR).
  • Работа с графикой.
  • Работа с сетью.

Задача 1:

Пусть у нас есть A и B. Необходимо поменять их местами без использования дополнительной переменной.

A = A + B
B = A – B // После этого B становится A, т.к. в действительности получаем (A + B) – B = A
A = A – B

В этом решении есть большой минус: возможность переполнения. Поэтому лучше использовать поразрядную операцию XOR.

A = A ^ B
B = A ^ B
A = A ^ B

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

Рассмотрим обмен чисел 5 и 9.

A = 0101 ^ 1001 = 1100
B = 1100 ^ 1001 = 0101
A = 1100 ^ 0101 = 1001


Задача 2:

Даны два числа K, N. Необходимо вычислить арифметическое выражение вида:

K * 2^N, используя только битовые операции.

Входные данные: K, N - натуральные числа, где K от 1 до 10^3, N от 1 до 20

Вывод: результат выражения K * 2^N

Пример: K = 3, N = 4

Ответ: 48

Реализация:
Умножение числа на 2 в степени N эквивалентно сдвигу влево на N позиций.
K << N = 3 << 4 = 11 << 4 = 110000 = 48


Задача 3:

Реализуйте Java метод, который возвращает количество бит, которое необходимо поменять для преобразования числа X в число Y и наоборот. Метод должен принимать два различных целых числа на входе. Например, для чисел 12 и 16 метод должен вернуть 3.

Для решения данной задачи следует применить оператор XOR(^), поскольку результат для чисел X и Y будет двоичным числом, каждый бит которого будет равен 1, если их биты отличаются между собой, или 0, когда биты одинаковы. Так, например, если мы применим XOR к 1001 и 0101, результат операции XOR будет 1100, потому что два крайних левых бита отличаются друг от друга,поэтому результат XOR'ing этих двух бит будет 1, а двумя самыми правыми битами в нашем входы одинаковы, поэтому результат XOR будет равен 0.

Реализация будет выглядеть следующим образом:

                public static int findNumberOfBits(int x, int y) {
                    int bitCount = 0;
                    int z = x ^ y;  //XOR x and y
                    while (z != 0) {
                       //увеличим счётчик, если последняя двоичная цифра = 1
                        bitCount += z & 1;
                        z = z >> 1;  //сдвигаем z на единицу вправо
                    }
                    return bitCount;
                }