Вредоносное ПО (malware) - это назойливые или опасные программы,...
Как известно, в 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 можно записать:
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 есть реализация беззнакового деления для long , причём довольно шустрая. Если вы не используете эту библиотеку, проще всего выдрать кусок кода прямо из файла :
/**
* 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)
- При выполнении арифметических действий, которые могут привести к переполнению в выбранной разрядной сетке, нужно всегда точно представлять, какая область допустимых значений может быть у переменных, и отслеживать эти инварианты, расставляя утверждения (assertions). Например, очевидно, что при умножении двух произвольных 32-разрядных беззнаковых чисел результат может не поместиться в 32 бита, и если вам нужно избежать переполнения, нужно либо убедиться, что в этом месте никогда не будет ситуации, при которой произведение не влезает в 32 бита, либо необходимо предварительно сконвертировать оба операнда в long (выполнив a & 0xffffffffL). Здесь, кстати, можно легко допустить ошибку, сконвертировав только один из операндов. Нет, нужно сконвертировать в long оба, т.к. если второй операнд окажется отрицательным, он будет неявно преобразован в long с расширением знака, и результат умножения будет неправильным.
- Щедро расставляйте скобки в выражениях, где используются побитовые операции. Дело в том, что приоритет побитовых операторов в Java несколько странный, и часто ведёт себя неочевидным образом. Лучше добавить пару скобок, чем потом несколько часов искать трудноуловимые ошибки.
- Если вам нужна константа типа long , не забудьте добавить суффикс L в конец литерала константы. Если этого не сделать, это будет не long , а int , и при неявном приведении к long снова произойдёт неприятное нам расширение со знаком.
Операторы в языке Java - это специальные символы, которые сообщают транслятору о том, что вы хотите выполнить операцию с некоторыми операндами. Некоторые операторы требуют одного операнда, их называют унарными. Одни операторы ставятся перед операндами и называются префиксными, другие - после, их называют постфиксными операторами. Большинство же операторов ставят между двумя операндами, такие операторы называются инфиксными бинарными операторами. Существует тернарный оператор, работающий с тремя операндами.
В Java имеется 44 встроенных оператора. Их можно разбить на 4 класса - арифметические, битовые, операторы сравнения и логические.
Арифметические операторы
Арифметические операторы используются для вычислений так же как в алгебре (см. таблицу со сводкой арифметических операторов ниже). Допустимые операнды должны иметь числовые типы. Например, использовать эти операторы для работы с логическими типами нельзя, а для работы с типом char можно, поскольку в Java тип char - это подмножество типа int.
Оператор |
Результат |
Оператор |
Результат |
Сложение |
сложение с присваиванием |
||
вычитание (также унарный минус) |
вычитание с присваиванием |
||
Умножение |
умножение с присваиванием |
||
деление с присваиванием |
|||
деление по модулю |
деление по модулю с присваиванием |
||
Инкремент |
декремент |
Четыре арифметических действия
Ниже, в качестве примера, приведена простая программа, демонстрирующая использование операторов. Обратите внимание на то, что операторы работают как с целыми литералами, так и с переменными.
class BasicMath{ public static void int a = 1 + 1;
intb = a *3;
main(String args) {
int c = b / 4;
int d = b - а;
int e = -d;
System.out.println("a =" +а);
System.out.println("b =" +b);
System.out.println("c =" +c);
System.out.println("d =" +d);
System.out.println("e =" +e);
} }
Исполнив эту программу, вы должны получить приведенный ниже результат:
C: \> java BasicMath
a = 2
b = 6
c = 1
d = 4
e = -4
Оператор деления по модулю
Оператор деления по модулю, или оператор mod, обозначается символом %. Этот оператор возвращает остаток от деления первого операнда на второй. В отличие от C++, функция mod в Java работает не только с целыми, но и с вещественными типами. Приведенная ниже программа иллюстрирует работу этого оператора.
class Modulus {
public static void main (String args ) {
int x = 42;
double у = 42.3;
System.out.println("x mod 10 = " + x % 10);
System.out.println("y mod 10 = " + у % 10);
} }
Выполнив эту программу, вы получите следующий результат:
С:\> Modulus
x mod 10 = 2
y mod 10 = 2.3
Арифметические операторы присваивания
Для каждого из арифметических операторов есть форма, в которой одновременно с заданной операцией выполняется присваивание. Ниже приведен пример, который иллюстрирует использование подобной разновидности операторов.
class OpEquals {
int a = 1;
int b = 2;
int с = 3;
a += 5;
b *= 4;
c += a * b;
с %= 6;
} }
А вот и результат, полученный при запуске этой программы:
С:> Java OpEquals
а = 6
b = 8
с = 3
Инкремент и декремент
В С существует 2 оператора, называемых операторами инкремента и декремента (++ и --) и являющихся сокращенным вариантом записи для сложения или вычитания из операнда единицы. Эти операторы уникальны в том плане, что могут использоваться как в префиксной, так и в постфиксной форме. Следующий пример иллюстрирует использование операторов инкремента и декреме нта.
class IncDec {
public static void main(String args) {
int a = 1;
int b = 2;
int c = ++b;
int d = a++;
c++;
System.out.println("a = " + a);
System.out.println("b = " + b);
System.out.println("c = " + c);
} }
Результат выполнения данной программы будет таким:
C:\ java IncDec
a = 2
b = 3
c = 4
d = 1
Целочисленные битовые операторы
Для целых числовых типов данных - long, int, short, char и byte, определен дополнительный набор операторов, с помощью которых можно проверять и модифицировать состояние отдельных битов соответствующих значений. В таблице приведена сводка таких операторов. Операторы битовой арифметики работают с каждым битом как с самостоятельной величиной.
Оператор |
Результат |
Оператор |
Результат |
побитовое унарное отрицание (NOT) |
|||
побитовое И (AND) |
побитовое И (AND) с присваиванием |
||
побитовое ИЛИ (OR) |
побитовое ИЛИ (OR) с присваиванием |
||
побитовое исключающее ИЛИ (XOR) |
побитовое исключающее ИЛИ (XOR) с присваиванием |
||
сдвиг вправо |
сдвиг вправо с присваиванием |
||
сдвиг вправо с заполнением нулями |
сдвиг вправо с заполнением нулями с присваиванием |
||
сдвиг влево |
сдвиг влево с присваиванием |
Пример программы, манипулирующей с битами
В таблице, приведенной ниже, показано, как каждый из операторов битовой арифметики воздействует на возможные комбинации битов своих операндов. Приведенный после таблицы пример иллюстрирует использование этих операторов в программе на языке Java.
class Bitlogic {
public static void main(String args ) {
String binary = { "OOOO", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001","1010", "1011", "1100", "1101",
"1110", "1111" };
int a = 3;//0+2+1или двоичное 0011
int b = 6;//4+2+0или двоичное 0110
int c = a | b;
int d = a & b;
int e = a ^ b;
int f = (~a & b) | (a & ~b);
int g = ~a & 0x0f;
System.out.println(" a = " + binary[a]);
System.out.println(" b = " + binary[b]);
System.out.println(" ab = " + binary[c]);
System.out.println(" a&b = " + binary[d]);
System.out.println(" a^b = " + binary[e]);
System.out.рrintln("~a&b|а^~Ь = " + binary[f]);
System.out.println(" ~a = " + binary[g]);
} }
Ниже приведен результат, полученный при выполнении этой программы:
С: \> Java BitLogic
a = 0011
b = 0110
a | b = 0111
a & b = 0010
a ^ b = 0101
~a & b | a & ~b = 0101
~а = 1100
Сдвиги влево и вправо
Оператор << выполняет сдвиг влево всех битов своего левого операнда на число позиций, заданное правым операндом. При этом часть битов в левых разрядах выходит за границы и теряется, а соответствующие правые позиции заполняются нулями. В предыдущей главе уже говорилось об автоматическом повышении типа всего выражения до int в том случае если в выражении присутствуют операнды типа int или целых типов меньшего размера. Если же хотя бы один из операндов в выражении имеет тип long, то и тип всего выражения повышается до long.
Оператор >> означает в языке Java сдвиг вправо. Он перемещает все биты своего левого операнда вправо на число позиций, заданное правым операндом.Когда биты левого операнда выдвигаются за самую правую позицию слова, они теряются. При сдвиге вправо освобождающиеся старшие (левые) разряды сдвигаемого числа заполняются предыдущим содержимым знакового разряда. Такое поведение называют расширением знакового разряда.
В следующей программе байтовое значение преобразуется в строку, содержащую его шестнадцатиричное представление. Обратите внимание - сдвинутое значение приходится маскировать, то есть логически умножать на значение 0 х0 f, для того, чтобы очистить заполняемые в результате расширения знака биты и понизить значение до пределов, допустимых при индексировании массива шестнадцатиричных цифр.
classHexByte {
char hex = { "0", "1, "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f };
byte b = (byte) 0xf1;
System.out.println(“b = 0x” + hex[(b >> 4) & 0x0f] + hex);
} }
Ниже приведен результат работы этой программы:
С:\> java HexByte
b = 0xf1
Беззнаковый сдвиг вправо
Часто требуется, чтобы при сдвиге вправо расширение знакового разряда не происходило, а освобождающиеся левые разряды просто заполнялись бы нулями.
class ByteUShift{
static public void main(String args) {
char hex = { "0", "1’, "2", "3", "4","5", "6", "7", "8", "9", "а", "b", "с", "d","e", "f’ };
byte b = (byte) 0xf1;
byte c = (byte) (b >> 4);
byte d = (byte) (b >> 4);
byte e = (byte) ((b & 0xff) >> 4);
System.out.println(" b = 0x" + hex(b >> 4) & 0x0f] + hex);
System.out.println(“ b >> 4 =0x" + hex[(c >> 4) & 0x0f] + hex);
System.out.println(“b >>> 4 = 0x" + hex[(d >> 4) & 0x0f] + hex);
System.out.println(“(b & 0xff) >> 4 = 0x" + hex[(e >> 4) & 0x0f] + hex);
} }
Для этого примера переменную b можно было бы инициализировать произвольным отрицательным числом, мы использовали число с шестнадцатиричным представлением 0xf1. Переменной с присваивается результат знакового сдвига b вправо на 4 разряда. Как и ожидалось, расширение знакового разряда приводит к тому, что 0xf1 превращается в 0xff. Затем в переменную d заносится результат беззнакового сдвига b вправо на 4 разряда. Можно было бы ожидать, что в результате d содержит 0x0f, однако на деле мы снова получаем 0xff. Это - результат расширения знакового разряда, выполненного при автоматическом повышении типа переменной b до int перед операцией сдвига вправо. Наконец, в выражении для переменной е нам удается добиться желаемого результата - значения 0x0f. Для этого нам пришлось перед сдвигом вправо логически умножить значение переменной b на маску 0xff, очистив таким образом старшие разряды, заполненные при автоматическом повышении типа. Обратите внимание, что при этом уже нет необходимости использовать беззнаковый сдвиг вправо, поскольку мы знаем состояние знакового бита после операции AND.
С: \> java ByteUShift
b = 0xf1
b >> 4 = 0xff
b >>> 4 = 0xff
b & 0xff) >> 4 = 0x0f
Битовые операторы присваивания
Так же, как и в случае арифметических операторов, у всех бинарных битовых операторов есть родственная форма, позволяющая автоматически присваивать результат операции левому операнду. В следующем примере создаются несколько целых переменных, с которыми с помощью операторов, указанных выше, выполняются различные операции.
class OpBitEquals {
public static void main(String args) {
int a = 1;
int b = 2;
int с = 3;
a |= 4;
b >>= 1;
с <<= 1;
а ^= с;
System.out.println("a = " + a);
System.out.println("b = " + b);
System.out.println("c = " + c);
} }
Результаты исполнения программы таковы:
С:\> Java OpBitEquals
а = 3
b = 1
с = 6
Операторы отношения
Для того, чтобы можно было сравнивать два значения, в Java имеется набор операторов, описывающих отношение и равенство. Список таких операторов приведен в таблице.
Оператор |
Результат |
больше или равно |
|
меньше или равно |
Значения любых типов, включая целые и вещественные числа, символы, логические значения и ссылки, можно сравнивать, используя оператор проверки на равенство == и неравенство!=. Обратите внимание - в языке Java, так же, как в С и C++ проверка на равенство обозначается последовательностью (==). Один знак (=) - это оператор присваивания.
Булевы логические операторы
Булевы логические операторы, сводка которых приведена в таблице ниже, оперируют только с операндами типа boolean. Все бинарные логические операторы воспринимают в качестве операндов два значения типа boolean и возвращают результат того же типа.
Оператор |
Результат |
Оператор |
Результат |
логическое И (AND) |
И (AND) с присваиванием |
||
логическое ИЛИ (OR) |
ИЛИ (OR) с присваиванием |
||
логическое исключающее ИЛИ (XOR) |
исключающее ИЛИ (XOR) с присваиванием |
||
оператор OR быстрой оценки выражений (short circuit OR) |
|||
оператор AND быстрой оценки выражений (short circuit AND) |
|||
логическое унарное отрицание (NOT) |
тернарный оператор if-then-else |
Результаты воздействия логических операторов на различные комбинации значений операндов показаны в таблице.
Программа, приведенная ниже, практически полностью повторяет ужезнакомый вам пример BitLogic. Только но на этот раз мы работаем с булевыми логическими значениями.
class BoolLogic {
public static void main(String args) {
boolean a = true;
boolean b = false;
boolean с = a | b;
boolean d = a & b;
boolean e = a ^ b;
boolean f = (!a & b) | (a & !b);
boolean g = !a;
System.out.println(" a = " + a);
System.out.println(" b = " + b);
System.out.println(" a|b = " + c);
System.out.println(" a&b = " + d);
System.out.println(" a^b = " + e);
System.out.println("!a&b|a&!b = " + f);
System.out.println(" !a = " + g);
} }
С: \> Java BoolLogic
а = true
b = false
a|b = true
a&b = false
a^b = true
!a&b|a&!b = true
!a = false
Операторы быстрой оценки логических выражений (short circuit logical operators)
Существуют два интересных дополнения к набору логических операторов. Это - альтернативные версии операторов AND и OR, служащие для быстрой оценки логических выражений. Вы знаете, что если первый операнд оператора OR имеет значение true, то независимо от значения второго операнда результатом операции будет величина true. Аналогично в случае оператора AND, если первый операнд - false, то значение второго операнда на результат не влияет - он всегда будет равен false. Если вы в используете операторы && и || вместо обычных форм & и |, то Java не производит оценку правого операнда логического выражения, если ответ ясен из значения левого операнда. Общепринятой практикой является использование операторов && и || практически во всех случаях оценки булевых логических выражений. Версии этих операторов & и | применяются только в битовой арифметике.
Тернарный оператор if-then-else
Общая форма оператора if-then-use такова:
выражение1? выражение2: выражениеЗ
В качестве первого операнда - «выражение1» - может быть использовано любое выражение, результатом которого является значение типа boolean. Если результат равен true, то выполняется оператор, заданный вторым операндом, то есть, «выражение2». Если же первый операнд paвен false, то выполняется третий операнд - «выражениеЗ». Второй и третий операнды, то есть «выражение2» и «выражениеЗ», должны возвращать значения одного типа и не должны иметь тип void.
В приведенной ниже программе этот оператор используется для проверки делителя перед выполнением операции деления. В случае нулевого делителя возвращается значение 0.
class Ternary {
public static void main(String args) {
int a = 42;
int b = 2;
int c = 99;
int d = 0;
int e = (b == 0) ? 0: (a / b);
int f = (d == 0) ? 0: (c / d);
System.out.println("a = " + a);
System.out.println("b = " + b);
System.out.println("c = " + c);
System.out.println("d = " + d);
System.out.println("a / b = " + e);
System.out.println("c / d = " + f);
} }
При выполнении этой программы исключительной ситуации деления на нуль не возникает и выводятся следующие результаты:
С: \>java Ternary
а = 42
b = 2
с = 99
d = 0
a / b = 21
с / d= 0
Приоритеты операторов
В Java действует определенный порядок, или приоритет, операций. В элементарной алгебре нас учили тому, что у умножения и деления более высокий приоритет, чем у сложения и вычитания. В программировании также приходится следить и за приоритетами операций. В таблице указаны в порядке убывания приоритеты всех операций языка Java.
В первой строке таблицы приведены три необычных оператора, о которых мы пока не говорили. Круглые скобки () используются для явной установки приоритета. Как вы узнали из предыдущей главы, квадратные скобки используются для индексирования переменной-массива. Оператор. (точка) используется для выделения элементов из ссылки на объект - об этом мы поговорим в главе 7 . Все же остальные операторы уже обсуждались в этой главе.
Явные приоритеты
Поскольку высший приоритет имеют круглые скобки, вы всегда можете добавить в выражение несколько пар скобок, если у вас есть сомнения по поводу порядка вычислений или вам просто хочется сделать свои код более читабельным.
а >> b + 3
Какому из двух выражений, а >> (b + 3) или (а >> b) + 3, соответствует первая строка? Поскольку у оператора сложения более высокий приоритет, чем у оператора сдвига, правильный ответ - а>> (b + а). Так что если вам требуется выполнить операцию (а>>b)+ 3 без скобок не обойтись.
Итак, мы рассмотрели все виды операторов языка Java. Теперь вы можете сконструировать любое выражение с различными типами данных . В следующей главе познакомимся с конструкциями ветвления, организацией циклов и научимся управлять выполнением программы.
В Java есть операторы сдвига. Операторы << и >> позаимствованы из С/C++. Кроме того, Java обладает своим новым оператором сдвига >>>.
Операторы сдвига присущи системам, которые могут выравнивать биты, прочтённые из IO портов или зартсываемые в IO порты. Это также быстрое умножение или деление на степень двойки. Преимущество операторов сдвига в Java - это независимость от платформы. Поэтому вы можете использовать их не беспокоясь ни о чём.
Основы сдвига
Сдвиг - это, по сути, простейшая операция: мы берём последовательность битов и двигаем её влево или вправо. Больше всего конфуза вызывает оператор >>>. Но о нём мы поговорим чуть позже.
Операторы сдвига могут применяться лишь к целым числам, то есть к типам int или long . Следующая таблица иллюстрирует базовый механизм сдвига.
Таблица 1: Идея сдвига
Исходные данные | ||||||
Бинарное представление | 00000000 | 00000000 | 00000000 | 11000000 | ||
Сдвиг влево на 1 бит | 00000000 | 00000000 | 00000001 | 1000000? | ||
Сдвиг вправо на бит | ?0000000 | 00000000 | 00000000 | 01100000 | 0 | |
Сдвиг влево на 4 бита | 0000 | 00000000 | 00000000 | 00001100 | 0000???? | |
Исходные данные | ||||||
Бинарное представление | 11111111 | 11111111 | 11111111 | 01000000 | ||
Сдвиг влево на 1 бит | 11111111 | 11111111 | 11111110 | 1000000? | ||
Сдвиг вправо на бит | ?1111111 | 11111111 | 11111111 | 10100000 | 0 |
Таблица показывает фундаментальную идею сдвига: перемещение битов относительно их позиций. Это как очередь в магазине: как только один человек совершил покупку и отшёл, вся очередь сдвинулась и позиции всех участников очереди изменились.
Однако, глядя на таблицу, возникают три вопроса вопроса:
- Что происходит, если мы сдвигаем влево и при этом часть бинарной записи выходит за границу слева, а часть - остаётся пустой справа?
- Что происходит, когда справа - выход за границы, а слева - пустое место?
- Какое истинное значение принимает знак "?"?.
Ответим на часть этих вопросов. Биты, вышедшие за границы, просто теряются. Мы о них забываем.
В некоторых языках, типа ассемблер, есть операция ротации , когда при сдвиге вышедшие за границы биты не теряются, но ставятся на освободившееся место (вместо вопросиков). Однако языки высокого уровня, типа Java, не имеют в своём арсенале такой операции.
Сдвиг отрицательных чисел
Ответ на вопрос о значении символов "?" в приведенной выше таблице требует отдельного рассмотрения.
В случае сдвига влево << и беззнакового сдвига вправо >>> новые биты просто устанавливаются в ноль. В случае сдвига вправо со знаком >> новые биты принимают значение старшего (самого левого) бита перед сдвигом. Следующая таблица демонстрирует это:
Таблица 2: Сдвиг положительных и отрицательных чисел
Исходные данные | ||||
Бинарное представление | 00000000 | 00000000 | 00000000 | 11000000 |
Сдвиг вправо на 1 бит | 00000000 | 00000000 | 00000000 | 01100000 |
Сдвиг вправо на 7 бит | 00000000 | 00000000 | 00000000 | 00000001 |
Исходные данные | ||||
Бинарное представление | 11111111 | 11111111 | 11111111 | 01000000 |
Сдвиг вправо на 1 бит | 11111111 | 11111111 | 11111111 | 10100000 |
Сдвиг вправо на 7 бит | 11111111 | 11111111 | 11111111 | 11111110 |
Заметьте: в том, случае, где старший бит был 0 перед сдвигом, новые биты стали тоже 0. Там где старший бит перед сдвигом был 1, новые биты тоже заполнились 1.
Это правило может показаться странным на первый взгляд. Но оно имеет под собой очень серьёзное обоснование. Если мы сдвигаем бинарное число влево на одну позицию, то в десятичной записи мы умножаем его на два. Если мы сдвигаем влево на n позиций, то умножение происходит на 2 n , то есть на 2, 4, 8, 16 и т.д.
Сдвиг вправо даёт деление на степени двойки. При этом, добавление слева нулей на появившиеся биты на самом деле даёт деление на степени двойки лишь в случае положительных чисел. Но для отрицательных чисел всё совсем по другому!
Как известно, старший бит отрицательных чисел равен единице, 1. Для того, чтобы сохранить старшинство единицы при сдвиге, то есть сохранить отрицательный знак результата деления отрицательного числа на положительное (степень двойки), нам нужно подставлять единицы на освободившиеся места.
Если мы посмотрим на Таблицу 2, то заметим, что 192, сдвинутое на 1 бит вправо - это 192/2=96, а сдвинутое на 7 битов вправо - это 192/2 7 =192/128=1 по законам целочисленной арифметики. С другой стороны, -192 сдвинутое на 1 бит вправо - это 192/2=-96 и т.д.
Есть, однако пример, когда реультат сдвига вправо отличается от результата целочисленного деления на 2. Это случай, когда аргумент = -1. При целочисленном делении мы имеем: -1/2=0. Но результат сдвига вправо нам даёт -1. Это можно трактовать так: целочисленное деление округляет к нулю, а сдвиг округляет к -1.
Таким образом, сдвиг вправо имеет две ипостаси: одна (>>>) просто сдвигает битовый паттерн "в лоб", а другая (>>) сохраняет эквивалентность с операцией деления на 2.
Зачем же Java потребовался беззнаковый сдвиг вправо (сдвиг "в лоб"), когда ни в С, ни в С++ его не существует? Ответ прост, потому что в С и С++ сдвиг всегда беззнаковый . То есть >>>> в Java - это и есть сдвиг вправо в C и C++. Но, поскольку в Java все численные типы со знаком (за исключением char ), то и результаты сдвигов должны иметь знаки.
Сокращение (reduction) правого операнда
На самом деле у операторов сдвига есть правый операнд - число позиций, на которое нужно произвести сдвиг. Для корректного сдвига это число должно быть меньше, чем количество битов в результате сдвига. Если число типа int (long) , то сдвиг не может быть сделан более, чем на 32 (64) бита.
Оператор же сдвига не делает никаких проверок данного условия и допускает операнды, его нарушающие. При этом правый операнд сокращается по модулю от нужного количества битов. Например, если вы захотите сдвинуть целое число на 33 бита, то сдвиг произойдёт на 33%32=1 бит. В результатае такого сдвига мы легко можем получить аномальные результаты, то есть результаты, которых мы не ожидали. Например, при сдвиге на 33 бита мы ожидаем получить 0 или -1 (в знаковой арифметике). Но это не так.
Почему Java сокращает правый операнд оператора сдвига или грустная история о заснувшем процессоре
Одной из главной причин введения сокращения было то, что процессоры сами сокращают подобным образом правый операнд оператора сдвига. Почему?
Несколько лет назад был создан мощнейший процессор с длинными регистрами и операциями ротации и сдвигам на любое количество битов. Именно потому, что регистры были длинными, корректное выполнение этих операций требовало несколько минут.
Основным применением данных процессоров был контроль систем реального времени. В данных системах самый быстрый ответ на внешнее событие должно занимать не более задержки на прерывание (interrupt latency ). Отдельные инскрукции таких процессоров были неделимы. Поэтому выполнение длинных операций (сдвига на несколько бит и ротации) нарушало эффективную работу процессора.
Следующая версия процессора имплементировала эти операции уже по-другому: размер правого операнда сократился. Задержка на прерывание восстанавилась. И многие процессоры переняли данную практику.
Арифметическое распространение (promotion ) операндов
Апифметическое распространение операндов происходит перед применением оперции сдвига и гарантирует, что операнды по крайней мере типа int . Это явление имеет особый эффект на беззнаковый сдвиг вправо, когда сдвигаемое число меньше, чем int : мы получаем не тот результат, который ожидали.
Следующая таблица показывает пример аномалии:
Таблица 3: Арифметическое распространение для беззнакового сдвига вправо, когда операнд меньше, чем int
Исходные данные (-64 в десятичной записи) | ||||
Распространение до int | 11111111 | 11111111 | 11111111 | 11000000 |
Сдвиг вправо на 4 битa | 00001111 | 11111111 | 11111111 | 11111100 |
Сокращение до байта | 11111100 | |||
Ожидаемый результат был | 00001100 |
Тебе наверняка знакомо слово “бит”. Если же нет, давай познакомимся с ним:) Бит - минимальная единица измерения информации в компьютере. Его название происходит от английского “binary digit ” - “двоичное число”. Бит может быть выражен одним из двух чисел: 1 или 0. Существует специальная система счисления, основанная на единицах и нулях - двоичная .
Не будем углубляться в дебри математики и отметим лишь, что любое число в Java можно сконвертировать в его двоичную форму. Для этого нужно использовать классы-обертки. Например, вот как можно сделать это для числа int: public class Main { public static void main (String args) { int x = 342 ; System. out. println (Integer. toBinaryString (x) ) ; } } Вывод в консоль: 101010110 1010 10110 (я добавил пробел для удобства чтения) - это число 342 в двоичной системе. Мы фактически разделили это число на отдельные биты - нули и единицы. Именно с ними мы можем выполнять операции, которые называются побитовыми.
~ - побитовый оператор “НЕ”.
& - побитовый оператор “И”
- | - побитовое “ИЛИ”. Принцип работы тот же - сравниваем два числа по битам. Только теперь если хотя бы один из битов равен 1, результат будет равен 1. Посмотрим на тех же числах - 277 и 432:
- ^ - побитовое исключающее “ИЛИ” (также известно как XOR)
Сдвиг влево
Сдвиг битов влево обозначается знаком << Пример: public class Main { public static void main (String args) { int x = 64 ; //значение int y = 3 ; //количество int z = (x << y) ; System. out. println (Integer. toBinaryString (x) ) ; System. out. println (Integer. toBinaryString (z) ) ; } } В этом примере число x=64 называется значением . Именно его биты мы будем сдвигать. Сдвигать биты мы будем влево (это можно определить по направлению знака <<) В двоичной системе число 64 = 1000000 Число y=3 называется количеством . Количество отвечает на вопрос “на сколько бит вправо/влево нужно сдвинуть биты числа x ” В нашем примере мы будем сдвигать их на 3 бита влево. Чтобы процесс сдвига был более понятен, посмотрим на картинке. У нас в примере используются числа типа int. Int ’ы занимают в памяти компьютера 32 бита. Вот так выглядит наше изначальное число 64:А теперь мы, в прямом смысле слова, берем каждый из наших битов и сдвигаем влево на 3 ячейки:
Вот что у нас получилось. Как видишь, все наши биты сдвинулись, а из-за пределов диапазона добавились еще 3 нуля. 3 - потому что мы делали сдвиг на 3. Если бы мы сдвигали на 10, добавилось бы 10 нулей. Таким образом, выражение x << y означает “сдвинуть биты числа х на y ячеек влево”. Результатом нашего выражения стало число 1000000000, которое в десятичной системе равно 512. Проверим: public class Main { public static void main (String args) { int x = 64 ; //значение int y = 3 ; //количество int z = (x << y) ; System. out. println (z) ; } } Вывод в консоль: 512 Все верно! Теоретически, биты можно сдвигать до бесконечности. Но поскольку у нас число int , в распоряжении есть всего 32 ячейки. Из них 7 уже заняты числом 64 (1000000). Поэтому если мы сделаем, например, 27 сдвигов влево, наша единственная единица выйдет за пределы диапазона и “затрётся”. Останутся только нули! public class Main { public static void main (String args) { int x = 64 ; //значение int y = 26 ; //количество int z = (x << y) ; System. out. println (z) ; } } Вывод в консоль: 0 Как мы и предполагали, единичка вышла за пределы 32 ячеек-битов и исчезла. У нас получилось 32-битное число, состоящее из одних нулей.
Естественно, в десятичной системе ему соответствует 0. Простое правило для запоминания сдвигов влево: При каждом сдвиге влево выполняется умножение числа на 2. Например, попробуем без картинок с битами посчитать результат выражения 111111111 << 3 Нам нужно трижды умножить число 111111111 на 2. В результате у нас получается 888888888. Давай напишем код и проверим: public class Main { public static void main (String args) { System. out. println (111111111 << 3 ) ; } } Вывод в консоль: 888888888
Сдвиги вправо
Они обозначаются знаком >> . Делают то же самое, только в другую сторону! :) Не будем изобретать велосипед и попробуем сделать это с тем же числом int 64. public class Main { public static void main (String args) { int x = 64 ; //значение int y = 2 ; //количество int z = (x >> y) ; System. out. println (z) ; } }В результате сдвига на 2 вправо два крайних нуля нашего числа вышли за пределы диапазона и затерлись. У нас получилось число 10000, которому в десятичной системе соответствует число 16 Вывод в консоль: 16 Простое правило для запоминания сдвигов вправо: При каждом сдвиге вправо выполняется деление на два с отбрасыванием любого остатка. Например, 35 >> 2 означает, что нам нужно 2 раза разделить 35 на 2, отбрасывая остатки 35/2 = 17 (отбросили остаток 1) 17:2 = 8 (отбросили остаток 1) Итого, 35 >> 2 должно быть равно 8. Проверяем: public class Main { public static void main (String args) { System. out. println (35 >> 2 ) ; } } Вывод в консоль: 8
Приоритет операций в Java
В процессе написания или чтения кода тебе часто будут попадаться выражения, в которых одновременно выполняются несколько операций. Очень важно понимать, в каком порядке они будут выполнены, иначе результат может быть неожиданным. Поскольку операций в Java много, все они были выделены в специальную таблицу:Operator Precedence
Operators | Precedence |
---|---|
postfix | expr++ expr-- |
unary | ++expr --expr +expr ~ ! |
Multiplicative | * / % |
additive | + - |
shift | << >> >>> |
relational | < > <= >= instanceof |
equality | == != |
bitwise AND | & |
bitwise exclusive OR | ^ |
bitwise inclusive OR | | |
logical AND | && |
logical OR | || |
ternary | ? : |
assignment | = += -= *= /= %= &= ^= |= <<= >>= >>>= |
- boolean x = 6 - 2 > 3 && 12 * 12 <= 119 ;
- boolean x = 4 > 3 && 144 <= 119 ;
-
4 > 3 = true
boolean x = true && 144 <= 119 ; 144 <= 119 = false
boolean x = true && false ;И, наконец, последним, будет выполнен оператор “И” && .
boolean x = true && false;
boolean x = false;Оператор сложения (+), например, имеет более высокий приоритет, чем оператор сравнения!= (“не равно”);
Поэтому в выражении:
Boolean x = 7 != 6+1;
сначала будет выполнена операция 6+1, потом проверка 7!=7 (false), а в конце - присваивания результата false переменной x . У присваивания вообще самый маленький приоритет из всех операций - посмотри в таблице.
12*12 = 144
- Отличная в картинках про побитовые операции
- - лекция JavaRush о логических и числовых операциях. Мы до них еще нескоро дойдем, но почитать можно уже сейчас, вреда не будет
Последнее обновление: 30.10.2018
Побитовые или поразрядные операции выполняются над отдельными разрядами или битами чисел. В данных операциях в качестве операндов могу выступать только целые числа.
Каждое число имеет определенное двоичное представление. Например, число 4 в двоичной системе 100, а число 5 - 101 и так далее.
К примеру, возьмем следующие переменны:
Byte b = 7; // 0000 0111 short s = 7; // 0000 0000 0000 0111
Тип byte занимает 1 байт или 8 битов, соответственно представлен 8 разрядами. Поэтому значение переменной b в двоичном коде будет равно 00000111 . Тип short занимает в памяти 2 байта или 16 битов, поэтому число данного типа будет представлено 16 разрядами. И в данном случае переменная s в двоичной системе будет иметь значение 0000 0000 0000 0111 .
Для записи чисел со знаком в Java применяется дополнительный код (two’s complement), при котором старший разряд является знаковым. Если его значение равно 0, то число положительное, и его двоичное представление не отличается от представления беззнакового числа. Например, 0000 0001 в десятичной системе 1.
Если старший разряд равен 1, то мы имеем дело с отрицательным числом. Например, 1111 1111 в десятичной системе представляет -1. Соответственно, 1111 0011 представляет -13.
Логические операции
Логические операции над числами представляют поразрядные операции. В данном случае числа рассматриваются в двоичном представлении, например, 2 в двоичной системе равно 10 и имеет два разряда, число 7 - 111 и имеет три разряда.
& (логическое умножение)
Умножение производится поразрядно, и если у обоих операндов значения разрядов равно 1, то операция возвращает 1, иначе возвращается число 0. Например:
Int a1 = 2; //010 int b1 = 5;//101 System.out.println(a1&b1); // результат 0 int a2 = 4; //100 int b2 = 5; //101 System.out.println(a2 & b2); // результат 4
В первом случае у нас два числа 2 и 5. 2 в двоичном виде представляет число 010, а 5 - 101. Поразрядное умножение чисел (0*1, 1*0, 0*1) дает результат 000.
Во втором случае у нас вместо двойки число 4, у которого в первом разряде 1, так же как и у числа 5, поэтому здесь результатом операции (1*1, 0*0, 0 *1) = 100 будет число 4 в десятичном формате.
| (логическое сложение)
Данная операция также производится по двоичным разрядам, но теперь возвращается единица, если хотя бы у одного числа в данном разряде имеется единица (операция "логическое ИЛИ"). Например:
Int a1 = 2; //010 int b1 = 5;//101 System.out.println(a1|b1); // результат 7 - 111 int a2 = 4; //100 int b2 = 5;//101 System.out.println(a2 | b2); // результат 5 - 101
^ (логическое исключающее ИЛИ)
Также эту операцию называют XOR, нередко ее применяют для простого шифрования:
Int number = 45; // 1001 Значение, которое надо зашифровать - в двоичной форме 101101 int key = 102; //Ключ шифрования - в двоичной системе 1100110 int encrypt = number ^ key; //Результатом будет число 1001011 или 75 System.out.println("Зашифрованное число: " +encrypt); int decrypt = encrypt ^ key; // Результатом будет исходное число 45 System.out.println("Расшифрованное число: " + decrypt);
Здесь также производятся поразрядные операции. Если у нас значения текущего разряда у обоих чисел разные, то возвращается 1, иначе возвращается 0. Например, результатом выражения 9^5 будет число 12. А чтобы расшифровать число, мы применяем обратную операцию к результату.
~ (логическое отрицание)
Поразрядная операция, которая инвертирует все разряды числа: если значение разряда равно 1, то оно становится равным нулю, и наоборот.
Byte a = 12; // 0000 1100 System.out.println(~a); // 1111 0011 или -13
Операции сдвига
Операции сдвига также производятся над разрядами чисел. Сдвиг может происходить вправо и влево.
a<
a>>b - смещает число a вправо на b разрядов. Например, 16>>1 сдвигает число 16 (которое в двоичной системе 10000) на один разряд вправо, то есть в итоге получается 1000 или число 8 в десятичном представлении.
a>>>b - в отличие от предыдущих типов сдвигов данная операция представляет беззнаковый сдвиг - сдвигает число a вправо на b разрядов. Например, выражение -8>>>2 будет равно 1073741822.
Таким образом, если исходное число, которое надо сдвинуть в ту или другую строну, делится на два, то фактически получается умножение или деление на два. Поэтому подобную операцию можно использовать вместо непосредственного умножения или деления на два, так как операция сдвига на аппаратном уровне менее дорогостоящая операция в отличие от операции деления или умножения.