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

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

Совокупность приемов наименования и обозначение чисел называется системой счисления. В качестве условных знаков для записи чисел используются цифры.

Система счисления, в которой значение каждой цифры в произвольном месте последовательности цифр, обозначающей запись числа, не изменяется, называется непозиционной.

Система счисления, в которой значение каждой цифры зависит от места в последовательности цифр в записи числа, называется позиционной.

Чтобы определить число, недостаточно знать тип и алфавит системы счисления. Для этого необходимо еще использовать правила, которые позволяют по значениям цифр установить значение числа. Простейшим способом записи натурального числа является изображение его с помощью соответствующего количества палочек или черточек. Таким способом можно обозначить небольшие чисел. Следующим шагом было изобретение специальных символов (цифр). В непозиционной системе каждый знак в записи независимо от места означает одно и то же число. Хорошо известным примером непозиционной системы счисления является римская система, в которой роль цифр играют буквы алфавита: І - один, V - пять, Х - десять, С - сто, L - пятьдесят, D -пятьсот, М - тысяча. Например, 324 = СССХХІ. В непозиционной системе счисления арифметические операции выполнять неудобно и сложно.

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

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

Общеупотребительной формой записи числа является сокращенная форма записи разложения по степеням основы системы счисления, например

130678=1*10⁵+3*10⁴+0*10³+6*10²+7*10¹+8

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

Проблема выбора системы счисления для представления чисел в памяти компьютера имеет большое практическое значение. В случае ее выбора обычно учитываются такие требования, как надежность представления чисел при использовании физических элементов, экономичность (использование таких систем счисления, в которых количество элементов для представления чисел из некоторого диапазона было бы минимальном). Для изображения целых чисел от 1 до 999 в десятичной системе достаточно трех разрядов, то есть трех элементов. Поскольку каждый элемент может находиться в десяти состояниях, то общее количество состояний - 30, в двоичной системе счисления: 999₁₀=1111100₂, необходимое количество состояний - 20 (индекс внизу числа - основа системы счисления).

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

+ 0 1 * 0 1

0 0 1 0 0 0

1 1 10 1 0 1

Поскольку 2³=8, а 2⁴=16, то каждых три двоичных разряда числа образовывают один восьмиричный, а каждых четыре двоичных разряда - один шестнадцатиричный. Поэтому для сокращения записи адресов и содержимого оперативной памяти компьютера используют шестнадцатиричную и восьмиричную системы счисления. Ниже, в таблице 1 приведены первые 16 натуральных чисел записанных в десятичной, двоичной, восьмиричной и шеснадцатиричной системах счисления.

Таблица 1

10 2 8 16

0 0000 0 0

1 0001 1 1

2 0010 2 2

3 0011 3 3

4 0100 4 4

5 0101 5 5

6 0110 6 6

7 0111 7 7

8 1000 10 8

9 1001 11 9

10 1010 12 A

11 1011 13 B

12 1100 14 C

13 1101 15 D

14 1110 16 E

15 1111 17 F

Для отладки программ и в других ситуациях в программировании актуальной является проблема перевода чисел из одной позиционной системы счисления в другую. Если основа новой системы счисления равняется некоторой степени старой системы счисления, то алгоритм перевода очень простой: нужно сгруппировать справа налево разряды в количестве, равном показателю степени и заменить эту группу разрядов соответствующим символом новой системы счисления. Этим алгоритмом удобно пользоваться при переводе числа из двоичной системы счисления в восьмиричную или шестнадцатиричную. Например, 10110₂= 10110 =26₈, 1011100₂= 1011100 =5C₈

Перевод чисел из восьмиричной или шестнадцатиричной систем счисления в двоичную происходит по обратному правилу: один символ старой системы счисления заменяется группой разрядов новой системы счисления, в количестве равном показателю степени новой системы счисления. Например, 472₈= 100111010 =100111010₂, B516= 10110101 =10110101₂

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

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

1. Для перевода чисел из системы счисления с основой p в систему счисления с основой q, используя арифметику новой системы счисления с основой q, нужно записать коэффициенты разложения, основы степеней и показатели степеней в системе с основой q и выполнить все действия в этой самой системе. Очевидно, что это правило удобно при переводе в десятичную систему счисления. Например:

из шестнадцатиричной в десятичную:

92C8₁₆=9*10₁₆³+2*10₁₆²+C*10₁₆¹+8*10₁₆⁰= 9*16₁₀³+2*16₁₀²+12*16₁₀¹+8*16₁₀⁰=37576

из восьмиричной в десятичную:

735₈=7*10₈²+3*10₈¹+5*10₈⁰= 7*8₁₀²+3*8₁₀¹+5*8₁₀⁰=477₁₀

из двоичной в десятичную:

110100101₂=1*10₂⁸+1*10₂⁷+ 0*10₂⁶+1*10₂⁵+0*10₂⁴+0*10₂³+ 1*10₂²+0*10₂¹+1*10₂⁰= 1*2₁₀⁸+1*2₁₀⁷+0*2₁₀⁶+1*2₁₀⁵+ 0*2₁₀⁴+0*2₁₀³+1*2₁₀²+0*2₁₀¹+ 1*2₁₀⁰=421₁₀

2. Для перевода чисел из системы счисления с основой p в систему счисления с основой q с использованием арифметики старой системы счисления с основой p нужно:

• для перевода целой части:
• последовательно число, записанное в системе основой делить на основу новой системы счисления, выделяя остатки. Последние записанные в обратном порядке, будут образовывать число в новой системе счисления;
• для перевода дробной части:
• последовательно дробную часть умножать на основу новой системы счисления, выделяя целые части, которые и будут образовывать запись дробной части числа в новой системе счисления.

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

Пример: 999,35₁₀=1111100111,01011₂