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

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

Как известно, в Java нет беззнаковых типов. Если в Си вы могли написать unsigned int ( char , long ), то в Java так не получится. Однако нередко возникает необходимость в выполнении арифметических операций именно с числами без знака. На первый взгляд кажется, что беззнаковые типы в принципе-то и не особо нужны (подумаешь, MaxInt для чисел со знаком меньше в два раза, если нужны числа больше, я просто возьму long и далее BigInteger ). Но основное различие на самом деле не в том, сколько различных неотрицательных чисел можно положить в signed или unsigned int, а в том, как над ними производятся арифметические операции и сравнения. Если вы работаете с бинарными протоколами или с двоичной арифметикой, где важен каждый используемый бит, нужно уметь выполнять все основные операции в беззнаковом режиме. Рассмотрим эти операции по порядку:

Преобразование byte в short (int, long)

Обычный каст (int) myByte выполнит расширение до 32 бит со знаком — это означает, что если старший бит байта был установлен в 1, то результатом будет то же самое отрицательное число, но записанное в 32-битном формате:

Часто это не то, чего бы мы хотели. Для того, чтобы выполнить расширение до 32 бит без знака и получить 0x000000ff , в Java можно записать:

int myInt = myByte & 0xff; short myShort = myByte & 0xff; 

Сравнение без учёта знака

Для беззнакового сравнения есть лаконичная формула:

int compareUnsigned(int a, int b)

Сложение, вычитание и умножение

А вот здесь приятный сюрприз — эти операции выполняются корректно в любом случае. Но в выражениях необходимо тщательно следить за тем, чтобы операции выполнялись с числами одного типа, так как любые неявные преобразования выполняются с расширением знака, и могут приводить к результатам, отличным от ожидаемых. Коварство таких багов в том, что ошибочный сценарий может выполняться очень редко.

Деление

Деление -256 на 256 даст нам -1. А нам бы хотелось, чтобы 0xffffff00 / 0x100 давало 0x00ffffff , а не 0xffffffff (-1) . Для byte , short и int решением будет переход к числам большей разрядности:

int a = 0xffffff00; int b = 0x100; int c = (int) ((a & 0xffffffffL) / b); // convert a to long before division 

Но что делать с long ? Переходить на BigInteger в таких случаях обычно не вариант — слишком медленно. Остаётся только брать всё в свои руки и реализовывать деление вручную. К счастью, всё уже украдено до нас — в Google Guava есть реализация беззнакового деления для long , причём довольно шустрая. Если вы не используете эту библиотеку, проще всего выдрать кусок кода прямо из файла UnsignedLongs.java:

 /** * Returns dividend / divisor, where the dividend and divisor are treated as unsigned 64-bit * quantities. * * @param dividend the dividend (numerator) * @param divisor the divisor (denominator) * @throws ArithmeticException if divisor is 0 */ public static long divide(long dividend, long divisor) < if (divisor < 0) < // i.e., divisor >= 2^63: if (compare(dividend, divisor) < 0) < return 0; // dividend < divisor >else < return 1; // dividend >= divisor > > // Optimization - use signed division if dividend < 2^63 if (dividend >= 0) < return dividend / divisor; >/* * Otherwise, approximate the quotient, check, and correct if necessary. Our approximation is * guaranteed to be either exact or one less than the correct value. This follows from fact * that floor(floor(x)/i) == floor(x/i) for any real x and integer i != 0. The proof is not * quite trivial. */ long quotient = ((dividend >>> 1) / divisor) = 0 ? 1 : 0); > 

Чтобы код компилировался, придётся также позаимствовать реализацию compare(long, long) :

 /** * Compares the two specified values, treating them as unsigned values between * and inclusive. * * @param a the first unsigned to compare * @param b the second unsigned to compare * @return a negative value if is less than ; a positive value if is * greater than ; or zero if they are equal */ public static int compare(long a, long b)

и Longs.compare(long, long) + flip(long) :

 /** * A (self-inverse) bijection which converts the ordering on unsigned longs to the ordering on * longs, that is, as unsigned longs if and only if * as signed longs. */ private static long flip(long a) < return a ^ Long.MIN_VALUE; >/** * Compares the two specified values. The sign of the value * returned is the same as that of . * * @param a the first to compare * @param b the second to compare * @return a negative value if is less than ; a positive * value if is greater than ; or zero if they are equal */ public static int compare(long a, long b) < return (a < b) ? -1 : ((a >b) ? 1 : 0); > 

Побитовые сдвиги

Чтобы окончательно покрыть тему о битовых операциях, вспомним также о сдвигах. В x86 ассемблере есть целая пачка различных команд, которые делают побитовые сдвиги — SHL, SHR, SAL, SAR, ROR, ROL, RCR, RCL. Последние 4 осуществляют циклические сдвиги, их эквивалентов в Java нет. А вот логические и арифметические сдвиги присутствуют. Логический сдвиг (не учитывает знака) — SHL (shift left) и SHR (shift right) — реализуется в Java операторами >> соответственно. С помощью логических сдвигов можно быстро выполнять целочисленные умножение и деление на числа степени двойки. Арифметический сдвиг (учитывает знак) вправо — SAR — реализуется оператором >> . Арифметический сдвиг влево эквивалентен логическому, и поэтому специального оператора для него нет. Может показаться странным, что в ассемблере есть специальный опкод для этой операции, но на самом деле он делает то же самое, то есть SAL полностью повторяет поведение SHL, и об этом прямо говорит документация от Intel:

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

a > 1; // сдвиг вправо с учётом знака (эквивалентно делению на 2) a >>> 1; // сдвиг вправо без учёта знака (эквивалентно беззнаковому делению на 2) 

Заключительные рекомендации

• При выполнении арифметических действий, которые могут привести к переполнению в выбранной разрядной сетке, нужно всегда точно представлять, какая область допустимых значений может быть у переменных, и отслеживать эти инварианты, расставляя утверждения (assertions). Например, очевидно, что при умножении двух произвольных 32-разрядных беззнаковых чисел результат может не поместиться в 32 бита, и если вам нужно избежать переполнения, нужно либо убедиться, что в этом месте никогда не будет ситуации, при которой произведение не влезает в 32 бита, либо необходимо предварительно сконвертировать оба операнда в long (выполнив a & 0xffffffffL ). Здесь, кстати, можно легко допустить ошибку, сконвертировав только один из операндов. Нет, нужно сконвертировать в long оба, т.к. если второй операнд окажется отрицательным, он будет неявно преобразован в long с расширением знака, и результат умножения будет неправильным.
• Щедро расставляйте скобки в выражениях, где используются побитовые операции. Дело в том, что приоритет побитовых операторов в Java несколько странный, и часто ведёт себя неочевидным образом. Лучше добавить пару скобок, чем потом несколько часов искать трудноуловимые ошибки.
• Если вам нужна константа типа long , не забудьте добавить суффикс L в конец литерала константы. Если этого не сделать, это будет не long , а int , и при неявном приведении к long снова произойдёт неприятное нам расширение со знаком.

Источник

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

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

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

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

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

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

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

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

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

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

Пример сложения «столбиком» (14₁₀ + 5₁₀ = 19₁₀ или 1110₂ + 101₂ = 10011₂):

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

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

Пример умножения «столбиком» (14₁₀ * 5₁₀ = 70₁₀ или 1110₂ * 101₂ = 1000110₂):

×	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:

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).
• Работа с графикой.
• Работа с сетью.

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

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

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

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

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

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

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

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

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

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

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

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

Источник