Java unsigned byte array

Беззнаковая арифметика в 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 снова произойдёт неприятное нам расширение со знаком.

Источник

Unsigned byte in Java

Java does not have unsigned data types. Your options are:

• Use a wider datatype such as short , char or int
• Use a byte and “manually” interpret it as unsigned (described below)

An unsigned byte

A byte is always signed in Java, but nothing prevents you from viewing a byte simply as 8 bits and interpret those bits as a value between 0 and 255.

Java byte value	Bits	Interpreted as unsigned
0	00000000	0
1	00000001	1
⋮	⋮	⋮
127	01111111	127
−128	10000000	128
⋮	⋮	⋮
−2	11111110	254
−1	11111111	255

Keep in mind that there’s nothing you can do to force your interpretation upon someone else’s method. If a method accepts a byte , then that method accepts a value between −128 and 127 unless explicitly stated otherwise.

Here are a couple of useful conversions / manipulations.

Printing an unsigned byte

Use Byte.toUnsignedInt and print the resulting int :

byte b = (byte) 0b10010110; // -106 signed, or 150 unsigned System.out.println("Value of my unsigned byte: " + Byte.toUnsignedInt(b)); // 150 

Converting from int to unsigned byte

Casting to byte throws away all but the lowest 8 bits.

int i = 150; // 00000000 00000000 00000000 10010110 byte b = (byte) i; // 10010110 System.out.println(b); // -106 System.out.println(Byte.toUnsignedInt(b)); // 150 

Converting from unsigned byte to int

byte b = (byte) 0b10010110; // -106 or 150 int signed = b; // -106 (with sign extension) int unsigned = Byte.toUnsignedInt(b); // 150 (without sign extension) 

Parsing an unsigned byte

byte b = (byte) Integer.parseInt("150"); System.out.println(Byte.toUnsignedInt(b)); // 150 

byte b = UnsignedBytes.parseUnsignedByte("150"); 

Compare unsigned byte s

Convert to int and compare.

int cmp = Integer.compare(Byte.toUnsignedInt(b1), Byte.toUnsignedInt(b2)) // cmp = -1 => b1 < b2// cmp = 0 => b1 = b2 // cmp = 1 => b1 > b2 

int cmp = UnsignedBytes.compare(b1, b2); 

Arithmetics

The 2-complement representation “just works” for addition, subtraction and multiplication.

// two unsigned bytes byte b1 = (byte) 200; byte b2 = (byte) 15; byte sum = (byte) (b1 + b2); // 215 byte diff = (byte) (b1 - b2); // 185 byte prod = (byte) (b2 * b2); // 225 

Division requires conversion of operands, and then convertion of result back to byte .

byte ratio = (byte) (Byte.toUnsignedInt(b1) / Byte.toUnsignedInt(b2)); 

Источник