Вредоносное ПО (malware) - это назойливые или опасные программы,...
Сдвиг вправо без учета знака
Как было показано, при каждом выполнении операция » автоматически заполняет старший бит его предыдущим содержимым. В результате знак значения сохраняется. Однако иногда это нежелательно. Например, при выполнении сдвига вправо в каком-либо значении, которое не является числовым, использование дополнительных знаковых разрядов может быть нежелательным. Эта ситуация часто встречается при работе со значениями пикселей и графическими изображениями. Как правило, в этих случаях требуется сдвиг нуля в позицию старшего бита независимо от его первоначального значения. Такое действие называют сдвигом вправо без учета знака. Для его выполнения используют операцию сдвига вправо без учета знака Java, >>>, которая всегда вставляет ноль в позицию старшего бита.
Следующий фрагмент кода демонстрирует применение операции >>>. В этом примере значение переменной а установлено равным -1, все 32 бита двоичного представления которого равны 1. Затем в этом значении выполняется сдвиг вправо на 24 бита с заполнением старших 24 битов нулями и игнорированием обычно используемых дополнительных знаковых разрядов. В результате значение а становится равным 255.
int а = -1;
а = а >>> 24;
Часто операция >>> не столь полезна, как хотелось бы, поскольку она имеет смысл только для 32- и 64-разрядных значений. Помните, что в выражениях тип меньших значений автоматически повышается до int. Это означает применение дополнительных знаковых разрядов и выполнение сдвига по отношению к 32-разрядным, а не 8- или 16-разрядным значениям. То есть программист может подразумевать выполнение сдвига вправо без учета знака применительно к значению типа byte и заполнение нулями, начиная с бита 7.
Однако в действительности это не так, поскольку фактически сдвиг будет выполняться в 32-разрядном значении. Этот эффект демонстрирует следующая программа.
// Сдвиг без учета знака значения типа byte.
class ByteUShift {
static public void main(String args) {
char hex = {
"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f"
};
byte b = (byte) 0xfl;
byte с = (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) S 0x0f] + hex) ;
}
}
Из следующего вывода этой программы видно, что операция »> не выполняет никаких действий по отношению к значениям типа byte. Для этого примера в качестве значения переменной b было выбрано произвольное отрицательное значение типа byte. Затем переменной с присваивается значение переменной b типа byte, сдвинутое вправо на четыре позиции:, которое в связи с применением дополнительных знаковых разрядов равно Oxff. Затем переменной d присваивается значение переменной b типа byte, сдвинутое вправо на четыре позиции без учета знака, которым должно было бы быть значение OxOf, но в действительности, из-за применения дополнительных знаковых разрядов во время повышения типа b до int перед выполнением сдвига, равное Oxff. Последнее выражение устанавливает значение переменной е равным значению типа byte переменной Ь, замаскированному до 8 бит с помощью операции AND и затем сдвинутому вправо на четыре позиции, что дает ожидаемое значение, равное OxOf. Обратите внимание, что операция сдвига вправо без учета знака не применялась к переменной d, поскольку состояние знакового бита после выполнения операции AND было известно.
Побитовые составные операции с присваиванием
Подобно алгебраическим операциям, все двоичные побитовые операции имеют составную форму, которая объединяет побитовую операцию с операцией присваивания. Например, следующие два оператора, выполняющие сдвиг вправо на четыре позиции в значении переменной а, эквивалентны:
Аналогично, эквивалентны и следующие два оператора, которые присваивают переменной а результат выполнения побитовой операции a OR b:
а = а | b;
а |= b;
Следующая программа создает несколько целочисленных переменных, а затем использует составные побитовые операции с присваиванием для манипулирования этими переменными:
class OpBitEquals
public static void main(String args){
int a = 1;
int b = 2;
int c = 3;
a |= 4;
b >= 1;
c
a ^= c;
System.out.println("a = " + a);
System.out.println("b = " + b);
System.out.println("c = " + c);
}
}
Эта программа создает следующий вывод.
Большинство операций над примитивными типами выполняется не с помощью методов, а с помощью специальных символов, называемых знаком операции .
Операция присваивания
Присвоение переменной значения константы, другой переменной или выражения (переменных и/или констант, разделенных знаками операций), называется операцией присваивания и обозначается знаком "= ", например: x = 3 ; y = x; z = x; В Java допустимо многократное использование операции присваивания в одном выражении, например: x1 = x2 = x3 = 0 ; Эта операция выполняется справа налево, т.е. сначала переменной x3 присваивается значение 0 , затем переменной x2 присваивается значение переменной x3 (0), и, наконец, переменной x1 присваивается значение переменной x2 (0). Знаки операций, аргументами которых являются числа, разделяются на две категории: унарные (unary) знаки операций с одним аргументом и бинарные (binary) с двумя аргументами.Унарные операции
В Java определены следующие унарные операции:- унарный минус " - " – меняет знак числа или выражения на противоположный;
- унарный плюс " + " – не выполняет никаких действий над числом или выражением;
- побитовое дополнение " ~ " (только для целых) – инвертирует все биты поля числа (меняет 0 на 1 и 1 на 0);
- инкремент " ++ " (только для целых) – увеличивает значение переменной на 1;
- декремент " -- " (только для целых) – уменьшает значение переменной на 1.
Арифметические бинарные операции
В Java определены следующие арифметические бинарные операции :- сложение " + ";
- вычитание " - ";
- умножение " * ";
- деление " / ";
- вычисление остатка от деления целых чисел " % " (возвращает остаток от деления первого числа на второе, причем результат будет иметь тот же знак, что и делимое), например, результат операции 5%3 будет равен 2 , а результат операции (-7)%(-4) будет равен -3 . В Java операция может использоваться и для вещественных переменных (типа float или double).
Побитовые операции
- Побитовые операции рассматривают исходные числовые значения как поля битов и выполняют над ними следующие действия:
- установка бита в i -ой позиции поля результата в 1 , если оба бита в i -ых позициях операндов равны 1 , или в 0 в противном случае – побитовое И (" & ");
- установка бита в i -ой позиции поля результата в 1 , если хотя бы один бит в i -ых позициях операндов равен 1 , или в 0 в противном случае – побитовое ИЛИ (" | ");
- установка бита в i -ой позиции поля результата в 1 , если биты в i -ых позициях операндов не равны друг другу, или в 0 в противном случае – побитовое исключающее ИЛИ (" ^ ");
- сдвиг влево битов поля первого операнда на количество битов, определяемое вторым операндом (бит знака числа при этом не меняется) – побитовый сдвиг влево с учетом знака " << ";
- сдвиг вправо битов поля первого операнда на количество битов, определяемое вторым операндом (бит знака числа при этом не меняется) – побитовый сдвиг вправо с учетом знака " >> ";
- сдвиг вправо битов поля первого операнда на количество битов, определяемое вторым операндом (бит знака числа при этом также сдвигается) – побитовый сдвиг вправо без учета знака " >>> ".
Побитовое И
int x = 112 ; int y = 94 ; int z; z = x & y; // z=80: 00000000 00000000 00000000 01010000Побитовое ИЛИ
int x = 112 ; // x: 00000000 00000000 00000000 01110000 int y = 94 ; // y: 00000000 00000000 00000000 01011110 int z; z = x | y; // z = 126: 00000000 00000000 00000000 01111110Побитовое исключающее ИЛИ
int x = 112 ; // x: 00000000 00000000 00000000 01110000 int y = 94 ; // y: 00000000 00000000 00000000 01011110 int z; z = x ^ y; // z = 46: 00000000 00000000 00000000 00101110Сдвиг влево с учетом знака
int x = 31 , z; // x: 00000000 00000000 00000000 00011111 z = x << 2 ; // z = 124: 00000000 00000000 00000000 01111100Сдвиг вправо с учетом знака
int x = - 17 , z; z = x >> 2 ; // z = -5: 11111111 11111111 11111111 11111011Сдвиг вправо без учета знака
int x = - 17 , z; // x: 11111111 11111111 11111111 11101111 z = x >>> 2 ; // z = 1073741819 // z: 00111111 11111111 11111111 11111011
Комбинированные операции
В Java для бинарных арифметических операций можно использовать комбинированные (составные) знаки операций: идентификатор операция = выражение Это эквивалентно следующей операции: идентификатор = идентификатор операция выражение Примеры:- Выражение x += b означает x = x + b .
- Выражение x -= b означает x = x - b .
- Выражение x *= b означает x = x * b .
- Выражение x /= b означает x = x / b .
- Выражение x %= b означает x = x % b .
- Выражение x &= b означает x = x & b .
- Выражение x |= b означает x = x | b .
- Выражение x ^= b означает x = x ^ b .
- Выражение x <<= b означает x = x << b .
- Выражение x >>= b означает x = x >> b .
- Выражение x >>>= b означает x = x >>> b .
Операции сравнения
В Java определены следующие операции сравнения:- " == " (равно), " != " (не равно),
- " > " (больше), " >= " (больше или равно),
- " < " (меньше) " <= " (меньше или равно)
Булевские операции
Булевские операции выполняются над булевскими переменными и их результатом также является значение типа boolean . В Java определены следующие булевские операции:- отрицание "!" – замена false на true , или наоборот;
- операция И "&" – результат равен true , только, если оба операнда равны true , иначе результат – false ;
- операция ИЛИ " | " – результат равен true , только, если хотя бы один из операндов равен true , иначе результат – false .
- операция исключающее ИЛИ " ^ " – результат равен true , только, если операнды не равны друг другу, иначе результат – false .
Условная операция
Условная операция записывается в форме выражение-1?выражение-2:выражение-3 . При этом сначала вычисляется выражение выражение-1 , которое должно дать булевское значение, а затем, если выражение-1 имеет значение true , вычисляется и возвращается выражение-2 как результат выполнения операции, либо (если выражение-1 имеет значение false), вычисляется и, как результат выполнения операции, возвращается выражение-3 . Пример условной операции: x= n> 1 ? 0 : 1 ; Переменной x будет присвоено значение 0 , если n>1 (выражение n>1 имеет значение true) или 1 , если n≤1 (выражение n>1 имеет значение false).Старшинство операций
Операции в выражениях выполняются слева направо, однако, в соответствии со своим приоритетом. Так операции умножения в выражении y = x + z* 5 ; будет выполнена раньше, чем операция сложения, поскольку приоритет операции умножения выше, чем приоритет операции сложения. Приоритеты операций (в порядке уменьшения приоритета) в Java приведены в табл. 1.Круглые скобки повышают старшинство операций, которые находятся внутри них. Так, если в приведенное выше выражение вставить скобки: y = (x + z) * 5 ; то сначала будет выполнена операция сложения, а затем операция умножения. Иногда скобки используют просто для того, чтобы сделать выражение более читаемым, например: (x > 1 ) && (x <= 5 ) ;
Преобразование и приведение типов при выполнении операций
В операции присваивания и арифметических выражениях могут использоваться литералы, переменные и выражения разных типов, например: double y; byte x; y = x + 5 ; В этом примере выполняется операция сложения переменной x типа byte и литерала 5 (типа int) и результат присваивается переменной y типа double . В Java, как и в языке C, преобразования типов при вычислении выражений могут выполняться автоматически, либо с помощью оператора приведения типа. Однако правила приведения типов несколько отличаются от правил языка C, и в целом являются более строгими, чем в языке C. При выполнении операции присваивания преобразование типов происходит автоматически, если происходит расширяющее преобразование (widening conversion) и два типа совместимы . Расширяющими преобразованиями являются преобразования byte ®short ®int ®long ®float ®double . Для расширяющих преобразований числовые типы, включая целый и с плавающей точкой, являются совместимыми друг с другом. Однако числовые типы не совместимы с типами char и boolean . Типы char и boolean не совместимы также и друг с другом. В языке Java выполняется автоматическое преобразование типов также и при сохранении литеральной целочисленной константы (которая имеет по умолчанию тип int) в переменных типа byte , short или long (однако если литерал имеет значение вне диапазона допустимых значений для данного типа, выдается сообщение об ошибке: возможная потеря точности). Если преобразование является сужающим (narrowing conversion), т. е. выполняется преобразование byte ¬ short ¬ char ¬ int ¬ long ¬ float ¬ double , то такое преобразование может привести к потере точности числа или к его искажению. Поэтому при сужающих преобразованиях при компиляции программы выводится диагностическое сообщение о несовместимости типов и файлы классов не создаются. Такое сообщение будет выдано и при попытке преобразование выражений типа byte или short в переменную типа char . Если все же необходимо выполнить такие преобразования, используется операция приведения (cast) типа, которая имеет следующий формат: (тип-преобразования ) значение , где тип-преобразования определяет тип, в который необходимо преобразовать заданное значение , например, в результате выполнения операторов: byte x = 71 ; char symbol = (char ) x; переменная symbol получит значение " G ". Если значение с плавающей точкой присваивается целому типу, то (если значение с плавающей точкой имеет дробную часть) при явном преобразовании типа происходит также усечение (truncation) числа. Так, в результате выполнения оператора int x = (int ) 77.85 ; переменная x получит значение 77 . Если же присваиваемое значение лежит вне диапазона типа-преобразования , то результатом преобразования будет остаток от деления значения на модуль диапазона присваиваемого типа (для чисел типа byte модуль диапазона будет равен 256 , для short – 65536 , для int – 4294967296 и для long – 18446744073709551616). Например, в результате выполнения оператора byte x = (byte ) 514 ; переменная x получит значение 2 . При преобразовании целых или вещественных чисел в данные типа char , преобразование в символ происходит, если исходное число лежит в диапазоне от 0 до 127, иначе символ получает значение " ? ". При выполнении арифметических и побитовых преобразований все значения byte и short , а также char расширяются до int , (при этом в вычислениях для char используется числовое значение кода символа) затем, если хотя бы один операнд имеет тип long , тип целого выражения расширяется до long . Если один из операндов имеет тип float , то тип полного выражения расширяется до float , а если один из операндов имеет тип double , то тип результата будет double . Так, если объявлены переменные byte a, c; short b; то в выражении a + b* c – 15 L + 1.5F + 1.08 - 10 ; сначала, перед вычислением a + b*c значения переменных будут расширены до int , затем, поскольку константа 15 имеет тип long , перед вычитанием результат вычисления будет увеличен до long . После этого, поскольку литерал 1.5 имеет тип float перед сложением с этим литералом результат вычисления a + b*c – 15L будет расширен до float . Перед выполнением сложения с числом 1.08 результат предыдущих вычислений будет расширен до double (поскольку вещественные константы по умолчанию имеют тип double) и, наконец, перед выполнением последнего сложения литерал 10 (по умолчанию int) будет расширен до double . Таким образом, результат вычисления выражения будет иметь тип double . Автоматические расширения типов (особенно расширения short и byte до int) могут вызывать плохо распознаваемые ошибки во время компиляции. Например, в операторах: byte x = 30 , y = 5 ; x = x + y; перед выполнением сложения значение переменных x и y будет расширено до int , а затем при выполнении попытки присвоения результата вычисления типа int переменной типа byte будет выдано сообщение об ошибке. Чтобы этого избежать надо использовать во втором операторе явное преобразование типов: x = (byte ) (x + y) ; Выражение x + y необходимо заключит в скобки потому, что приоритет операции приведения типа, заключенной в скобки, выше, чем приоритет операции сложения. Кстати, если записать второй оператор в виде: x += y; то сообщения об ошибке не будет. Ссылка на первоКак известно, в 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 снова произойдёт неприятное нам расширение со знаком.
Тебе наверняка знакомо слово “бит”. Если же нет, давай познакомимся с ним:) Бит - минимальная единица измерения информации в компьютере. Его название происходит от английского “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 о логических и числовых операциях. Мы до них еще нескоро дойдем, но почитать можно уже сейчас, вреда не будет
В 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 |