Системы счисления

26 февраля 2023

Тэги: Java, алгоритмы, головоломки, руководство.

Содержание

Что такое системы счисления
Десятичная система счисления
Единичная система счисления
Римская система счисления
Двоичная система счисления
Восьмеричная система счисления
Шестнадцатеричная система счисления
Реализация на Java

Что такое системы счисления

В математике и программировании понятие системы счисления занимает очень важную роль. За столь умным названием кроется довольно простая идея. Система счисления – это способ записи (представления) чисел.

Иными словами, как записать любое сколь угодно большое число, имея в арсенале всего 10 цифр-символов? Правильно, комбинируя эти цифры друг с другом. Причём расположение цифры в записи числа имеет значение, ибо 123 не равно 321. Хотя цифры используются одинаковые.

Десятичная система счисления

В повседневной жизни мы используем десятичную систему счисления, хоть и не задумываемся над этим. Просто так исторически сложилось. Десятичной она называется потому что для записи любого числа используется ровно 10 цифр.

Обратите внимание, что любое число в десятичной записи можно разбить на слагаемые и степени числа 10. Например:

123 = 100 + 20 + 3 = 1*10^2 + 2*10^1 + 3*10^0
// символ ^ означает возведение в степень

Однако помимо десятичной существуют другие системы счисления. И у каждой из них своя область применения.

Единичная система счисления

Наверное, самой первой системой счисления, возникшей на заре человечества, была единичная система счисления. Запись любого числа делалась единственным символом – вертикальной чертой – как если бы мы делали засечки на стволе дерева, подобно потерпевшему крушение на необитаемом острове. Число чёрточек равно значению. Чем больше число – тем длиннее его запись.

1 = |
3 = |||
10 = ||||||||||

Римская система счисления

В какой-то момент люди задумались, а что, если нам использовать разные символы в записи числа? Как развитие этой мысли, следующая система счисления, которая приходит на ум – римская. Она используется и в наше время. В ней определённые числа обозначались соответствующей буквой:

Число	Обозначение
1	I
5	V
10	X
50	L
100	C
500	D
1000	M

В римской системе счисления важно взаимное расположение бОльших и меньших цифр относительно друг друга. Если меньшее число находится слева от большего (и при этом не может повторяться), то оно вычитается из большего, а если справа – прибавляется.

3 = III = 1 + 1 + 1
20 = XX = 10 + 10
23 = XXIII = X XIII = 10 + 10 + 3
19 = XIX = X IX = 10 + 10 - 1
42 = XLII = XL II = 50 - 10 + 2
62 = LXII = LX II = 50 + 10 + 2

Примечательно, что 0 нельзя записать в виде римского числа.

Двоичная система счисления

В вычислительной технике широко распространена двоичная система счисления. Любое число в ней записывается как последовательность нулей и единиц. Это тесно связано с технической реализацией ячеек памяти в комьютере. 0 – низкий заряд, 1 – высокий. Каждая такая ячейка называется битом. Бит – это минимальная единица информации.

Рассмотрим несколько примеров:

"11" = 1*2^1 + 1*2^0 = 2
"101" = 1*2^2 + 0*2^1 + 1*2^0 = 5
"1111" = 1*2^3 + 1*2^2 + 1*2^1 + 1*2^0 = 15

Если приглядеться повнимательнее, можно увидеть следующую закономерность. Двоичная запись числа – это сумма чисел, в котором цифра соответствующего разряда умножается на 2 в степени, равной индексу расположения этой цифры. Самая правая цифра умножается на 2 в степени 0, т.е. на 1. Самая левая – на 2 в степени, равной количеству цифр в записи числа минус 1.

Восьмеричная система счисления

Двоичная запись также не отличается компактностью. Поэтому логичным развитием двоичной системы в вычислительной технике стала восьмеричная. Так мы можем одной цифрой записать значение трёх бит. Общий принцип остался прежним, но теперь у нас используется не только 0 и 1, а все цифры от 0 до 7:

"10" = 1*8^1 +0*8^0 = 8 + 0 = 8
"16" = 1*8^1 + 6*8^0 = 8 + 6 = 14
"123" = 1*8^2 + 2*8^1 + 3*8^0 = 64 + 16 + 3 = 83

Шестнадцатеричная система счисления

В какой-то момент инженеры ЭВМ пошли ещё дальше и решили компактно записывать целый байт данных. 1 байт = 8 бит. Всего 256 возможных комбинаций, а 256 – это 16 в квадрате. Так появилась шестандцатеричная система счисления, в которой используются не только цифры от 0 до 9, но и буквы от A до F. Откуда взялись буквы? Просто нужно было как-то обозначать одним символом цифры от 10 до 16. В остальном прежний принцип сохраняется.

"A" = 10*16^0
"B5" = 11*16^1 + 5*16^0 = 181
"D03" = 13*16^2 + 0*16^1 + 3*16^0 = 3331

Поскольку в шестандцатеричной записи используются буквы, то некоторые числа в этой системе могут быть записаны только с помощью букв. То есть некоторые слова английского алфавита являются шестнадцатеричными числами! Попробуйте вычислить, чему равны в шестандцатеричной системе слова «BAD», «CAFE», «FACADE».

Реализация на Java

Следуя приведённой выше логике, реализуем на Java алгоритм для преобразования из двоичной, восьмеричной или шестнадцатеричной системы в привычную нам десятичную.

Метод convertToDecimalNumber() принимает на вход запись числа в виде строки и основание системы счисления (2, 8 или 16).

public static int convertToDecimalNumber(String value, int radix) {
    int decimal = 0;
    for (int i = 0; i < value.length(); i++) {
        char digit = value.charAt(i);
        decimal = decimal * radix + hexCharToInt(digit);
    }
    return decimal;
}

Здесь мы в начале инициализируем результат decimal нулём. Затем проходимся по каждому символу строки и преобразуем его в соответствующую цифру с помощью метода hexCharToInt(). После этого происходит умножение результата предыдущей итерации на основание системы счисления.

Вспомогательный метод hexCharToInt() выглядит тривиально:

private static int hexCharToInt(char c) {
    return switch (c) {
        case '0' -> 0;
        case '1' -> 1;
        case '2' -> 2;
        case '3' -> 3;
        case '4' -> 4;
        case '5' -> 5;
        case '6' -> 6;
        case '7' -> 7;
        case '8' -> 8;
        case '9' -> 9;
        case 'A', 'a' -> 10;
        case 'B', 'b' -> 11;
        case 'C', 'c' -> 12;
        case 'D', 'd' -> 13;
        case 'E', 'e' -> 14;
        case 'F', 'f' -> 15;
        default -> throw new RuntimeException("Unexpected char: " + c);
    };
}

Его можно записать гораздо компактнее, пользуясь тем свойством, что в ASCII кодировке все цифровые символы идут подряд и их можно вычитать друг из друга как цифры. Но я решил привести более общую реализацию.

Теперь проверим работу нашего метода:

System.out.println(convertToDecimalNumber("0", 2)); // 0
System.out.println(convertToDecimalNumber("101", 2)); // 5
System.out.println(convertToDecimalNumber("1111", 2)); // 15

System.out.println(convertToDecimalNumber("10", 8)); // 8
System.out.println(convertToDecimalNumber("77", 8)); // 63
System.out.println(convertToDecimalNumber("567", 8)); // 375

System.out.println(convertToDecimalNumber("ff", 16)); // 255
System.out.println(convertToDecimalNumber("BAD", 16)); // 2989
System.out.println(convertToDecimalNumber("Facade", 16)); // 16435934

Как видите, с шестнадцатеричными значениями бывает очень забавно работать.

Но это «нативная» реализация алгоритма. Её писать совершенно не обязательно, т.к. в стандартной библиотеке есть готовый метод Integer.parseInt(), принимающий те же параметры, что и наш самописный метод.

public static int convertToDecimalNumber(String value, int radix) {
return Integer.parseInt(value, radix);
}

Напоследок хочу заметить, что на моём сайте есть онлайн-утилита для преобразования из одной системы счисления в другую.

См. также

Облако тэгов

Kotlin, Java, Spring, Spring Boot, Spring Data, SQL, PostgreSQL, Oracle, H2, Linux, Hibernate, Collections, Stream API, многопоточность, чат-боты, нейросети, файлы, devops, Docker, Nginx, Apache, maven, gradle, JUnit, YouTube, новости, руководство, ООП, алгоритмы, головоломки, rest, GraphQL, Excel, XML, json, yaml.