Содержание
Существует несколько побитовых операторов, применимых к целочисленными типам long, int, short, char, byte.
Все целочисленные типы представляются двоичными числами различной длины. Например, значение типа byte, равное 42, в двоичном представлении имеет вид 00101010, в котором каждая позиция представляет степень числа два.
Все целочисленные типа, за исключением char — типы со знаком, т.е. могут быть положительными или отрицательными. В Java применяется двоичное дополнение, при котором отрицательные числа представляются в результате инвертирования всех битов значения (изменения 1 на 0 и наоборот) и последующего добавления 1 к результату. Например, -42 представляется в результате инвертирования всех битов в двоичном представлении числа 42, что даёт значение 11010101, и добавления 1, что приводит к значению 110110110, или -42. Чтобы декодировать отрицательное число, необходимо вначале инвертировать все биты, а затем добавить 1 к результату. Например, инвертирование значения -42, или 11010110, приводит к значению 00101001, или 41, после добавления 1 к которому мы получим 42.
Двоичное дополнение используется в большинстве компьютерных языков. Опустим теорию, нужно только помнить, что старший бит определяет знак целого числа.
Побитовые логические операторы
Побитовые логические операторы — это &, |, ^,
. Побитовые операторы применяются к каждому отдельному биту каждого операнда.
Результаты выполнения побитовых логических операторов
| A | B | A | B | A & B | A ^ B | |
|---|---|---|---|---|---|
| 1 | |||||
| 1 | 1 | 1 | |||
| 1 | 1 | 1 | 1 | ||
| 1 | 1 | 1 | 1 |
Побитовое OR (|)
Результирующий бит, полученный в результате выполнения оператора OR, |, равен 1, если соответствующий бит в любом из операндов равен 1.
Побитовое AND (&)
Значение бита, полученное в результате выполнения побитового оператора AND, &, равно 1, если соответствующие биты в операндах также равны 1. Во всех остальных случаях значение результирующего бита равно 0.
Побитовое XOR (^)
Результирующий бит, полученный в результате выполнения оператора XOR, ^, равен 1, если соответствующий бит только в одном из операндов равен 1. Во всех других случаях результирующий бит равен 0.
Данный оператор обладает полезной особенностью, часто используемый в программировании. Например, можно обменять значения переменных без использования дополнительной переменной
Но увлекаться такой записью не стоит, это работает медленнее и код менее читаем.
Гораздо шире используется XOR для шифрования. В простейшем виде это выглядит так. Есть текст, к которому применяется ключ с оператором XOR. Зашифрованное сообщение передаётся человеку, который знает ключ. Всё, что ему нужно сделать — это применить к зашифрованному тексту тот же ключ, используемый для шифровки и текст снова станет читаемым.
Ниже приводится приблизительный пример работы шифровки/дешифровки текста. С русским текстом пример не будет работать, так как используются разные кодировки и требуется писать дополнительный код. Итак, у нас есть некий текст, который мы зашифровали с помощью ключа (meow) и передали полученный набор байтов другому человеку. Если кто-то перехватит ваше сообщение, то увидит просто набор символов. А ваш сообщник сможет прочитать сообщение, так как вы заранее условились, каким будем ключ для расшифровки.
Побитовое NOT (
Унарный оператор NOT (Не),
, называемый также побитовым дополнением, инвертирует все биты операнда. Например, число 42 в битовом представлении имеет вид:
В результате применения оператора NOT преобразуется в значение:
Сдвиг влево
Оператор сдвига влево, >, смещает все биты значения вправо на указанное количество позиций:
Вы указываете количество позиций, на которое нужно сдвинуть вправо биты в значении. Следующий код выполняет сдвиг право на две позиции в значении 32, в результате чего значение переменной станет равным 8.
Крайние биты при сдвиге просто теряются. Например, значение 35 при сдвиге вправо на две позиции также приводит к значению 8, так как теряются два младщих бита.
При каждом сдвиге вправо выполняется деление на два с отбрасыванием любого остатка. Данная операция намного эффективнее, чем обычное деление на два, поэтому часто используется в сложных вычислениях. При этом нужно быть уверенным, что никакие биты не будут сдвинуты за пределы правой границы.
При выполнении сдвига вправо старшие (расположенные в крайних левых позициях) биты, освобожденные в результате сдвига, заполняются предыдущим содержимым старшего бита. Этот эффект называется дополнительных знаковым разрядом и служит для сохранения знака отрицательных чисел при их сдвиге.
Обратите внимание, что результат сдвига вправо значения -1 всегда равен -1, поскольку дополнительные знаковые разряды добавляют новые единицы к старшим битам.
Иногда при выполнении сдвига вправо появление дополнительных знаковых разрядов нежелательно. В этом случае используется маскировка за счёт объединения значения со значением 0x0f оператором AND, что приводит к отбрасыванию любых битов дополнительных знаковых разрядов.
Сдвиг вправо без учёта знака
Как было показано выше, при каждом выполнении оператор >> автоматически заполняет старший бит его предыдущим содержимым. В результате знак значения сохраняется. Однако иногда это нежелательно. Например, при работе со значениями пикселей и графическими изображениями. Как правило, в этих случаях требуется сдвиг нуля в позицию старшего бита независимо от его первоначального значения. Такое действие называют сдвигом вправо без учета знака, когда всегда вставляется нуль в позицию старшего бита.
Допустим, мы хотим сдвинуть вправо на 24 бит значение -1 (в двоичном представлении 11111111 11111111 11111111 11111111):
Оператор >>> не столь полезен, поскольку имеет смысл только для 32- и 64-разрядных значений.
Побитовые составные операторы с присваиванием
Двоичные побитовые операторы имеют составную форму, которая объединяет побитовый оператор с оператором присваивания.
Битовые операции в Java.
Java позволяет манипулировать числами на битовом уровне, что означает работу с битами, из которых состоит число, а именно с его представлением в двоичной системе счисления. Что же такое система счисления вообще и двоичная система в частности?
Система счисления — символический метод записи чисел, представление чисел с помощью письменных знаков. Количество цифр, используемых в системе счисления, называется её «основанием».
Позиционные системы счисления — это системы счисления, в которых значение цифры напрямую зависит от её положения в числе.
Двоичная система счисления — позиционная система счисления с основанием 2. В двоичной системе счисления числа записываются с помощью двух символов (0 и 1).
Двоичная арифметика.
Таблица сложения
| + | 1 | |
|---|---|---|
| 1 | ||
| 1 | 1 | 10(перенос в старший разряд) |
Таблица вычитания
| — | 1 | |
|---|---|---|
| д | ||
| 1 | (заём из старшего разряда) 1 |
Пример сложения «столбиком» (1410 + 510 = 1910 или 11102 + 1012 = 100112):
| + | 1 | 1 | 1 | |
|---|---|---|---|---|
| 1 | 1 | |||
| 1 | 1 | 1 |
Таблица умножения
| × | 1 | |
|---|---|---|
| 1 | 1 |
Пример умножения «столбиком» (1410 * 510 = 7010 или 11102 * 1012 = 10001102):
| × | 1 | 1 | 1 | |||
|---|---|---|---|---|---|---|
| 1 | 1 | |||||
| + | 1 | 1 | 1 | |||
| 1 | 1 | 1 | ||||
| 1 | 1 | 1 |
Эти операции работают с целочисленными типами данных
| Тип | Размер (бит) | Диапазон |
|---|---|---|
| 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 | 1 | 1 | ||
| 1 | 1 | 1 | ||
| 1 | 1 | 1 | 1 | |
Первые четыре оператора представляют собой применение битовых масок к аргументу в соответствие с логическими функциями. Например, оператор & применяется для поиска элемента в 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:
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 > 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
Как известно, в Java нет беззнаковых типов. Если в Си вы могли написать unsigned int ( char , long ), то в Java так не получится. Однако нередко возникает необходимость в выполнении арифметических операций именно с числами без знака. На первый взгляд кажется, что беззнаковые типы в принципе-то и не особо нужны (подумаешь, MaxInt для чисел со знаком меньше в два раза, если нужны числа больше, я просто возьму long и далее BigInteger ). Но основное различие на самом деле не в том, сколько различных неотрицательных чисел можно положить в signed или unsigned int, а в том, как над ними производятся арифметические операции и сравнения. Если вы работаете с бинарными протоколами или с двоичной арифметикой, где важен каждый используемый бит, нужно уметь выполнять все основные операции в беззнаковом режиме. Рассмотрим эти операции по порядку:
Преобразование byte в short (int, long)
Обычный каст (int) myByte выполнит расширение до 32 бит со знаком — это означает, что если старший бит байта был установлен в 1, то результатом будет то же самое отрицательное число, но записанное в 32-битном формате:
0xff -> 0xffffffff (-1)
Часто это не то, чего бы мы хотели. Для того, чтобы выполнить расширение до 32 бит без знака и получить 0x000000ff , в Java можно записать:
Сравнение без учёта знака
Для беззнакового сравнения есть лаконичная формула:
Для byte, short и long, соответственно, константы будут 0x80 , 0x8000 и 0x8000000000000000L .
Сложение, вычитание и умножение
А вот здесь приятный сюрприз — эти операции выполняются корректно в любом случае. Но в выражениях необходимо тщательно следить за тем, чтобы операции выполнялись с числами одного типа, так как любые неявные преобразования выполняются с расширением знака, и могут приводить к результатам, отличным от ожидаемых. Коварство таких багов в том, что ошибочный сценарий может выполняться очень редко.
Деление
Деление -256 на 256 даст нам -1. А нам бы хотелось, чтобы 0xffffff00 / 0x100 давало 0x00ffffff , а не 0xffffffff (-1) . Для byte , short и int решением будет переход к числам большей разрядности:
Но что делать с long ? Переходить на BigInteger в таких случаях обычно не вариант — слишком медленно. Остаётся только брать всё в свои руки и реализовывать деление вручную. К счастью, всё уже украдено до нас — в Google Guava есть реализация беззнакового деления для long , причём довольно шустрая. Если вы не используете эту библиотеку, проще всего выдрать кусок кода прямо из файла UnsignedLongs.java:
Чтобы код компилировался, придётся также позаимствовать реализацию compare(long, long) :
и Longs.compare(long, long) + flip(long) :
Побитовые сдвиги
The shift arithmetic left (SAL) and shift logical left (SHL) instructions perform the same operation; they shift the bits in the destination operand to the left (toward more significant bit locations). For each shift count, the most significant bit of the destination operand is shifted into the CF flag, and the least significant bit is cleared (see Figure 7-7 in the Intel®64 and IA-32 Architectures Software Developer’sManual, Volume 1).
То есть SAL добавили просто для симметрии, с учётом того, что для сдвига вправо есть разделение на логический и арифметический. Ну а Гослинг решил не заморачиваться (и, думается, правильно сделал).
Загрузка...
