- Привет, Амиго!
- Привет, Билаабо!
Хочу рассказать тебе немного про различные системы исчисления.
Ты уже слышал, что люди пользуются десятичной системой исчисления. Вот главные факты этого подхода:
1) Для записи числа используются 10 цифр: 0,1, 2, 3, 4, 5, 6, 7, 8, 9.
2) Число 543 значит 5 сотен + 4 десятка + 3 единицы.
Эта равносильно записи 5*100 + 4*10 + 3*1, что можно записать как 5*102+4*101+3*100
Обрати внимание – тысячи, сотни, десятки и единицы – это степени числа 10.
1) Единица – это 10 в нулевой степени.
2) Десять – это 10 в первой степени
3) Сто – это 10 во второй степени
4) Тысяча – это 10 в третьей степени и т.д.
- Ага. Понятно.
- А теперь представь, что цифр всего 8. Тогда у нас есть восьмеричная система исчисления и вот ее главные факты:
1) Для записи числа используются 8 цифр: 0,1, 2, 3, 4, 5, 6, 7.
2) Число 5438 значит 5*82+4*81+3*80. Т.е. это 5*64+4*8+3*1 = 320+32+3=35510
Я написал снизу числа знаки 8 и 10, чтобы мы знали, сколько цифр используется для его записи.
- Вроде как и ясно. Я думаю, я бы смог перевести число из восьмеричной системы в десятичную. Но наоборот – вряд ли.
- Все не так уж и сложно. Представь, что тебе нужно перевести кучу песка на нескольких грузовых машинах. У тебя есть карьерные самосвалы, обычные, и совсем маленькие машинки. Но надо, чтобы машины не ехали полупустыми.
Как бы ты возил?
- Сначала я бы насыпал в карьерные самосвалы, они самые большие. Затем, когда понял, что для заполнения машины песка не хватит, то перешел бы на машины поменьше. Затем еще меньше.
- Тут все тоже очень похоже. Давай попробуем перевести число 35510 обратно в восьмеричный формат.
Сначала мы разделим его на 64 (82), получим 5 целых и 35 в остатке. Значит первая цифра нашего числа – 5. Затем разделим остаток на 8(81), получим 4 и 3 в остатке. Так и получится число 5438.
Можно, кстати, пойти и с другой стороны. Ведь 5438 ==5*64+4*8+3 == ((5)*8+4)*8+3. Наши восьмеричные «десятки» и «сотни» обязательно делятся на 8. Значит, остаток от деления на 8 это и будут наши восьмеричные единицы.
Поделим сначала число 355 на 8. Получим 44 и 3 в остатке. Т.е. 355=44*8+3. А 44 можно представить как 5*8+4. Значит 355= (5*8+4)*8+3; Вот наши цифры: 5,4,3. Искомое число 5438
- В общем вроде понятно, но надо немного попрактиковаться, чтобы окончательно во всем разобраться.
- В программировании очень часто используются числа с различным основанием (количеством цифр). Самые популярные – это 2, 8, 10, 16, 64.
- А зачем это нужно. Зачем нужны числа, состоящие из 2, 8, 16 и 64 цифр?
- Дело во внутреннем устройстве процессора. Очень упрощенно - если в проводе есть ток, то говорят, что в нем «единица», если тока нет, то в нем «ноль». Все числа хранятся в памяти в виде ячеек. Устройство таких ячеек очень примитивно. Они тоже могу хранить только 0 или 1.
Зато такое упрощение всего (только 0 или 1) дало возможность сделать элементы внутри процессора и памяти очень маленькими. Современные процессоры и модули памяти включают миллиарды различных элементов. При том, что их площадь зачастую не превышает квадратного сантиметра.
- Ничего себе. Буду знать.
- Теперь перейдем к двоичным числам. Там то же самое, что и с восьмеричными, только еще проще.
1) Для записи числа используются 2 цифры: 0,1
2) Число 1012 значит 1*22+0*21+1*20. Т.е. это 1*4+0*2+1*1 =4+1=510
- Да. Я помню. Одна ячейка, которая принимает значение 0 или 1 называется битом. Но т.к. в ней можно сохранить очень мало информации, то их объединяют в группы по 8. И называют такую группу – байтом.
- Именно. Байт – это группа из восьми бит. В нем можно хранить значения: 00000000, 00000001, …, 11111111. Которые соответствуют десятичным 0,1,… 255. Всего 256 значений.
Какое самое большое целое число в Java? Вернее его тип?
- long. long состоит из 8 байт. Т.е. 64 бита и может хранить значения от -263 до 263-1
- Ага. Я не буду касаться темы, как переводить числа из десятичной системы в двоичную или наоборот. Иначе лекция слишком затянется.
Давай лучше еще немного расскажу про 16-ричную систему исчисления.
- Да, очень интересно. Для двоичной и восьмеричной систем мы просто выкинули цифры начиная с двойки или восьмерки. А тут как? Мы добавим новые цифры?
- Именно! Смотри:
1) Для записи числа используются 16 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
2) Число 54316 значит 5*162+4*161+3*160. Т.е. это 5*256+4*16+3*1 =1280+64+3=134710
- Т.е. мы просто добавили буквы в качестве цифр? О_о
- Ага. А что в этом такого? Зачем придумывать новые цифры, когда с этой ролью отлично справляются буквы. Вот смотри:
Шестнадцатеричная цифра | Десятичное значение |
---|---|
0 | 0 |
1 | 1 |
8 | 8 |
9 | 9 |
A | 10 |
B | 11 |
C | 12 |
D | 13 |
E | 14 |
F | 15 |
Про перевод из десятичной системы в шестнадцатеричную тоже рассказывать не буду. Зато есть один интересный факт. Шестнадцатеричная цифра – это ровно 4 бита со значениями от 0 до 15. Поэтому один байт можно записать восемью двоичными цифрами (0 или 1) или двумя шестнадцатеричными.
Пример:
Десятичное число | Двоичное число | Шестнадцатеричное число |
---|---|---|
0 | 0000 0000 | 00 |
1 | 0000 0001 | 01 |
15 | 0000 1111 | 0f |
16 | 0001 0000 | 10 |
31 | 0001 1111 | 1f |
32 | 0010 0000 | 20 |
128 | 1000 0000 | 80 |
129 | 1000 0001 | 81 |
255 | 1111 1111 | ff |
Шестнадцатеричное представление легко приводится к двоичному (и обратно). Поэтому, если где-то в программировании нужно показать именно внутреннее байтовое представление числа, то очень редко прибегают к двоичной записи через 0 и 1. Слишком длинно и не понятно. Шестнадцатеричная запись гораздо читабельней и компактней.
- Согласен. Даже мне понравилось.
- Кстати, в Java можно прямо в коде записывать числа в различных системах исчисления:
Основание | Отличительный признак | Примеры | Неправильные числа |
---|---|---|---|
2 | 0b в начале числа | 0b00001111 | 0b1111121 |
8 | 0 в начале числа | 01234343 | 0128 |
10 | нет | 95459 | 909a |
16 | 0x в начале числа | 0x10ff | 0x1cgh |
- Отличная лекция. Спасибо, Билаабо.
- Привет, Амиго!
Задачи |
---|
1. Осваиваем методы класса Integer Используя метод Integer.parseInt(String, int) реализуйте логику метода convertToDecimalSystem, который должен переводить переданную строку в десятичное число и возвращать его в виде строки. |
2. Конвертер систем счислений Реализуйте логику метода convertNumberToOtherNumerationSystem, который должен переводить число number.getDigit() из одной системы счисления(numerationSystem) в другую (expectedNumerationSystem). Бросьте NumberFormatException, если переданное число некорректно, например, число "120" с системой счисления 2 Валидация для - number.getDigit() - целое не отрицательное Метод main не участвует в тестировании |
- Привет, Амиго!
Хочу рассказать тебе про числовые операторы.
- А мне Билаабо уже рассказывал!
- Да? Тогда я задам всего лишь пару вопросов.
Как увеличить переменную на 1? Приведи как можно больше вариантов.
- Легко:
Код |
---|
x++; |
++x; |
x=x+1; |
x+=1; |
- Верно. А теперь нужно умножить переменную на два?
- Готово:
Код |
---|
x=x*2; |
x*=2; |
x=x+x; |
x+=x; |
x=x<<1; |
x<<=1; |
- Как возвести переменную в девятую степень?
- Тут и думать нечего:
Код |
---|
x = x*x*x*x*x*x*x*x*x; |
x = x*x*x; (x3) x = x*x*x; (x3*x3*x3=x9) |
x = Math.exp( 9 * Math.log(x)); // x9==exp(ln(x9))==exp(9*ln(x)); |
- Корень из числа?
- Запросто:
Код |
---|
Math.sqrt(x) |
x = Math.exp(0.5 * Math.log(x)); // x1/2 = exp(ln(x0.5))==exp(0.5*ln(x)); |
- Синус пи/2?
Код |
---|
x = Math.sin(Math.PI/2); |
Случайное число от 0 до 1?
Код |
---|
x = Math.random(); |
Случайное число от 0 до 3?
Код |
---|
x = Math.random() *3; |
Случайное число от 0 до 10?
Код |
---|
x = Math.random() *10; |
Случайное число от -5 до 5?
Код |
---|
x = Math.random() *10 - 5; |
Случайное число от -1 до 1?
Код |
---|
x = Math.random() *2 - 1; |
Случайное целое число от 0 до 100?
- Даже два варианта:
Код |
---|
int x = (int) (Math.random() *100); |
Random random = new Random(); int x = random.nextInt(100); |
- Отлично! Я поражен. Ты великолепно знаешь тему.
- Привет, Амиго!
Задачи |
---|
1. Экономим время 1. Создайте Producer и Consumer (См. комментарий к методу main) 2. Создайте методы toString, equals и hashCode в классе ShareItem. Для этого в теле класса ShareItem выполни: 2.1. Alt+Enter -> toString() -> Enter 2.2. Alt+Enter -> equals() and hashCode() -> click all 'Next'-s 3. В Producer и Consumer реализуйте метод run так, чтобы вызов метода interrupt прерывал работу consumer и producer трэдов 4. Реализация метода run для Producer: 4.1. Используя метод offer добавить в очередь 9 ShareItem-ов с такими параметрами: ("ShareItem-N", N), где N - номер элемента от 1 до 9 4.2. Перед каждым добавлением вывести фразу "Элемент 'ShareItem-N' добавлен". Используйте System.out.format 4.3. Усыпить трэд на 0.1 секунды 4.4. Если у очереди есть Consumer, не занятый работой, то вывести фразу "Consumer в ожидании!". Просмотрите методы интерфейса TransferQueue, там есть нужный метод. 5. Реализация метода run для Consumer: 5.1. Усыпить трэд на 0.5 секунды 5.2. В бесконечном цикле заберите элемент из очереди методом take и выведите в консоль "Processing item.toString()". 6. Сверьте вывод с файлом output.txt 7. Стек-трейс не выводите в консоль |
- Привет, Амиго!
Сейчас будет небольшая лекция о логических операторах.
Какие логические операторы ты знаешь?
- OR (||), AND (&&), NOT(!)
- Ага. Молодец. А ты помнишь, как они работают?
- Да:
OR дает в результате true, когда есть хотя бы один true
AND дает true, когда оба true.
NOT меняет true на false, а false на true.
- Верно. А в каком порядке выполняются операторы в таком выражении?
boolean a = true; boolean b = false; boolean c = true; boolean result = a && b || !c &&b || !a; |
- Тут все очень просто.
Сначала выполняется операция NOT(!) , затем AND(&&), а в самом конце OR(||).
Т.е. если добавить скобки, то у нас получится:
boolean a = true; boolean b = false; boolean c = true; boolean result = (a && b) || ((!c) && b) || (!a); |
- Все правильно, молодец. И какой же будет ответ?
- 1) (a && b) == (true && false) == false
2) ((!c) && b) == (false && false) == false
3) (!a) == false
4) false || false || false == false
Ответ – false.
- А ты, оказывается, отлично знаешь тему. Тогда я раскрою тебе пару маленьких секретов.
Во-первых, логические выражения вычисляются слева направо.
Во-вторых, тут работает принцип ленивых вычислений (вычислений только при необходимости). Если при вычислении части выражения ответ уже и так понятен, то остальная часть выражения не вычисляется.
Пример |
---|
boolean result = (true && false) || (true && true) || (true && false); |
Если очень нужно создать независимый объект Boolean, то надо создать его явно:
Такое выражение разбито на три части, разделенные знаком OR(||).
Если хотя-бы одна часть будет true, то ответ будет true и дальше можно ничего не считать. Поэтому такое выражение вычисляется вот так:
1) вычисляем первую часть: (true && false) == false
2) вычисляем вторую часть: (true && true) == true
3) третью часть мы не вычисляем, т.к. уже ясно, что ответ будет true.
Такой подход еще называют ленивыми вычислениями.
- Ок. И что тут такого особенного?
- Ничего, пока ты не начинаешь вызывать методы внутри условия. Если часть условия пропускается, то и методы не вызовутся.
Но такой подход получил очень распространенное применение вот почему:
Пример |
---|
Job job = null; if (job!=null && job.isDone()) { … } |
Если во время проверки в условии job равен null, то вызова job.isDone() не произойдет!
- Действительно, первая часть выражения равно false, а затем идет AND(&&), значит, все выражение уже будет равно false и вторую его часть вычислять не обязательно.
- Именно. Хороший подход, да?
- Ага.
- Привет, Амиго!
Задачи |
---|
1. Такие хитрые исключения! Исправьте реализацию метода checkAFlag, чтобы во всех случаях он не приводил к бросанию исключений. Сохраните логику вывода данных. Метод main не участвует в тестировании. |
2. Fork/Join 1. Создайте класс BinaryRepresentationTask. Для этого на красном имени класса нажмите Alt+Enter -> Create Class ... (класс должен наследоваться от RecursiveTask) 2. Реализуйте логику метода compute, должна переводить число в двоичное представление. 3. Используйте методы fork и join. 4. Пример функциональной реализации - метод binaryRepresentationMethod. |
- Привет, Амиго!
И еще одна маленькая лекция о побитовых операторах.
Знаешь же, что кроме логических операторов AND(&&), OR(||) и NOT(!), есть еще побитовые AND(&), OR(|), NOT(~), XOR(^)?
- Ага. В свое время Билаабо давал очень хорошую лекцию на эту тему.
- Так вот, насчет этих операторов у меня есть две новости:
Во-первых, их можно применять к boolean-переменным так же, как и логические операторы.
Во-вторых, при их применении ленивых вычислений не происходит.
Смотри пример:
Код | Аналог |
---|---|
if (a!=null && a.getName()!=null && c!=null) { c.setName(a.getName()); } |
if (a!=null) { if (a.getName()!=null) { if (c!=null) { c.setName(a.getName()); } } } |
Левая часть компактней правой?
- Ага.
- А по смыслу такая же?
- Ага.
- То-то и оно. А вот теперь такое же выражение с использованием побитовых операций:
Код | Аналог |
---|---|
if (a!=null && a.getName()!=null && c!=null) { c.setName(a.getName()); } |
boolean c1 = (a!=null); boolean c2 = (a.getName()!=null); boolean c3 = (c!=null); if (c1) { if (c2) { if (c3) { c.setName(a.getName()); } } } |
Т.е. код тот же самый, но абсолютно все вычисления будут проделаны.
Обрати внимание, что если a равно null, то при вычислении c2 будет выкинуто исключение!
- Ага. Теперь картина более ясна.
- Привет, Амиго!
Задачи |
---|
1. Найдем число 2 в максимальной степени Реализуйте логику метода maxPowerOf2, который должен возвращать число 2 в максимальной степени, которое получается поместить в переданное число Аргументом maxPowerOf2 может быть только положительное число Используйте только операции: 1) побитовые сдвиги, 2) присваивание, 3) побитовое ИЛИ Не оставляйте комментарии |
2. Swap по-новому В классе Pair реализуйте метод swap, который должен для x, y менять местами их значения. Можно использовать только операции 1)исключающее или, 2) присваивание Не оставляйте комментарии, не меняйте остальной код |
- Привет, Амиго!
Сегодня я расскажу тебе еще про несколько интересных вещей в Java.
Бесконечность.
В Java тип double имеет специальные значения для понятий «плюс бесконечность» и «минус бесконечность». Положительное число, разделенное на 0.0, дает «плюс бесконечность», а отрицательное – «минус бесконечность».
Этим понятиям соответствуют специальные константы типа Double:
Код | Описание |
---|---|
public static final double POSITIVE_INFINITY = 1.0 / 0.0; | плюс бесконечность |
public static final double NEGATIVE_INFINITY = -1.0 / 0.0; | минус бесконечность |
- И что, это действительно работает?
- Да. Смотри:
Код |
---|
double inf = Double.POSITIVE_INFINITY; System.out.println(inf); // Бесконечность System.out.println(inf + 1); //Бесконечность+1 ==Бесконечность System.out.println(inf + 10); //Бесконечность+10 ==Бесконечность System.out.println(inf * -1); //равно «минус бесконечность» Double.NEGATIVE_INFINITY |
Вывод на экран: |
Infinity Infinity Infinity -Infinity |
- Действительно работает. А если у нас получается неопределенность? Например, если мы из бесконечность вычитаем бесконечность?
- Для этого в Java есть еще одно понятие – NaN – Not-a-Number (не число).
Его используют в различных ситуациях:
1) Строку конвертируем в число, а в ней есть буквы. Ответ – NaN
2) Бесконечность минус бесконечность. Ответ - NaN
3) Многие другие ситуации, где в ответе ждут число, а получается неизвестно что.
- А какие операции можно производить с Infinity и NaN?
- С NaN все очень просто. Любая операция, где есть NaN, дает в результате NaN.
А с бесконечностью можно и поработать:
Выражение | Результат |
---|---|
n ÷ ±Infinity | 0 |
±Infinity × ±Infinity | ±Infinity |
±(не ноль) ÷ 0 | ±Infinity |
Infinity + Infinity | Infinity |
±0 ÷ ±0 | NaN |
Infinity - Infinity | NaN |
±Infinity ÷ ±Infinity | NaN |
±Infinity × 0 | NaN |
- Логично. Спасибо, Риша.
- Привет, Амиго!
Еще хотел бы рассказать про битовые маски и XOR.
Ты уже знаешь, что числа состоят из битов и над этими битами можно производить различные операции. Битовая маска – это когда мы храним много различных логических значений (true/false) в виде одного целого числа. При этом каждому boolean-значению соответствует определенный бит. Вот как это можно делать:
Числа-степени двойки (1,2,4,8,16,32,…) занимают в двоичном представлении числа всего по одному биту:
Число | Двоичное представление |
---|---|
1 | 0000 0001 |
2 | 0000 0010 |
4 | 0000 0100 |
8 | 0000 1000 |
16 | 0001 0000 |
19 (не степень двойки) | 0001 0011 |
31 (не степень двойки) | 0001 1111 |
Поэтому любое целое число можно рассматривать, как массив бит или массив boolean.
Вот как можно хранить различные логические значения в одном числе:
Значения логических переменных |
---|
boolean a = true; boolean b = false; boolean c = true; boolean d = false; |
Упаковка их в одно число: |
int result = 0; if (a) result+= 1; //1 == 20 – нулевой бит if (b) result+= 2; //2 == 21 – первый бит if (c) result+= 4; //4 == 22 – второй бит if (d) result+= 8; //8 == 23 – третий бит |
Теперь каждый бит равен 1, если соответствующая ему логическая переменная была true.
В нашем случае true были переменные a и c, значит число result равно 1+4 ==5
0000 0101 0000 dcba |
- Вроде понятно, что происходит.
- Ну, раз понятно, то пошли дальше.
В числе int 32 бита, один из них используется для знака, а еще 31 можно использовать для хранения значений 31-й булевской переменной.
- А в числе long 64 бита. Мы там можем хранить 63 логических переменных.
- Ага.
- Полсотни переменных в одном числе. Немало.
А где такое применяется?
- В основном там, где надо компактно хранить много информации об объектах. Когда хранишь много информации об объекте, всегда наберется пара десятков логических переменных. Вот их всех удобно хранить в одном числе.
Именно хранить. Т.к. пользоваться им в работе не так уж удобно.
- Кстати, как раз хотел спросить. А как нам обратно получить логические значение их числа?
- Это совсем не сложно. Вот допустим тебе нужно узнать, установлен ли 6-й бит числа в единицу или нет (2 в пятой степени – это 32). Вот как это можно проверить:
Соединяем числа в одно: |
---|
int a = 32; //25 == 0010 0000 int b = 8; //23 == 0000 1000 int c = 2; //21 == 0000 0010 int result = a+b+c; //32+8+2 == 42 == 0010 1010 |
Восстанавливаем обратное значение – проверяем установлен ли определенный бит: |
int a = result & 32; // 0010 1010 & 0010 0000 = 0010 0000 int b = result & 8; // 0010 1010 & 0000 1000 = 0000 1000 int c = result & 2; // 0010 1010 & 0000 0010 = 0000 0010 |
Т.е. фактически, для работы с битовыми масками нужны три операции:
1) Установить определенный бит в 0
2) Установить определенный бит в 1
3) Проверить, какое значение определенного бита.
Возьмем, например, бит номер 6.
Код | Описание |
---|---|
result = result | 01000000; result |= 01000000; |
Как установить в 1 бит 6? |
result = result & 10111111; result &= 10111111; |
Как установить в 0 бит 6? |
с = result & 01000000; | Как получить значение 6-го бита? |
- Очень необычно, но не сложно. Я ж теперь уже крутой программист.
- И теперь еще маленькая подсказка. Как легко получить числа со снятым или установленным определенным битом: 01000000 или 10111111.
Для этого у нас есть операции сдвига >> и <<.
Вот 1 – это 2 в нулевой степени. Т.е. число с установленным нулевым битом. Нам надо число с установленным 6-м битом.
int c = 1<<6; //0000 0001 <<6 == 0100 0000 == 64 |
- Круто! Действительно полезная вещь для таких дел.
А если мне нужно число, где все биты 1, а один определенный – 0?
- Это тоже не сложно:
int d = ~(1<<6); //~0100 0000 == 10111111 |
Т.е. все очень просто:
Код | Описание |
---|---|
result = result | (1<<6); result |= (1<<6); |
Как установить в 1 бит 6? |
result = result & ~(1<<6); result &= ~(1<<6); |
Как установить в 0 бит 6? |
с = result & (1<<6); | Как получить значение 6-го бита? |
- Выглядит не очень сложно. Но так сразу - не запомню.
- Зато, если встретишь где-то в чужом коде такое страшное выражение:
«result &= ~(1<<6)», будешь знать, что это кто-то просто работает с битовой маской. А если часто будешь встречать, то вскоре все само запомнится.
- Само запомнится… Хорошо звучит. Спасибо за лекцию.
- Привет, Амиго!
Продолжаем наши уроки – учимся гуглить.
Вот тебе несколько заданий:
Задания на поиск в интернете: | |
---|---|
1 | Как получить представление числа в 16-й системе? |
2 | Как получить представление числа в 2-й системе? |
3 | Как получить представление числа в 8-й системе? |
4 | Как получить представление числа в 19-й системе? |
5 | Как преобразовать число из 2-й системы в 10-ю? |
6 | Как преобразовать число из 8-й системы в 10-ю? |
7 | Как преобразовать число из 16-й системы в 10-ю? |
8 | Как преобразовать число из 16-й системы в 2-ю? |
9 | Как преобразовать число из 16-й системы в 2-ю? |
10 | Что такое base64? |
- Привет, Амиго!
Вот тебе дополнительный материал по теме.
- Привет, Амиго!
- Привет, Хулио.
- Очередные десять уровней позади. Как себя чувствуешь?
- Как будто у меня наступил deadlock...
- Хм.. Значит обучение проходит как надо. Садись, отдыхай.
- Привет, Амиго!
Вопросы к собеседованиям | |
---|---|
1 | Что такое NaN? |
2 | Как получить бесконечность в Java? |
3 | Как проверить, что в результате вычисления получилась бесконечность? |
4 | Что такое битовая маска? |
5 | Где применяют битовые маски? |
6 | Как установить бит в единицу в битовой маске? |
7 | Как установить бит в ноль в битовой маске? |
8 | Как получить значение определенного бита в битовой маске? |
9 | Что такое ленивое вычисление выражения? |
10 | Чем отличается использование && и & для типа boolean? |
- Привет, Амиго!
- В секретных лабораториях проекта JavaRush уже разрабатываются сверхсложные задачи нового поколения. Как только задача будет закончена, отлажена и протестирована, тут появится ее условие. А пока немного подожди.