- PVSM.RU - https://www.pvsm.ru -
Как известно, в Java нет беззнаковых типов. Если в Си вы могли написать unsigned int
(char
, long
), то в Java так не получится. Однако нередко возникает необходимость в выполнении арифметических операций именно с числами без знака. На первый взгляд кажется, что беззнаковые типы в принципе-то и не особо нужны (подумаешь, MaxInt
для чисел со знаком меньше в два раза, если нужны числа больше, я просто возьму long
и далее BigInteger
). Но основное различие на самом деле не в том, сколько различных неотрицательных чисел можно положить в signed или unsigned int, а в том, как над ними производятся арифметические операции и сравнения. Если вы работаете с бинарными протоколами или с двоичной арифметикой, где важен каждый используемый бит, нужно уметь выполнять все основные операции в беззнаковом режиме. Рассмотрим эти операции по порядку:
Обычный каст (int) myByte
выполнит расширение до 32 бит со знаком — это означает, что если старший бит байта был установлен в 1, то результатом будет то же самое отрицательное число, но записанное в 32-битном формате:
0xff -> 0xffffffff (-1)
Часто это не то, чего бы мы хотели. Для того, чтобы выполнить расширение до 32 бит без знака и получить 0x000000ff
, в Java можно записать:
int myInt = myByte & 0xff;
short myShort = myByte & 0xff;
Для беззнакового сравнения есть лаконичная формула:
int compareUnsigned(int a, int b) {
return Integer.compare( a ^ 0x80000000, b ^ 0x80000000 );
}
Для byte, short и long, соответственно, константы будут 0x80
, 0x8000
и 0x8000000000000000L
.
А вот здесь приятный сюрприз — эти операции выполняются корректно в любом случае. Но в выражениях необходимо тщательно следить за тем, чтобы операции выполнялись с числами одного типа, так как любые неявные преобразования выполняются с расширением знака, и могут приводить к результатам, отличным от ожидаемых. Коварство таких багов в том, что ошибочный сценарий может выполняться очень редко.
Деление -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 [1] есть реализация беззнакового деления для long
, причём довольно шустрая. Если вы не используете эту библиотеку, проще всего выдрать кусок кода прямо из файла UnsignedLongs.java [2]:
/**
* 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) << 1;
long rem = dividend - quotient * divisor;
return quotient + (compare(rem, divisor) >= 0 ? 1 : 0);
}
Чтобы код компилировался, придётся также позаимствовать реализацию compare(long, long)
:
/**
* Compares the two specified {@code long} values, treating them as unsigned values between
* {@code 0} and {@code 2^64 - 1} inclusive.
*
* @param a the first unsigned {@code long} to compare
* @param b the second unsigned {@code long} to compare
* @return a negative value if {@code a} is less than {@code b}; a positive value if {@code a} is
* greater than {@code b}; or zero if they are equal
*/
public static int compare(long a, long b) {
return Longs.compare(flip(a), flip(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, {@code a <= b} as unsigned longs if and only if {@code flip(a) <= flip(b)}
* as signed longs.
*/
private static long flip(long a) {
return a ^ Long.MIN_VALUE;
}
/**
* Compares the two specified {@code long} values. The sign of the value
* returned is the same as that of {@code ((Long) a).compareTo(b)}.
*
* @param a the first {@code long} to compare
* @param b the second {@code long} to compare
* @return a negative value if {@code a} is less than {@code b}; a positive
* value if {@code a} is greater than {@code b}; 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)
a >>> 1; // сдвиг вправо без учёта знака (эквивалентно беззнаковому делению на 2)
a & 0xffffffffL
). Здесь, кстати, можно легко допустить ошибку, сконвертировав только один из операндов. Нет, нужно сконвертировать в long оба, т.к. если второй операнд окажется отрицательным, он будет неявно преобразован в long с расширением знака, и результат умножения будет неправильным. long
, не забудьте добавить суффикс L
в конец литерала константы. Если этого не сделать, это будет не long
, а int
, и при неявном приведении к long
снова произойдёт неприятное нам расширение со знаком.Автор: elw00d
Источник [3]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/java/62045
Ссылки в тексте:
[1] Google Guava: https://code.google.com/p/guava-libraries/
[2] UnsignedLongs.java: https://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/primitives/UnsignedLongs.java
[3] Источник: http://habrahabr.ru/post/225901/
Нажмите здесь для печати.