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

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

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

Например: =5₁₀=101₂=5₁₆.

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

Обозначим преобразование числа Z, представленного в р- ричной системе счисления в представление в q -ричной системе как Z_p→Z_q. Теоретически возможно произвести его при любых q и р. Однако подобный прямой перевод будет затруднен тем, что придется выполнять операции по правилам арифметики недесятичных систем счисления (полагая в общем случае, что p, q ≠10).

По этой причине более удобными с практической точки зрения оказываются варианты преобразования с промежуточным переводом Z_p →Z_r→ Z_q с основанием r, для которого арифметические операции выполнить легко. Такими удобными основаниями являются r=1 и r=10, т. е. перевод осуществляется через унарную или десятичную систему счисления.

Преобразование Z_p → Z ₁ → Z_q

Идея алгоритма перевода предельно проста: положим начальное значение Z_q:=0; из числа Z_p вычтем 1 по правилам вычитания системы p, т.е. Z _p:=Z _p - 1, и добавим ее к Z_q по правилам сложения системы q, т.е. Z_q:=Z_q +1. Будем повторять эту последовательность действий, пока не достигнем Z_p= 0. Правила сложения с 1 (инкремента) и вычитания 1 (декремента) могут быть записаны так, как представлено в табл. 3.1.

(Страница37)

Таблица 3.1. Правила сложения и вычитания 1

Для системы p	Для системы q
(p - 1) - 1=р - 2	0+1=1
(p - 2) - 1=p - 3	1+1=2
...	...
1 - 1=0	(q - 2)+1=q - 1
0 - 1=π(р - 1)	(q - 1)+1=π. 0

Примечание: π — перенос в случае инкремента или заем в случае декремента.

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

Преобразование Z_p →Z_w → Z_q

Очевидно, первая и вторая часть преобразования не связаны друг с другом, что дает основание рассматривать их по отдельности. Алгоритмы перевода Z_w →Z_q вытекают из следующих соображений. Многочлен (3.1) для Z_q может быть представлен в виде:

(3.2)

где m — число разрядов в записи Z _p, a b_j (j= 0,..., m-1) — цифры числа Z_q.

Разделим число Z_q на две части по разряду номер i. Число, включающее m-i разрядов с (m- i)-го по i- й, обозначим γ _{i ,} а число с i разрядами с (i -1)-го по 0-й — δ _i. Очевидно,

Позаимствуем из языка PASCAL обозначение двух операций: div — результат целочисленного деления двух целых чисел и mod — остаток от целочисленного деления (13 div 4=3; 13 mod 4=1).

(Страница38)

Теперь если принять то в (3.2) усматривается следующее рекуррентное соотношение: из которого, в свою очередь, получаются выражения:

(3.3)

Аналогично, если принять , то для правой части числа будет справедливо другое рекуррентное соотношение: из которого следуют:

(3.4)

Из соотношений (3.3) и (3.4) непосредственно вытекают два способа перевода целых чисел из десятичной системы счисления в систему с произвольным основанием q.

Способ 1 является следствием соотношений (3.3), предполагающий следующий алгоритм перевода:

1. Целочисленно разделить исходное число (Z₁₀) на основании новой системы счисления (q) и найти остаток от деления — это будет цифра 0-го разряда числа Z_q.

2. Частное от деления снова целочисленно разделить на q с выделением остатка; процедуру продолжать до тех нор, пока частное от деления не окажется меньше q.

3. Образовавшиеся остатки от деления, поставленные в порядке, обратном порядку их получения, и представляю Z_q.

Пример 3.1

Выполнить преобразование 123₁₀ → Z₅. Результат — на рис. 3.1

Рис. 3.1. Результат выполнения примера 3.1

Остатки от деления (3, 4) и результат последнего целочисленного деления (4) образуют обратный порядок цифр нового числа. Следовательно, 123₁₀=443₅.

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

Способ 2 вытекает из соотношения (3.4), действия производятся в соответствии со следующим алгоритмом:

1. Определить m-1 — максимальный показатель степени в представления числа по форме (3.1) для основания q.

2. Целочисленно разделить исходное число (Z₁₀) на основание новой системы счисления в степени m-1 (т. е. q^{m - 1}) и найти остаток от деления; результат деления определит первую цифру числа Z_q.

3. Остаток от деления целочисленно разделить на g^{m - 2}, результат деления принять за вторую цифру нового числа; найти остаток; продолжать эту последовательность действий, пока показатель степени q не достигнет значения 0.

Продемонстрируем действие алгоритма на той же задаче, что была рассмотрена выше.

Определить m- 1 можно либо путем подбора (5⁰=1<123; 5¹=5<123; 5²=25<123; 5³=125>123, следовательно, m-1=2), либо логарифмированием с оставлением целой части логарифма (log₅123=2, 99, т.е. m-1=2).

Далее:

Алгоритмы перевода Z _g →Z _W явно вытекают из представлений (3.1) или (3.2): необходимо Z_p представить в форме многочлена и выполнить все операции по правилам десятичной арифметики.

Пример 3.2

Выполнить преобразование 443₅ →Z₁₀.

Решение:

443₅=4*5²+4*5¹+3*5⁰=4*25+4*5+3*1=123₁₀.

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

По этой причине переход, например, Z ₃ → Z₈ проще осуществить через промежуточное преобразование к десятичной системе Z ₃ → Z₁₀ → Z₈. Ситуация, однако, значительно упрощается, если основания исходной и конечной систем счисления оказываются связанными соотношением p = q^r, где r— целое число (естественно, большее 1) или r=1 /n (n> 1, целое) — эти случаи будут рассмотрены далее.

Дата добавления: 2015-04-25