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

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

Существует несколько побитовых операторов, применимых к целочисленными типам long, int, short, char, byte.

Побитовый унарный оператор NOT&Побитовый AND&=Побитовый AND с присваиванием|Побитовый OR|=Побитовый OR с присваиванием^Побитовый исключающее OR^=Побитовый исключающее OR с присваиванием>>Сдвиг вправо>>=Сдвиг вправо с присваиванием>>>Сдвиг вправо с заполнением нулями>>=Сдвиг вправо с заполнением нулями с присваиванием

Все целочисленные типы представляются двоичными числами различной длины. Например, значение типа byte, равное 42, в двоичном представлении имеет вид 00101010, в котором каждая позиция представляет степень числа два.

Все целочисленные типа, за исключением char — типы со знаком, т.е. могут быть положительными или отрицательными. В Java применяется двоичное дополнение, при котором отрицательные числа представляются в результате инвертирования всех битов значения (изменения 1 на 0 и наоборот) и последующего добавления 1 к результату. Например, -42 представляется в результате инвертирования всех битов в двоичном представлении числа 42, что даёт значение 11010101, и добавления 1, что приводит к значению 110110110, или -42. Чтобы декодировать отрицательное число, необходимо вначале инвертировать все биты, а затем добавить 1 к результату. Например, инвертирование значения -42, или 11010110, приводит к значению 00101001, или 41, после добавления 1 к которому мы получим 42.

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

Побитовые логические операторы

Побитовые логические операторы — это &, |, ^,

. Побитовые операторы применяются к каждому отдельному биту каждого операнда.

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

A

Побитовое 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-разрядных значений.

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

Двоичные побитовые операторы имеют составную форму, которая объединяет побитовый оператор с оператором присваивания.

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

Побитовые операторы интерпретируют операнды как последовательность из 32 битов (нулей и единиц). Они производят операции, используя двоичное представление числа, и возвращают новую последовательность из 32 бит (число) в качестве результата.

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

Формат 32-битного целого числа со знаком

Побитовые операторы в JavaScript работают с 32-битными целыми числами в их двоичном представлении.

Это представление называется «32-битное целое со знаком, старшим битом слева и дополнением до двойки».

Разберём, как устроены числа внутри подробнее, это необходимо знать для битовых операций с ними.

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

Старший бит слева – это научное название для самого обычного порядка записи цифр (от большего разряда к меньшему). При этом, если больший разряд отсутствует, то соответствующий бит равен нулю.

Примеры представления чисел в двоичной системе:

Обратите внимание, каждое число состоит ровно из 32-битов.

Дополнение до двойки – это название способа поддержки отрицательных чисел.

Двоичный вид числа, обратного данному (например, 5 и -5 ) получается путём обращения всех битов с прибавлением 1.

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

Например, вот число 314 :

Чтобы получить -314 , первый шаг – обратить биты числа: заменить 0 на 1 , а 1 на 0 :

Второй шаг – к полученному двоичному числу прибавить единицу, обычным двоичным сложением: 11111111111111111111111011000101 + 1 = 11111111111111111111111011000110 .

Итак, мы получили:

Принцип дополнения до двойки делит все двоичные представления на два множества: если крайний-левый бит равен 0 – число положительное, если 1 – число отрицательное. Поэтому этот бит называется знаковым битом.

Список операторов

В следующей таблице перечислены все побитовые операторы. Далее операторы разобраны более подробно.

a

Побитовые операторы работают следующим образом:

1. Операнды преобразуются в 32-битные целые числа, представленные последовательностью битов. Дробная часть, если она есть, отбрасывается.
2. Для бинарных операторов – каждый бит в первом операнде рассматривается вместе с соответствующим битом второго операнда: первый бит с первым, второй со вторым и т.п. Оператор применяется к каждой паре бит, давая соответствующий бит результата.
3. Получившаяся в результате последовательность бит интерпретируется как обычное число.

Посмотрим, как работают операторы, на примерах.

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

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

Побитовые операторы JavaScript:

0101

Числовые значения в JavaScript хранятся как 64 битные числа с плавающей точкой. Однако все побитовые операции выполняются с 32 битными двоичными числами.

Перед выполнением побитовой операции JavaScript преобразует числовые операнды в 32 битные целые числа со знаком. После завершения побитовой операции результат преобразуется обратно в 64 битное число.

В примерах в таблице выше приведены 4-битные числа без знака. Поэтому

5 возвращает 10.

В действительности же JavaScript использует 32-битные числа со знаком. Таким образом, в JavaScript выражение

5 вернет не 10, а -6:

00000000000000000000000000000101 (5)
11111111111111111111111111111010 (

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

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

Если побитовое И (AND) выполняется с парой бит, то 1 возвращается тогда, когда оба бита равны 1.

Пример с 1-битовыми числами:

Пример с 4-битовыми числами:

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

Если побитовое ИЛИ (OR) выполняется с парой бит, то 1 возвращается тогда, когда один из битов равен 1.

Пример с 1-битовыми числами:

Пример с 4-битовыми числами:

Побитовое ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR)

Если побитовое ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR) выполняется с парой бит, то 1 возвращается тогда, когда биты различны.

Пример с 1-битовыми числами:

Пример с 4-битовыми числами:

Побитовое И в JavaScript (&)

Побитовое И возвращает 1 в том случае, если оба бита равны 1:

Побитовое ИЛИ в JavaScript (|)

Побитовое ИЛИ возвращает 1 в том случае, если хотя бы один из двух битов равен 1:

Побитовое ИСКЛЮЧАЮЩЕЕ ИЛИ в JavaScript (^)

Побитовое ИСКЛЮЧАЮЩЕЕ ИЛИ возвращает 1 в том случае, если у битов разное значение:

Побитовое ОТРИЦАНИЕ в JavaScript (

5

Побитовый сдвиг влево в JavaScript ( >)

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

Побитовый сдвиг вправо в JavaScript (>>>)

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

Беззнаковая арифметика в Java

Как известно, в 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 добавили просто для симметрии, с учётом того, что для сдвига вправо есть разделение на логический и арифметический. Ну а Гослинг решил не заморачиваться (и, думается, правильно сделал).