Системы счисления: позиционные и непозиционные, перевод чисел

Двоичная, восьмеричная и шестнадцатеричная системы счисления, алгоритмы перевода чисел

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

Системой счисления называют способ записи чисел с помощью определённого набора символов — цифр — и правил их сочетания. Системы счисления делятся на непозиционные, где значение цифры не зависит от её положения в записи числа (классический пример — римская система: в числе XXX каждая X означает одно и то же — десять), и позиционные, где значение цифры зависит от её позиции (разряда) в записи числа. Привычная всем десятичная система — позиционная: в числе 555 каждая пятёрка обозначает разное количество (пятьсот, пятьдесят и пять) в зависимости от занимаемого разряда.

Развёрнутая форма записи числа

В позиционной системе счисления с основанием q используется q различных цифр (от 0 до q−1), а само число записывается как сумма произведений цифр на степени основания — так называемую развёрнутую форму:

$N=a_n{·q}^n+a_{n-1}{·q}^{n-1}+...+a_1{·q}^1+a_0{·q}^0$

Здесь q — основание системы счисления, а aᵢ — цифры числа, каждая из которых принимает значения от 0 до q−1. Например, десятичное число 555 в развёрнутой форме записывается как 5·10²+5·10¹+5·10⁰=500+50+5=555 — именно позиция определяет, какую степень основания умножать на цифру.

Двоичная, восьмеричная и шестнадцатеричная системы

В компьютерной технике из-за простоты технической реализации (два устойчивых состояния элемента — есть сигнал или нет сигнала) базовой является двоичная система счисления с основанием q=2 и всего двумя цифрами: 0 и 1. Однако запись чисел в двоичной системе получается длинной и неудобной для человека, поэтому в информатике широко используют также восьмеричную (основание 8, цифры 0–7) и шестнадцатеричную (основание 16, цифры 0–9 и буквы A–F, где A=10, B=11, …, F=15) системы счисления — они компактнее двоичной, но при этом легко и без остатка переводятся в двоичную и обратно, так как 8=2³ и 16=2⁴.

Перевод целых чисел из десятичной системы

Чтобы перевести целое число из десятичной системы счисления в систему с основанием q, применяют алгоритм последовательного деления с остатком: число делят на q, полученный остаток записывают как очередную цифру результата, а частное снова делят на q — и так до тех пор, пока частное не станет равным нулю. Цифры результата затем выписывают в порядке, обратном порядку их получения — от последнего остатка к первому.

Пример 1. Перевод из десятичной в двоичную систему

Дано: переведите число 45 из десятичной системы счисления в двоичную.

Решение. Последовательно делим число на 2, каждый раз фиксируя остаток:

45:2=22, остаток 1; 22:2=11, остаток 0; 11:2=5, остаток 1; 5:2=2, остаток 1; 2:2=1, остаток 0; 1:2=0, остаток 1. Выписываем остатки в обратном порядке (от последнего к первому):

${45}_{10}={101101}_2$

Ответ: 101101₂. Проверить результат можно по развёрнутой форме: 1·2⁵+0·2⁴+1·2³+1·2²+0·2¹+1·2⁰=32+8+4+1=45 — совпадает с исходным числом.

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

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

Пример 2. Перевод из двоичной системы в десятичную

Дано: переведите число 101101₂ в десятичную систему счисления.

Решение. Записываем число в развёрнутой форме, нумеруя разряды справа налево, начиная с нулевого:

${101101}_2={1·2}^5+{0·2}^4+{1·2}^3+{1·2}^2+{0·2}^1+{1·2}^0$

$=32+0+8+4+0+1=45$

Ответ: 45₁₀ — результат совпадает с исходным числом из примера 1, что подтверждает правильность перевода в обе стороны.

Быстрый перевод между двоичной, восьмеричной и шестнадцатеричной системами

Поскольку 8=2³ и 16=2⁴, между двоичной и восьмеричной, а также между двоичной и шестнадцатеричной системами существует прямой способ перевода без обращения к десятичной системе. Для перевода из двоичной в восьмеричную двоичную запись разбивают справа налево на группы по 3 цифры (триады), дополняя при необходимости самую левую группу нулями слева, и каждую триаду заменяют одной восьмеричной цифрой. Для перевода в шестнадцатеричную систему аналогично разбивают запись на группы по 4 цифры (тетрады) и заменяют каждую на одну шестнадцатеричную цифру. Обратный перевод выполняется так же просто: каждую восьмеричную (шестнадцатеричную) цифру заменяют соответствующей триадой (тетрадой) двоичных цифр.

Пример 3. Перевод из двоичной в шестнадцатеричную систему

Дано: переведите число 110101101₂ в шестнадцатеричную систему счисления.

Решение. Разбиваем число на тетрады справа налево, дополняя левую группу нулём: 0001 1010 1101. Заменяем каждую тетраду шестнадцатеричной цифрой: 0001=1, 1010=A (10), 1101=D (13):

${110101101}_2={1AD}_{16}$

Ответ: 1AD₁₆. Проверка через десятичную систему: 110101101₂=256+128+32+8+4+1=429₁₀, а 1AD₁₆=1·256+10·16+13=256+160+13=429₁₀ — результаты совпадают.

Таблица соответствия чисел в разных системах счисления

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

Рассмотрим программу на Python, реализующую перевод целого числа из десятичной системы в систему с произвольным основанием (алгоритмом деления с остатком) и обратный перевод (по развёрнутой форме, средствами встроенной функции int).

def to_base(n, base):

"""Переводит десятичное целое число n в систему счисления с данным основанием."""

if n == 0:

return "0"

digits = "0123456789ABCDEF"

result = ""

while n > 0:

result = digits[n % base] + result

n //= base

return result

def from_base(s, base):

"""Переводит число, записанное строкой s в данной системе счисления, в десятичное."""

return int(s, base)

print(to_base(45, 2)) # 101101

print(to_base(429, 16)) # 1AD

print(from_base("101101", 2)) # 45

print(from_base("1AD", 16)) # 429

Функция to_base на каждом шаге цикла находит остаток от деления на основание (это и есть очередная цифра результата, младшая из ещё не найденных) и добавляет её в начало строки результата, а затем переходит к целой части от деления — это прямая программная реализация алгоритма из примера 1. Функция from_base использует то, что встроенный тип int в Python умеет разбирать строку числа в любой системе счисления от 2 до 36, если явно указать основание вторым аргументом.

Типичные ошибки

Частая ошибка при переводе делением на основание — забыть перевернуть порядок полученных остатков: правильный результат читается снизу вверх (от последнего остатка к первому), а не в порядке вычисления. Вторая ошибка — при быстром переводе между двоичной и восьмеричной (шестнадцатеричной) системами разбивать двоичную запись на группы неверной длины или начинать группировку не с младшего (правого) разряда, из-за чего группы сдвигаются и результат искажается. Третья ошибка — путать основание системы счисления с количеством используемых в ней цифр: в системе с основанием q цифры принимают значения от 0 до q−1 включительно, а не от 1 до q.

Краткий словарь терминов

Позиционная система счисления — система, в которой значение цифры зависит от её положения (разряда) в записи числа.

Основание системы счисления — количество различных цифр, используемых в позиционной системе счисления.

Развёрнутая форма числа — запись числа в виде суммы произведений его цифр на соответствующие степени основания.

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

Тетрада — группа из четырёх двоичных цифр, используемая при переводе между двоичной и шестнадцатеричной системами.

Шестнадцатеричная система счисления — позиционная система с основанием 16, использующая цифры 0–9 и буквы A–F.

Заключение

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