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

В ряде случаев числа, заданные в системе счисления с основанием Р, приходится изображать с помощью "цифр другой системы счисления с основанием Q, где Q<P. Такая ситуация возникает, например, когда в ЭВМ, способной непосредственно воспринимать только двоичные числа, необходимо изобразить десятичные числа, с которыми мы привыкли работать. В этих случаях используются смешанные системы счисления, в которых каждый коэффициент Р- ичного разложения числа записывается в £>-ичной системе. В такой системе Р называется старшим основанием, a Q — младшим основанием, а сама смешанная система называется (Q - Р)-ичной. Для того чтобы запись числа в смешанной системе счисления была однозначной, для представления любой Р-ичной цифры отводится одно и то же количество £?-ичных разрядов, достаточное для предс тавления любого базисного числа Р-ичной системы. Так, в сме шанной двоично-десятичной системе счисления для изображения каждой десятичной цифры отводится четыре двоичных разряда., Например, десятичное число х = 925 в двоично-десятичной системе запишется в виде 1001 0010 0101. Здесь последовательные четверки (тетрады) двоичных разрядов изображают цифры 9, 2, 5 записи числа в десятичной системе счисления. Следует обратить внимание, что хотя в двоично-десятичной записи числа и используются только цифры 0 и 1, эта запись отличается от двоичного изображения данного числа. Например, приведенный выше двоичный код в двоичной системе счисления изображает число 2341, а не число 925.

Условимся изображать принадлежность числа к (Q — /*)-ичной системе счисления с помощью нижнего индекса (Q - Р) при данном числе, например: 925ю= 100i00100101₂_m.

Аналогично рассмотренной выше двоично-десятичной системе можно использовать и другие смешанные системы при различных значениях Р и Q. Особого внимания заслуживает случай, когда Р = Q ', где / — целое положительное число. В этом случае запись какого-либо числа в смешанной системе тождественно совпадает с изображением этого числа в системе счисления с основанием Q (что не имеет места в двоично-десятичной системе в общем случае).

Докажем это утверждение. Рассмотрим произвольное целое число N. В Р-ичной системе счисления это число будет записано в виде

Как видно, эта запись тождественно совпадает с приведенной выше записью числа N в смешанной системе счисления, где каждая очередная группа из / цифр является просто изображением соответствующего коэффициента p_f в системе счисления с осно ванием Q.

Все сказанное выше относительно целых чисел автоматически переносится и на случай произвольных чисел. Таким образом, изображение числа х в Р-ичной системе счисления в случае Р - Q является просто сокращенной записью изображения этого же числа х

в g-ичной системе.

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

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

3.3,5. ПЕРЕВОД ЧИСЕЛ ИЗ ОДНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДРУГУЮ

При решении задач с помощью ЭВМ исходные данные обычно задаются в десятичной системе счисления; в этой же системе, как правило, нужно получить и окончательные результаты. Так как в современных ЭВМ данные кодируются в основном в двоичных кодах, то, в частности, возникает необходимость перевода чисел из десятичной в двоичную систему счисления и наоборот.

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

Задача перевода заключается в следующем. Пусть известна запись числа х в системе счисления с каким-либо основанием Р:

где pi — цифры r-ичной системы (0 <p_f < r~\). Требуется найти запись этого же числа х в системе счисления с другим основанием Q:

где q_t —искомые цифры 0-ичнои системы (0 < q, < Q - 1). При этом можно ограничиться случаем положительных чисел, так как перевод любого числа сводится к переводу его модуля и приписыванию числу нужного знака.

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

Перевод Q—>P. Задача перевода произвольного числа х, задан ного в системе счисления с основанием Q, в систему счисления с основанием Р сводится к вычислению полинома вида

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

Пример 1. Перевести число х ~ 371_В в десятичную систему счисления, пользуясь

правилами десятичной арифметики.

Для перевода запишем число х в виде х = 3*8² н- 7*8' + 1 и выполним все необходимые действия в десятичной системе:

х = 3x64 +7x8+ 1 = 192 + 56+1 =249.

Пример 2. Перевести число *=af4_!6 в десятичную систему счисления, пользуясь

правилами десятичной арифметики.

Для перевода запишем число х в видел = 10х1б' + 15x16° + 4^х! б"¹ и выполним все необходимые действия в десятичной системе:

х =10x16+ 15 + 4/16=160+15+0.25=175.25.

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

Перевод Р — > Q. Так как для перевода любого числа достаточно уметь переводить его целую и дробную части, рассмотрим отдельно эти два случая.

1. Перевод целых чисел. Пусть известна запись целого числа./V в системе счисления с основанием Р и требуется перевести это число в систему счисления с основанием Q. Так как N— целое, то его запись в (9-ичной системе счисления имеет вид

N=q«q_x._l...qiq_0?

где q, - искомые цифры £?-ичной системы (0 < #, ^ £? - 1). Для опреде ления #о разделим обе части равенства:

N=q_xQ⁴ + q.,.&-¹ +...+ q_}Q^]+q₀ (3.12)

на число Q, причем в левой части произведем деление, пользуясь правилами Р-ичной арифметики (так как запись числа./V в Р-ичной системе счисления известна), а правую часть перепишем в виде

WQ = qff¹ + q^O* +...+ qi+qo/Q.
3-514 65

Приравнивая между собой полученные целые и дробные части (учитывая, что q,<Q}'.

[WQ] = q*0'^l + q^ff~² + -+q>,

[N/Q] = q,IQ.

Таким образом, младший коэффициент q_Q в разложении (3.12) определяется соотношением

q*=Q[NIQl

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

N_} = [N/Q] = q_xff'¹ + g,,__}ff-² +...+ <?,.

Тогда N\ будет целым числом и к нему можно применить ту же самую процедуру для определения следующего коэффициента q\ и т!д.

Таким образом, при условии что N₀ = N, перевод чисел с исполь зованием.Р-ичной арифметики осуществляется по следующим рекур рентным формулам:

<a=Q№/gi, (3.13)

N_m = [Ni/Q\ (/ = 0,1,2,....)-Этот процесс продолжается до тех пор, пока не будет получено

Ai,,=0.

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

счисления с основанием Р, то в этой же системе будут получены

искомые коэффициенты <?,, поэтому их необходимо записать одной Q-

ичной цифрой.

Пример 3. Перевести число Л'= 47 в двоичную систему с использованием деся тичной арифметики. Применяя формулы (3.13) при Q = 2, имеем:

47:2 = 23(1); 23:2=11(1); 11:2 = 5(1);

5:2 = 2(1); 2:2 = 1(0); 1:2 = 0(1).

Поскольку числа нуль и единица в обеих системах счисления обозначаются одинаковыми цифрами 0 и 1, то в процессе деления сразу получим двоичные изображения искомых цифр:

N = 1011П₂.

Пример 4. Перевести число N = 3060 в шестнадцатеричную систему с исполь зованием десятичной арифметики. Применяя формулы (3.10) при Q - 16, получим

3060:16=191(4); 191:16=11(15); 11:16 = 0(11). 66

Отсюда

до = 4; 4т = 15 = f; (J₂ = И = Ь, т.е. N= bf4_l6.

2. Перевод дробных чисел. Пусть необходимо перевести в Q- ичную систему счисления правильную дробь х (0 < х < 1), заданную в Р-ичной системе счисления.

Так как х < 1, то число х в £>-ичной системе счисления можно представить в виде полинома

x~q-_lff^l+q-2ff²+...+ q*ff^m+.~, (3.14)

где q.i (i = 1, 2,...) — искомые коэффициенты £-ичного разложения числа х. Для определения q.\ умножим обе части равенства (3.14) на число Q, причем в левой части произведем умножение, пользуясь правилами Р-ичной арифметики (так как запись числа JE в Р-ичной системе счисления известна), а правую часть перепишем в виде

xQ = q.i +q-2Q^rl+q-*Q-^m+ *+....'

Приравняем между собой полученные в правой части этого выражения целые и дробные части (учитывая, что 0 < q_t < Q):

[xQ] = 3-i,

ш=<&&+..-+g™g^m*+-

Таким образом, младший коэффициент q._{ в разложении (3.14) определяется соотношением

q-\ = [xiQ\. Положим

Тогда х\ будет правильной дробью и к этому числу можно применить ту же самую процедуру для определения следующего коэффициента q.i и т.д.

Таким образом, при условии, что х₀ = х, перевод дроби с исполь зованием Р-ичной арифметики осуществляется по следующим рекур рентным формулам:

1ЧН-1) = №i/b (/' = 0,1,2,...).

(3-15)

Этот процесс продолжается до тех пор, пока не будет получено x_i+i = 0 или не будет достигнута требуемая точность изображения числа.

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

Если единица младшего разряда числа л;, заданного в Р-ичной системе счисления, есть Р~, то в его g-ичной записи следует сохранить / разрядов после запятой, где / удовлетворяет условию

gi >p-^k!2>Q-^(l+l\

округляя последнюю оставляемую цифру обычным способом.

Пример 5. Перевести число х = 0.2 в двоичную систему счисления с использованием средств десятичной арифметики. Применение формул (3.15) при водит к такой последовательности действий:

0.2x2 = 0.4 = 0 + 0.4 =>?_, =0

0.4x2-0.8=0 + 0.8 =>?_₂=0

0.8x2=1.6=1+0.6 =><?_₃ = 1

0.6x2=1.2 = 1 +0.2 =>9-< =1 ит.д.

Если десятичную дробь х = 0.2 считать точным числом, то в результате перевода в двоичную систему счисления получим периодическую дробь х = О.(ООП) (в скобках указан период дроби).