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

Задача перевода чисел из одной позиционной системы счисления в другую является одной из главных в компьютерной арифметике. Ее можно сформулировать следующим образом: требуется перевести некоторое число (X), записанное в позиционной системе счисления с основанием (k₁), в такую же систему счисления, имеющую основание (k₂).

Другими словами: по изображению операнда (X) в системе счисления с основанием (k₁) найти изображение (Y) того же операнда в системе с основанием (k₂).

. (2.18)

. (2.19)

Существуют 2 группы методов перевода: табличные и расчетные.

1.Табличные методы. В простейшем случае в памяти компьютерной системы хранится таблица соответствия между всеми числами в системах счисления с основаниями (k₁) и (k₂), а сама процедура перевода сводится к обращению к этой таблице. Плюс табличных методов перевода заключается в высокой скорости перевода. Минус табличных методов перевода заключается в том, что размеры такой таблицы и, следовательно, занимаемый ею объем памяти, часто оказываются технически неприемлемыми. Поэтому с целью уменьшения занимаемого объема памяти в ней хранят только таблицы соответствия цифр заданных систем счисления и весов их разрядов. Перевод чисел осуществляется путем обращения к этим таблицам и выполнения операций умножения и сложения в соответствии с выражением для КЭЧ. Если, например, числа в системе с основанием (k₁) представлены (n - разрядами), то по первому варианту размерность таблицы, сохраняемой в памяти, определяется () строками, а по второму варианту - (k₁+n+1) строками.

2.Расчетные методы. В общем виде решение задачи перевода можно представить как нахождение коэффициентов (y_j) нового ряда, изображающего число в системе счисления с основанием (k₂).

Тривиальным методом решения является. Основная трудность - в выборе максимальной степени (), которая все еще содержится в числе (X).

Все действия должны выполняться по правилам (k₁-арифметики), т.е. по правилам исходной арифметики. После нахождения максимальной степени основания проверяют «вхождение» в заданное число всех степеней нового основания, меньших максимального. Каждая из отмеченных степеней может входить в ряд не более раз, что определяется условием:

(2.20)

Для перевода операнда (X) в систему с основанием (k₂) необходимо записать (X) в форме для вычисления количественного эквивалента, далее заменить цифры (x_i) и основания (k₁) их эквивалентами в системе с основанием (k₂), а потом вычислить полученное выражение по правилам арифметики в системе с основанием (k₂). Этот алгоритм удобно использовать в случае, когда (k₁< k₂), причем (k₂) соответствует системе счисления, где просто и " привычно" выполняются операции сложения и умножения (например, десятичной системе). Для упрощения вычислений при этом используют схему Горнера, в соответствии с которой формула для КЭЧ преобразуется путем многократного вынесения за скобки:

Y=(...((x_s-1k₁+x_s-2)k₁+x_s-3)k₁+...+x₁)k₁+x₀+…+(..(((0+x_-m) k₁^-1 +

+x_-m+1)k₁^-1+x_-m+2)k₁^-1+...+x_-1)k₁^-1. (2.21)

Отсюда видно, что для получения целой части числа необходимо выполнить (s) шагов вычислений, а для получения дробной - (m).

Т.е., алгоритм МНЗ, по существу, состоит из двух алгоритмов, а именно: перевода целого числа, выполняемого в соответствии с рекуррентной формулой

(2.22)

где А₀=0, A_s - целая часть исходного числа в системе счисления с основанием (k₂); и перевода дробей по рекуррентной формуле:

(2.23)

где В₀=0, В_m - дробная часть исходного числа в системе с основанием

(k₂ ).

Рассмотренный алгоритм не имеет каких-либо теоретических ограничений на область своего применения.

Однако при переводе целых чисел в системы с " непривычными" основаниями, особенно в случае (k₁> k₂), использование этого алгоритма связано с весьма громоздкими вычислениями.

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

В случае (k1> k2). Целое число (X) запишем в системе с основанием (k₂) с использованием схемы Горнера:

Y=(…((y_r-1k₂+y_r-2)k₂+y_r-3)k₂+…+y₁)k₂+y₀. (2.24)

Правую часть выражения разделим на величину основания (k₂). В результате получим первый остаток (y₀) и целую часть:

Y=(…((y_r-1k₂+y_r-2)k₂+y_r-3)k₂+…+y₁). (2.25)

Разделив целую часть на(k₂), найдем второй остаток(y₁).

Повторяя процесс деления r раз, получим последнее целое частное, которое, по условию, меньше основания системы счисления (k₂) и является старшей цифрой числа, представленного в системе с основанием (k₂).

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

- для перевода целого числа в новую систему его надо последовательно делить на основание новой системы счисления до тех пор, пока не получится частное, у которого целая часть равна (0).

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

Алгоритмперевода целых чисел из одной позиционной системы счисления в другую можно сформулировать следующим образом:

- операнд (X) необходимо делить на (k₂) по правилам целочисленного деления в исходной системе с основанием (k₁) до получения остатка.

Если частное от такого деления не нуль, то далее частное рассматривается как делимое и процесс деления на (k₂). продолжают.

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

Остаток, полученный при первом делении на (k₂), представляет собой цифру результата с весом (), остаток от второго деления - цифру результата с весом () и т.д.

Последний остаток является старшей цифрой результата.

Например: необходимо перевести из десятичной системы счисления в двоичную систему счисления целое число А = 53₍₁₀₎.

Решение: произведем последовательное деление исходного числа (53₍₁₀₎) на основание новой системы счисления (2). Перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в двоичную систему счисления, приведен на рис. 2.14:

Рисунок 2.14 - Перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в двоичную систему счисления

Из сформулированного выше правила при перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в двоичную систему счисления получим:

53₍₁₀₎ – 110101₍₂₎.

Например: необходимо перевести из десятичной системы счисления в троичную систему счисления целое число А = 53₍₁₀₎.

Решение: произведем последовательное деление исходного числа (53₍₁₀₎) на основание новой системы счисления (3). Перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в троичную систему счисления, приведен на рис. 2.15:

Рисунок 2.15 - Перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в троичную систему счисления

Из сформулированного выше правила при перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в троичную систему счисления получим:

53₍₁₀₎ – 1222₍₃₎.

Например: необходимо перевести из десятичной системы счисления в пятеричную систему счисления целое число А = 53₍₁₀₎.

Решение: произведем последовательное деление исходного числа (53₍₁₀₎) на основание новой системы счисления (5). Перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в пятеричную систему счисления, приведен на рис. 2.16:

Рисунок 2.16 - Перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в пятеричную систему счисления

Из сформулированного выше правила при перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в пятеричную систему счисления получим:

53₍₁₀₎ - 203₍₅₎.

Например: необходимо перевести из десятичной системы счисления в восьмеричную систему счисления целое число А = 53₍₁₀₎.

Решение: произведем последовательное деление исходного числа (53₍₁₀₎) на основание новой системы счисления (8). Перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в восьмеричную систему счисления, приведен на рис. 2.17:

Рисунок 2.17 - Перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в восьмеричную систему счисления

Из сформулированного выше правила при перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в восьмеричную систему счисления получим:

53₍₁₀₎ - 65₍₈₎.

Например: необходимо перевести из десятичной системы счисления в шестнадцатеричную систему счисления целое число А = 53₍₁₀₎.

Решение: произведем последовательное деление исходного числа (53₍₁₀₎) на основание новой системы счисления (16). Перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в шестнадцатеричную систему счисления, приведен на рис. 2.18:

Рисунок 2.18 - Перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в шестнадцатеричную систему счисления

Из сформулированного выше правила при перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в шестнадцатеричную систему счисления получим:

53₍₁₀₎ - 35₍₁₆₎.

При переводе из не десятичной системы счисления в десятичную систему счисления, то ввиду ее не привычности для человека производство в ней арифметических действий значительно затруднено. В этом случае для преобразования чисел необходимо воспользоваться формулой (2.6):

.

Например: перевести из двоичной системы счисления в десятичную систему счисления целое число А = 110101₍₂₎.

Решение: Запишем число (А) в виде суммы произведений степеней основания на соответствующую цифру в десятичной системе счисления:

А = 110101₍₂₎ = 1∙ 2⁵ + 1∙ 2⁴ + 0∙ 2³ + 1∙ 2² + 0∙ 2¹ + 1∙ 2⁰ = 1∙ 32 + 1∙ 16 + 1∙ 2⁵ + 0∙ 8 + 1∙ 4 + 0∙ 2 + 1∙ 1 = 32 + 16 + 0 + 4 + 0 + 1 = 53₍₁₀₎.

Таким образом, получаем: 110101₍₂₎ - 53₍₁₀₎.

Например: перевести из троичной системы счисления в десятичную систему счисления целое число А = 1222₍₃₎.

Решение: Запишем число (А) в виде суммы произведений степеней основания на соответствующую цифру в десятичной системе счисления:

А = 1222₍₃₎ = 1∙ 3³ + 2∙ 3² + 2∙ 3¹ + 2∙ 3⁰ = 1∙ 27 + 2∙ 9 + 2∙ 3 + 2∙ 1 = 27 + 18 + 6 + 2 = 53₍₁₀₎.

Таким образом, получаем: 1222₍₃₎- 53₍₁₀₎.

Например: перевести из пятеричной системы счисления в десятичную систему счисления целое число А = 203₍₅₎.

Решение: Запишем число (А) в виде суммы произведений степеней основания на соответствующую цифру в десятичной системе счисления:

А = 203₍₅₎ = 2∙ 5² + 0∙ 5¹ + 3∙ 5⁰ = 2∙ 25 + 0∙ 5 + 3∙ 1 = 50 + 0 + 3 = 53₍₁₀₎.

Таким образом, получаем: 203₍₅₎- 53₍₁₀₎.

Например: перевести из восьмеричной системы счисления в десятичную систему счисления целое число А = 65₍₈₎.

Решение: Запишем число (А) в виде суммы произведений степеней основания на соответствующую цифру в десятичной системе счисления:

А = 65₍₈₎ = 6∙ 8¹ + 5∙ 8⁰ = 48 + 5 = 53₍₁₀₎.

Таким образом, получаем: 65₍₈₎- 53₍₁₀₎.

Например: перевести из шестнадцатеричной системы счисления в десятичную систему счисления целое число А = 35₍₁₆₎.

Решение: Запишем число (А) в виде суммы произведений степеней основания на соответствующую цифру в десятичной системе счисления:

А = 35₍₁₆₎ = 3∙ 16¹ + 5∙ 16⁰ = 48 + 5 = 53₍₁₀₎.

Таким образом, получаем: 35₍₁₆₎- 53₍₁₀₎.

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

Например, если перевод осуществляется в восьмеричную систему счисления, то группы будут содержать три цифры (8 = 2³), такая группа называется триадой. Если перевод осуществляется в шестнадцатеричную систему счисления, то группы будут содержать четыре цифры (16 = 2⁴), такая группа называется тетрадой. В целой части числа группировка производится справа налево, в дробной части – слева направо. Если в последней группе недостает цифр, то дописываются нули: в целой части – слева, в дробной – справа. Затем каждая группа заменяется соответствующей цифрой новой системы счисления.

Например: необходимо из двоичной системы счисления перевести в восьмеричную систему счисления целое число: А = 110101₍₂₎.

Решение: исходя из вышесказанного, разобьем целое число: А = 110101₍₂₎ на триады и получим рис.2.19:

Рисунок 2.19 - Перевод целого числа А = 110101₍₂₎ в восьмеричную систему счисления

Таким образом, получаем: 110101₍₂₎ - 65₍₈₎.

Например: необходимо из двоичной системы счисления перевести в шестнадцатеричную систему счисления целое число: А = 110101₍₂₎.

Решение: исходя из вышесказанного, разобьем целое число: А = 110101₍₂₎ на тетрады и получим рис.2.20:

Рисунок 2.20 - Перевод целого числа А = 110101₍₂₎ в шестнадцатеричную систему счисления

Таким образом, получаем: 110101₍₂₎ - 35₍₁₆₎.

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

Например: необходимо из восьмеричной системы счисления перевести в шестнадцатеричную систему счисления целое число: А = 65₍₈₎.

Решение: исходя из вышесказанного, переведем сначала целое число: А = 65₍₈₎ в двоичную систему счисления, разбив его на триады, а затем триады преобразовав в тетрады получим число в шестнадцатеричной системе счисления рис.2.21:

Рисунок 2.21 - Перевод из восьмеричной системы счисления в шестнадцатеричную систему счисления целого числа А = 65₍₈₎

Таким образом, получаем: 65₍₈₎ - 35₍₁₆₎.

Например: необходимо из шестнадцатеричной системы счисления перевести в восьмеричную систему счисления целое число: А = 35₍₁₆₎.

Решение: исходя из вышесказанного, переведем сначала целое число:

А = 35₍₁₆₎ в двоичную систему счисления, разбив его на тетрады, а затем тетрады преобразовав в триады получим число в восьмеричной системе счисления рис.2.22:

Рисунок 2.22 - Перевод из шестнадцатеричной системы счисления в восьмеричную систему счисления целого числа А = 35₍₁₆₎

Таким образом, получаем: 35₍₁₆₎ - 65₍₈₎.

При переводе из десятичной системы счисления двоично-десятичную систему счисления подразумевают, что двоично-десятичная система счисления представляет собой систему с основанием (10), цифры которой закодированы в виде четырехразрядных двоичных чисел (тетрад), либо с естественным порядком весов (8-4-2-1), либо с искусственным порядком весов.

Например: необходимо из десятичной системы счисления перевести в двоично-десятичную систему счисления целое число: А = 118₍₁₀₎.

Решение: исходя из вышесказанного, при переводе целого десятичного числа: А = 118₍₁₀₎ в двоично-десятичную систему счисления, необходимо разбить его на тетрады рис. 2.23:

Рисунок 2.23 - Перевод из десятичной системы счисления в двоично-десятичную систему счисления целого числа А = 118₍₁₀₎.

Таким образом, получаем: 118₍₁₀₎ - 100011000_(2-10).

Например: необходимо из двоично-десятичной системы счисления перевести в десятичную систему счисления целое число: А = 100011000_(2-10).

Решение: исходя из вышесказанного, при переводе целого двоично-десятичного числа: А = 100011000_(2-10).в десятичную систему счисления, необходимо разбить его на тетрады рис. 2.24:

Рисунок 2.24 - Перевод из двоично-десятичной системы счисления в десятичную систему счисления целого числа А = 100011000_(2-10)

Таким образом, получаем: 100011000_(2-10) - 118₍₁₀₎

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

Например: перевести из пятеричной системы счисления в троичную систему счисления целое число А = 203₍₅₎.

Решение: Исходя из вышесказанного сначала необходимо целое число:

А = 203₍₅₎ записанное в пятеричной системы счисления, перевести в десятичную систему счисления, а затем полученное число из десятичной системы счисления перевести в троичную систему счисления.

Действие №1: А = 203₍₅₎ - 10.

А = 203₍₅₎ = 2∙ 5² + 0∙ 5¹ + 3∙ 5⁰ = 2∙ 25 + 0∙ 5 + 3∙ 1 = 50 + 0 + 3 = 53₍₁₀₎.

Действие №2: А = 53₍₁₀₎ – 3, рис.2.25:

Рисунок 2.25 - Перевод целого числа А = 53₍₁₀₎ из десятичной системы счисления в троичную систему счисления

Таким образом, получаем: 203₍₅₎ - 1222₍₃₎.

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

Пусть правильная (р^х – ичная) дробь А(р^х) уже переведена и представлена в новой системе счисления с основанием (р):

А(р^х) = а₁ ∙ р^-1 + а₂ ∙ р^-2 + а₃ ∙ р^-3 +….+ а_n ∙ р^-n. (2.26)

где а₁ - целая часть первого произведения;

А(р^х1) = а₂ ∙ р^-1 + а₃ ∙ р^-2 + ….+ а_n ∙ р^-n+1 – дробная часть первого произведения.

Умножив на (р) дробную часть А(р^х1) первого произведения, определим вторую цифру (а₂):

А(р^х1) = а₂ + а₃ ∙ р^-1 + ….+ а_n ∙ р^(-n+2). (2.27)

где а₁ - целая часть первого произведения.

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

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

Например: необходимо перевести из десятичной системы счисления в двоичную систему счисления правильную дробь А = 0.375₍₁₀₎.

Решение: исходя из вышесказанного произведем последовательное умножение А = 0.375₍₁₀₎ на новое основание системы счисления (2), рис.2.26:

Рисунок 2.26 - Перевод из десятичной системы счисления в двоичную систему счисления правильной дроби А = 0.375₍₁₀₎.

Таким образом, получаем: 0, 375₍₁₀₎ = 0, 0110₍₂₎.

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

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

Например: необходимо перевести из десятичной системы счисления в двоичную систему счисления правильную дробь А = 0.35₍₁₀₎.

Решение: исходя из вышесказанного произведем последовательное умножение А = 0.35₍₁₀₎ на новое основание системы счисления (2), рис.2.27:

Рисунок 2.27 - Перевод из десятичной системы счисления в двоичную систему счисления правильной дроби А = 0.35₍₁₀₎.

последнее произведение получилось равным (0, 40), а ранее было уже получено произведение (1, 40), следовательно считаем, что начался период.

Таким образом, получаем: 0, 35₍₁₀₎ 0, 010110₍₂₎.

Например: необходимо перевести из двоичной системы счисления в десятичную систему счисления правильную дробь А = 0.0110₍₂₎.

Решение: в этом случае для преобразования чисел необходимо воспользоваться формулой (2.6). Запишем число (А) в виде суммы произведений степеней основания на соответствующую цифру в десятичной системе счисления:

А = 0.0110₍₂₎ = 0∙ 2^-1+1∙ 2^-2+1∙ 2^-3+0∙ 2^-4 = 0∙ (1/2)+1∙ (1/4)+ 1∙ (1/8)+ 0∙ (1/16) = (1/4)+(1/8) = (2/8)+(1/8) = (3/8) = 0.375₍₁₀₎.

Таким образом, получаем: 0.0110₍₂₎ = 0.375₍₁₀₎.

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

Например: необходимо перевести из десятичной системы счисления в двоичную систему счисления неправильную дробь А = 23.125₍₁₀₎.

Решение: исходя из вышесказанного необходимо сначала перевести целую часть числа (А) путем последовательного деления на основание новой системы счисления (2) до тех пор, пока не получится частное, у которого целая часть равна (0). При этом число в новой системе счисления записывается из остатков от последовательного деления, причем последний остаток будет старшей цифрой нового числа. А затем перевести дробную часть путем последовательного умножения на основание новой системы счисления (2) до тех пор, пока в новой дроби не будет нужного количества цифр, которое определяется требуемой точностью представления дроби. Тогда дробная часть числа (А) в новой системе счисления записывается из целых частей произведений, получающихся при последовательном умножении, причем первая целая часть будет старшей цифрой новой дроби, рис.2.28:

Рисунок 2.28 - Перевод из десятичной системы счисления в двоичную систему счисления неправильной дроби А = 23.125₍₁₀₎.

Таким образом, получаем: 23.125₍₁₀₎ - 10111.001₍₂₎.

2.3 Перевод неправильной восьмеричной (шестнадцатеричной) дроби в двоичную систему счисления

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

Например: необходимо перевести из восьмеричной системы счисления в двоичную систему счисления неправильную дробь А = 273.5₍₈₎.

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

Например: необходимо перевести из шестнадцатеричной системы счисления в двоичную систему счисления неправильную дробь А = 5АЕ.18₍₁₆₎.

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

Лекция №6 (90-минут)