Вы достигли нового уровня

Уровень 30

1. 16-я система исчисления. 2 и 8 системы исчисления. Запись двоичного числа как 1000100В

- Привет, Амиго!

- Привет, Билаабо!

Хочу рассказать тебе немного про различные системы исчисления.

Ты уже слышал, что люди пользуются десятичной системой исчисления. Вот главные факты этого подхода:

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

- Отличная лекция. Спасибо, Билаабо.

2. Задачи по системам исчисления

- Привет, Амиго!

Задачи
1. Осваиваем методы класса Integer

Используя метод Integer.parseInt(String, int) реализуйте логику метода convertToDecimalSystem, который должен переводить переданную строку в десятичное число и возвращать его в виде строки.
2. Конвертер систем счислений

Реализуйте логику метода convertNumberToOtherNumerationSystem, который должен переводить число number.getDigit() из одной системы счисления(numerationSystem) в другую (expectedNumerationSystem). Бросьте NumberFormatException, если переданное число некорректно, например, число "120" с системой счисления 2
Валидация для - number.getDigit() - целое не отрицательное
Метод main не участвует в тестировании

3. Числовые операторы

- Привет, Амиго!

Хочу рассказать тебе про числовые операторы.

- А мне Билаабо уже рассказывал!

- Да? Тогда я задам всего лишь пару вопросов.

Как увеличить переменную на 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);

- Отлично! Я поражен. Ты великолепно знаешь тему.

4. Задачи на числовые операторы

- Привет, Амиго!

Задачи
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. Стек-трейс не выводите в консоль

5. Логические операторы

- Привет, Амиго!

Сейчас будет небольшая лекция о логических операторах.

Какие логические операторы ты знаешь?

- 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 и вторую его часть вычислять не обязательно.

- Именно. Хороший подход, да?

- Ага.

6. Задачи на логические операторы

- Привет, Амиго!

Задачи
1. Такие хитрые исключения!

Исправьте реализацию метода checkAFlag, чтобы во всех случаях он не приводил к бросанию исключений.
Сохраните логику вывода данных.
Метод main не участвует в тестировании.
2. Fork/Join

1. Создайте класс BinaryRepresentationTask. Для этого на красном имени класса нажмите Alt+Enter -> Create Class ...
(класс должен наследоваться от RecursiveTask)
2. Реализуйте логику метода compute, должна переводить число в двоичное представление.
3. Используйте методы fork и join.
4. Пример функциональной реализации - метод binaryRepresentationMethod.

7. Побитовые операторы (&, xor, <<,...)

- Привет, Амиго!

И еще одна маленькая лекция о побитовых операторах.

Знаешь же, что кроме логических операторов 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 будет выкинуто исключение!

- Ага. Теперь картина более ясна.

8. Задачи на побитовые операторы

- Привет, Амиго!

Задачи
1. Найдем число 2 в максимальной степени

Реализуйте логику метода maxPowerOf2,
который должен возвращать число 2 в максимальной степени, которое получается поместить в переданное число
Аргументом maxPowerOf2 может быть только положительное число
Используйте только операции: 1) побитовые сдвиги, 2) присваивание, 3) побитовое ИЛИ
Не оставляйте комментарии
2. Swap по-новому

В классе Pair реализуйте метод swap, который должен для x, y менять местами их значения.
Можно использовать только операции 1)исключающее или, 2) присваивание
Не оставляйте комментарии, не меняйте остальной код

9. NaN, Infinity

- Привет, Амиго!

Сегодня я расскажу тебе еще про несколько интересных вещей в 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

- Логично. Спасибо, Риша.

10. Практическое применение (Битовые маски,...)

- Привет, Амиго!

Еще хотел бы рассказать про битовые маски и 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)», будешь знать, что это кто-то просто работает с битовой маской. А если часто будешь встречать, то вскоре все само запомнится.

- Само запомнится… Хорошо звучит. Спасибо за лекцию.

11. Учимся гуглить. (Перевод чисел в 16 систему)

- Привет, Амиго!

Продолжаем наши уроки – учимся гуглить.

Вот тебе несколько заданий:

 Задания на поиск в интернете:
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?

12. Профессор дает доп. материал

- Привет, Амиго!

Вот тебе дополнительный материал по теме.

Ссылка на дополнительный материал

13. Хулио

- Привет, Амиго!

- Привет, Хулио.

- Очередные десять уровней позади. Как себя чувствуешь?

- Как будто у меня наступил deadlock...

- Хм.. Значит обучение проходит как надо. Садись, отдыхай.

Оригинал видео на YouTube

14. Вопросы к собеседованию по этой теме

- Привет, Амиго!

 Вопросы к собеседованиям
1 Что такое NaN?
2 Как получить бесконечность в Java?
3 Как проверить, что в результате вычисления получилась бесконечность?
4 Что такое битовая маска?
5 Где применяют битовые маски?
6 Как установить бит в единицу в битовой маске?
7 Как установить бит в ноль в битовой маске?
8 Как получить значение определенного бита в битовой маске?
9 Что такое ленивое вычисление выражения?
10 Чем отличается использование && и & для типа boolean?

15. Большая задача

- Привет, Амиго!

- В секретных лабораториях проекта JavaRush уже разрабатываются сверхсложные задачи нового поколения. Как только задача будет закончена, отлажена и протестирована, тут появится ее условие. А пока немного подожди.