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

Введение#

Числа являются неотъёмлимой частью нашей жизни и десятичная система счисления глубоко пустила корни в наше сознание. В современном мире обывателю непривычно представить, что числа можно обозначать как-то иначе. В школе нас знакомят с римскими цифрами, на уроках информатики мы узнаём про привычную компьютеру двоичную систему, но в быту крайне редко приходится сталкиваться с чем-то помимо десятичной системы.

На самом же деле, в числе $10$ нет ничего особенного. Существует целое множество способов представить числа иначе. Некоторые способы в чём-то удобнее других, однако нет того самого уникального способа, каким можно было бы считать десятичную в силу её распространнёности. Ненадолго, мы погрузимся в краткий исторический экскурс, чтобы проследить этапы развития систем обозначения чисел, узнаем особенности их работы, достинства и недостатки. Цель этого путешествия — понять устройство систем счисления и научиться переводить числа из одной системы в другую.

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

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

Непозиционные системы счисления#

Непозиционным системам счисления характерно отсутствие связи между величиной цифры и её разрядом (положением). Этот тип систем наиболее древний крайне прост в использовании.

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

Всё это сохраняло свою простоту и практичность, пока числа оставались небольшими. Запись крупных чисел в подобной манере становится непосильным занятием; чтобы записать такое относительно небольшое число как один миллион — пришлось бы потратить достаточно много времени и сил, а скорее всего и вовсе сбиться со счёту.

Следующим этапом развития стало введение понятия «групп» как дополнительных специальных символов для упрощения записи крупных чисел. Первые группы появились для таких чисел как 5 и 10, так как изначально для счёта использовались пальцы рук. Группировка позволила продвинуться заметно дальше и создать более практичные системы счисления.

Древнеегипетская десятичная система#

Одним из ранниих примеров непозиционных систем счисления являются символы, встречаемые в иероглифах древнего Египта. В древнеегипетской десятичной системе использовались специальные символы для обозначения чисел различных степеней десяти: $1, 10, 100, 1000$ и так далее:

𓏤 1
𓎆 10
𓍢 100
𓆼 1000
𓂭 10000
𓆐 100000
𓁨 1000000

Так как основой записи и обозначения чисел является число 10, система называется десятичной, а само число 10 — основанием системы. Все числа в Египетской системе записывались как комбинация символов, каждый из которых не повторялся более девяти раз. Итоговое значение числа определялось суммой значений символов, а порядок расположения символов не имел значения.

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

Самым узнаваемым примером непозиционных систем счисления являются римские цифры. Благодаря существенному влиянию древнего Рима в течение долгого времени, превосходство римской системы над другими известными на то время и объясняет почему римская система сохраняет свою распространнёность даже спустя почти 2 000 лет в научной и теологической литературе.

Римская система обладала серьёзным преимуществом благодаря простоте записи, ведь для обозначений использовалось несколько букв латинского алфавита: $I, V, X, L, C$ ; а в таких числах как $III$ было проще увидеть тройку, чем в арабской $3$ . Всё существенно упрощало использование системы для типичного обывателя тех времён.

Римская система за время своего существования претерпела ряд заметных изменений и в целом, считается одной из самых неструктурированных систем. К примеру, были добавлены новые символы для записи крупных чисел, введенно обозначение нуля, но в основе своей использовались следующие общепринятые обозначения:

egin{array}{c:c:c:c:c:c:c} I & V & X & L & C & D & M\ hline 1 & 5 & 10 & 50 & 100 & 500 & 1000 end{array}

Несмотря на наличие символов для чисел $50$ и $500$ , римская система имеет основание 10. В привычном нам виде римская система позволяет записать числа до $3 999$ включительно, так как один символ не может повторяться более трёх раз:

Перевод арабских цифр в римские

Позиционные системы счисления#

Позиционные системы являются следующим этапом развития систем счисления. Как ясно из названия, позиционную систему характеризует связь разряда цифры числа с его значением. Привычная нам десятичная система счисления как раз и является примером позиционных систем.

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

Попробуем разобраться, каким образом формируется число в позиционной системе счисления. В системе с произвольным основанием $r$ — в распоряжении имеется $r$ доступных символов, используя (пусть и не совсем обязательно) привычные числовые обозначения, получаем ряд $0, 1, 2, ... , r - 1$ . К примеру, в привычной десятичной системе это $0, 1, 2, ... , 9$ .

Используя данный набор символов, можно вести счёт до числа $r - 1$ , далее позиционная система переиспользует те же обозначения, располагая символы в последующей позиции, именуемой разрядом: $r_n ... r_2 r_1 r_0$ . Разряды располагаются один за другим по мере необходимости, когда уже имеющихся обозначений становится недостаточно.

Если первый разряд имеет $r$ возможных комбинаций, то последующий отображает уже $r * r = r^2$ комбинаций. Таким образом, каждый новый разряд увеличивает количество комбинаций в $r$ раз. К примеру в десятичной системе, в каждой тысяче — десять сотен, в каждой сотне — десять десятков, в каждом десятке — десять символов.

Итого, в позиционной системе с основанием $r$ число $N$ может быть записано уникальной комбинацией:

$egin{aligned} N &= sum_{i} d_i r^i \ &= ... + d_2 r^2 + d_1 r^1 + d_0 r^0,\ end{aligned}$

где $d_i$ - цифры числа, используемые для обозначения в ряду $0, 1, 2, ... , r - 1$ .

Мы ещё вернёмся к данному равенству при переводе чисел из одной системы в другую, и попытаемся объяснить принцип его работы с помощью аналогии. Прежде, ознакомимся с некоторыми примерами позиционных систем.

Вавилонская шестидесятеричная система#

Вавилонская система счисления сформировалась в Древнем Вавилоне в районе около двух тысяч лет до нашей эры. Для обозначения использовалось два символа: «прямой» клин — для единиц, и «лежачий» — для десятков.

𒐕 1
𒌋 10

Вавилонская шестидесятеричная система счисления является первой известной системой, основанной на позиционном принципе, пусть и частично. Частичность обсуловлена нехваткой символа отсутствующего разряда — числа нуль. Заметно позже, лишь за 300 лет до нашей эры, недоразумение всё же исправили добавлением символа в форме двух клиньев:

𒑊 0

Использовалось «новвоведение» изредка и не совсем практично. Нуль не использовался для обозначения крайних значений, по этой причине различать некоторые числа, такие как $77$ и $7700$ было невозможно, о значении приходилось догадываться из контекста.

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

Двоичная система имеет ряд серьёзных преимуществ, благодаря которым она смогла отодвинуть десятичную систему со своего коронного места в области электронных технологий. Двоичная система имеет основание $2$ и использует два символа: единицу и нуль. Поначалу счёт в двоичной системе может сбить с толку, но и тут используются те же самые принципы, знакомые нам из десятичной системы: $0, 1, 10, 11, 100, 101, 110, ...$ .

Число в двоичной системе использует заметно больше символов для записи аналогичного числа в десятичной; например, $12 345$ имеет двоичное представление как $11000000111001$ . Причина кроется в том, что цифра в двоичной системе характеризует лишь две возможности: $0$ или $1$ , в то время как в десятичной их все $10$ ; другими словами двоичный символ несёт меньшее количество информации.

Намного проще сконструировать устройство, различающее два состояния, нежели целых 10; однако большую роль играет возможность не только хранить числовую информацию, но и возможность кодировать логические выражения. Та самая дитохомия «истины» и «лжи», имеющей значение единицы и нуля, и всё это сводится лишь к двум символам.

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

Шестидесятеричная система так же широко применяется в сфере компьютерных технологий и имеет основание $16$ ; система использует привычные цифры $0-9$ и латинские буквы $A-F$ для обозначения чисел в промежутке с $10$ по $15$ , к примеру число $256_10$ будет записываться как $FF_16$ . Система широко применяется в низкоуровневом программировании, поскольку минимальной адресуемой единицей памяти является 1 байт, содержащий 8 бит, значение которого удобно записать двумя шеснадцатеричными цифрами.

Помимо того, на шеснадцатеричную систему можно натолкнуться работая с цветами в формате RGB записываемыми в формате HEX числа.

Преобразование из одной системы в другую#

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

Важно понимать, преобразования практически никогда не производятся человеком вручную, лишь в академических целях. Для расчётов есть компьютеры. Мы, в свою очередь, делаем акцент на понимании принципов работы перевода позиционных систем.

Немного о структуре чисел в позиционной системе#

Если снова взглянуть на определение числа в позиционной системе, то можно представить его структуру подобно молекуле. Подобным образом, как и молекула — состоит из атомов, так и число состоит из других, предопределённых групп. Размеры этих групп определяются основанием системы.

К примеру, для десятичной системы это степени числа десять, для двоичной — степени двойки. Именно из этих чисел и формируется число в позиционной системе, попробуйте убедиться сами:

Разбивка числа на составляющие

1234₁₀

1 4
10 3
100 2
1000 1

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

Преобразование из десятичной системы в произвольную#

Исходя из аналогии с «молекулой», для перевода числа в произвольную систему с основанием $r$ наша задача сводится к переопределению той самой однозначной комбинации «атомов» ( $r^0, r^1, r^2, r^3, ...$ ), сумма которых равна исходному числу в десятичной системе.

Действовать необходимо по принципу жадного алгоритма:

Определяем наибольшее число степени $r^n$ , не превышающее вводное число;
Вычитаем наибольшее число степени $r^n$ максимальное количество раз из исходного числа; степень $n$ определяет положение порядка, а количество вычитаний — его значение;
Пункты $1, 2$ повторяются до тех пор, исходное число не обратится в нуль.

Важно, при записи результатов не пропускать неиспользованные значения степеней. Степени должны быть записаны без пропусков, при отсутвии используется нуль.

Ниже можно ознакомиться с этапами перевода числа из десятичной системы в произвольную для лучшего понимания:

Этапы перевода десятичной позиционной системы в произвольную

\begin{array}{c:c:c:c:c:c:c} 2^6&2^5&2^4&2^3&2^2&2^1&2^0\\ \hline 1&1&0&0&1&0&1\\ \end{array}

\begin{aligned} 2^6 &\leq 101 &\leq 2^7\\2^5 &\leq 37 &\leq 2^6\\2^2 &\leq 5 &\leq 2^3\\2^0 &\leq 1 &\leq 2^1\\ \end{aligned}

\begin{aligned} 101 &- {\color{#7A82E3}1} \cdot 2^6\\37 &- {\color{#7A82E3}1} \cdot 2^5\\5 &- {\color{#7A82E3}1} \cdot 2^2\\1 &- {\color{#7A82E3}1} \cdot 2^0\\ \end{aligned}

Преобразование из произвольной системы в десятичную#

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

Разобьем число на разряды и запишем каждое число число как $a_i * r^i$ , где $i$ - номер разряда, а $a_i$ - значение данного разряда;
Найдём сумму всех значений, получив итоговый результат.

Пример расчёта числа можно увидеть ниже:

Перевод числа в десятичную позиционную систему

10010₂

\to

18₁₀

2⁰ 0
2¹ 1
2² 0
2³ 0
2⁴ 1

Тренажёр#

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

Упражнение поддерживает основания систем от $2$ до $36$ включительно. Основания от $11$ и выше — используют заглавные буквы латинского алфавита, точно так же как и шестнадцатеричная система. Например, система с основанием $36$ — использует набор символов $1 ... 9, A ... Z$ .

Для ввода предоставлена виртуальная клавиатура, также доступен ввод с помощью физической клавиатуры в случае наличия фокуса на виртуальной (например, коснувшись). При необходимости, можно очистить ввод клавишей Delete или отменить последний выбранный символ клавишей Backspace. Для проверки результата нужно активировать соответствующую кнопку или воспользовавшись клавишей Enter.

В случае ошибки можно продолжать попытку перевода сколь угодно раз.

Navigation

User Preferences

Interface language

Theme