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

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, Linux, Hibernate, Collections, Stream API, многопоточность, файлы, Nginx, Apache, maven, gradle, JUnit, YouTube, новости, руководство, ООП, алгоритмы, головоломки, rest, GraphQL, Excel, XML, json, yaml.