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

Рассмотрим вначале методы перевода чисел из смещенной системы счисле- ния с основанием k₁ в смещенную систему с основанием k₂ . Через будем обозначать число X в k₁-й системе.

Правая часть выражения (2) определяет правило вычисления количествен- ­ного эквивалента числа, записанного в форме (1). На этом основан один из ме­то- дов перевода чисел. Для перевода числа в систему с основанием k₂необходимо записать в форме (2); заменить цифры х_i и основание k₁их k₂-ми эквива­лен- тами, а затем вычислить выражение (2) по правилам системы счисления с осно- ванием k₂.

Пример 1. Перевести число X₍₂₎ = 1011,1001 в десятичную систему счис­ле-ния

Описанный метод перевода чисел из одной системы в другую получил наз- ва­ние метода непосредственного замещения. Этот метод удобно использовать в случае, когда k₁< k₂ и при переводе чисел в такую систему, где просто выполняя- ются операции сложения и умножения (например, из двоичной системы в десятич-ную). Для упрощения вычисления при этом можно воспользоваться таким выра- жени­ем, полученным из (2):

Однако при переводе чисел в системы с «непривычными» основаниями, осо­бенно в случае k₁> k₂ ,применение этого метода связано с довольно громозд- кими вычислениями. Поэтому во многих случаях удобнее пользоваться отдельными ме­тодами перевода целых чисел и правильных дробей.

Метод перевода целых чисел из системы с основанием k₁всистему с осно- ва­нием k₂(k₁> k₂) заключается в следующем. Число делят на k₂поправилам деления с основанием k₁до получения остатка. Если частное от деления не нуль, то частное становится делимым и процесс деления на k₂продолжают. Как толь- ко очередное частное станет равным нулю, процесс деления на k₂ прекращают. Оста­ток, полученный при первом делении на k₂ , представляет цифру разряда резуль­тата с весом , остаток от второго деления представляет цифру результата с ве­сом ,и т . д. Последний остаток является старшей цифрой результата.

Пример 2. Перевести число Х₍₁₀₎ = 1247 в пятеричную систему счисления.

В случае, когда k₁< k₂, выполняют умножение цифры с весом , числа (старшей цифры числа ) на основание k₁, после чего к произведению прибав­- ляют следующую (в порядке убывания весов) цифру числа . Результат преды­дущей операции умножают на k₁и прибавляют очередную цифру числа . Этот процесс заканчивают, когда будет прибавлена цифра с весом (младшая цифра). Все вычисления при этом выполняются в k₂-й системе счисления.

Пример 3. Перевести из двоичной системы в троичную число Х₍₂₎ = 10110110.

Перевод правильных дробей из системы счисления с основанием k₁всис- тему с основанием k₂ (k₁> k₂) осуществляется так. Дробь, соответствующая числу , умножается на k₂ по правилам умножения в системе с основанием k₁ . В по­лученном произведении отделяется целая часть, которая может быть равной ну- лю, а дробная часть снова умножается на k₂с последующим отделением целой части. Эти операции повторяют либо до получения нулевой дробной части произ- веде­ния, либо до получения необходимого количества разрядов числа в новой системе счисления. Старшая цифра результата перевода (т. е. первая после за­пятой) совпадает с первой отделенной целой частью, вторая цифра результата—со второй отделенной целой частью и т. д.

Пример 4. Перевести число Х₍₁₀₎ = 0,314 в двоичную систему счисления, ограничившись шестью разрядами после запятой.

При k₁< k₂ для перевода правильной дроби, имеющей т цифр после запя- той, необходимо разделить цифру младшего разряда числа на k₁ и сложить со сле­дующей цифрой этого числа. Такую операцию необходимо повторить еще т–1 раз, используя на каждом шаге в качестве делимого сумму, полученную на пре- ды­дущем шаге. Все операции выполняются в k₂-й системе.

Пример 5. Перевести в десятичную систему число Х₍₂₎ = 0,101101.

Перевод чисел в симметричные и кососимметричные системы счисления с ос­нованием k₂можно осуществить в три этапа. На первом этапе, используя рас- смот­ренные выше правила, осуществляется перевод чисел в смещенную систему счис­ления с основанием k₂ . На втором этапе цифры k₂-й смещенной системы, ко- торые отсутствуют в симметричной и кососимметричной системе, представляются двумя цифрами симметричной или кососимметричной системы, в которую осуще-ствляется перевод. На третьем этапе осуществляется суммирование всех допусти- мых для симметричной или кососимметричной системы цифр, полученных на пер- вом и втором этапе, с учетом их весов по правилам этих систем счисления.

Пример 6. Перевести число Х₍₁₀₎ = 1247 в пятеричную каноническую сим­метричную систему счисления.

После выполнения первого этапа (см. пример 2) получим Х_{5) = 14442. По­сколь- ку допустимыми для симметричной системы счисления являются цифры {-2, -1, 0, 1, 2}, то цифру 4 представляем двумя цифрами симметричной систе­мы следую- щим образом: 4 = . На третьем этапе осуществляем суммирование. Результат суммирования является числом 1247, представленным в пятеричной симметричной системе счисления.

Для перевода чисел из симметричных и кососимметричных систем в сме- щен­ные системы достаточно просуммировать цифры числа в исходной системе с учетом их знаков и весов.

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

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

Для преобразования нечетного положительного числа из k₁-й системы счи- сле­ния в двоичную систему с цифрами {1, } необходимо вначале перевести это число в двоичную систему с цифрами {0, 1). Затем, просматривая полученную запись слева направо, необходимо выделить все группы цифр вида 00...01, даже если они включают один нуль. Эти группы необходимо заменить на группы вида . Остальные цифры 1 остаются без изменения. При преобразовании нечетных от-рицательных чисел группы цифр 00...01 необходимо заменить на группы 1...11, остальные цифры 1 заменить на .

Пример 8. Перевести число X₍₁₀₎= 0,314 в двоичную систему с цифрами (1, }. Используя результат примера 4, получим:

X₍₂₎= 0,0101000001; = 0,1 1 1 .

Обратный перевод выполняется так же, как и перевод из симметричных систем в смещенные.

Методы перевода чисел из систем с основанием 2^r в двоичную систему и наобо­рот очень просты, чем и объясняется широкое использование этих систем для ввода и вывода информации в ЭВМ. Для перевода числа из системы счисления с основанием 2^r в двоичную систему необходимо представить каждую цифру систе­- мы с основанием 2^r посредством r двоичных разрядов.

Пример 9. Перевести числа X₍₈₎ = 762,15 и Y₍₁₆₎ = Е51А,7D в двоичную сис-тему счисления.

X₍₂₎ = 111110010,001101 ; Y₍₂₎ =1110010100011010,01111101 .

Для перевода двоичного числа в систему счисления с основанием 2^r необхо­димо, двигаясь от запятой влево и вправо, разбить двоичное число на группы, со- держащие no r разрядов, дополняя при необходимости нулями крайние левую и правую группы. Затем каждую группу из r двоичных разрядов необходимо заме­- нить цифрой системы счисления с основанием 2^r.

Пример 10.Перевести число Х_{2) = 11111101, 1000001 в шестнадцатирич- ную систему счисления

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

В позиционных системах с отрицательным основанием k < –1 представле­ние любого рационального числа имеет вид

где x_i – цифры i-го разряда. Отсюда следует, что веса отдельных разрядов в таких системах образуют ряд

На этом основан один из методов перевода чисел из системы с основанием k₁в систему с отрицательным основанием k₂< -1. Сначала число переводят в си­с- тему с положительным основанием k₂ . Затем число разделяют на два числа А и B. При положительном числе разряды числа А с четным i (в том числе и i = 0) равны разрядам числа с таким же i, а разряды числа А с нечетным i равны нулю.

Разряды числа В с четным i равны нулю, а в разрядах с нечетным i каждая не равная нулю цифра заменяется единицей в i +1-м разряде и цифрой |k| - x_i. После этого необходимо выполнить суммирование чисел A и В с учетом того, что переносы из разрядов с четным i имеют знак «+», а из разрядов с нечетным i – знак «–». Перенос из последнего (n-го) разряда чисел А и В заменяется цифрами 1 и |k|– 1 соответственно в п + 2-м и п + 1-м разрядах.

Если же число отрицательное, то разряды числа А с четным i при заменяются единицей в i+1-м разряде и цифрой |k| –x_i в i-м разряде. Нечет­- ные разряды числа А равны нулю. Разряды числа В с четным i равны нулю, а раз- ­ряды с нечетным i равны i-м разрядам числа .Суммирование чисел также должно осуществляться с учетом знаков переносов.

Пример 11. Перевести числа X₍₁₀₎ = 30,75 и Y₍₁₀₎ = – 23,5 в систему с ос­но- ванием k₂= – 2. В системе с основанием 2 указанные числа будут представ­лены как X₍₂₎ = 11110,11 и Y₍₂₎= – 10111,1.

1 1 1 1 0 , 1 1 1 0 1 1 1 , 1

Таким образом, X_(-2) = 1100011,11; Y_(-2) = 111001,1.

Для перевода числа в систему с положительным основанием k₂ , необхо­димо также разделить на два числа А и B. При этом четные разряды числа А равны четным разрядам , нечетные разряды числа А равны нулю. Число В имеет в нечетных разрядах те же цифры, что и число в нечет­ных разрядах. Четные разряды В равны нулю. Далее, из А следует вычесть В, если положительное, или же из В вычесть А, если отрицатель­ное. Знак определяется знаком веса старшего разряда.

Пример 12. Перевести в систему с положительным основанием числа X_(-2) = 10100,1101 и Y_(-2) = 101101,10101. Первое из этих чисел положительное, так как его старший разряд имеет вес 2⁴, а второе число отрицательное – вес его стар- ­шего разряда равен 2⁵.

Другие методы перевода чисел всистемы с отрицательным k основаны на пос­ледовательном делении целого числа на основание ина последовательном ум- ноже­нии дробей на основание. Припереводе целых чисел все остатки от деления и припереводе дробей целые части получаемых произведений должны быть по- ложитель­ными, меньшими k. Для выполненияэтих требований при переводе дро- бей дробная часть D, используемая на каждом шаге перевода, должна удовлетво- рять условию

Перевод чисел из позиционной системы в СОК в простейшем случае вы- полня­ется путем деления числа X на модули Р_i (i = ). Наименьшие положи- тельные остатки от такого деления и образуют представление X в СОК. Однако такой ме­тод перевода часто оказывается малоэффективным из-за большого числа операций деления.

Другие методы перевода из позиционных систем в СОК основаны на ис- пользо­вании следующих свойств чисел, представленных остатками:

rest (A+B) (mod P_i) = (rest A (mod P_i) + rest B (mod P_i)) (mod P_i) ,

rest AB (mod P_i) = (rest A (mod P_i) x rest B (mod P_i)) (mod P_i) . (4)

Пусть для заданного набора модулей Р_i (i = )и позиционной k-ичной системы известны представления в остатках любой степени основания

k ^j = ( k_{1 j} , k_{2 j} , … , k_{m j} ) , ( j = ) ,

а также любой k-ичной цифры

x_j = ( x_{1 j} , x_{2 j} , … , x_{m j} ) , ( j = ) .

Тогда

X_i = rest X (mod P_i) = rest (mod P_i) =

= (rest x_j (mod P_i) rest k ^j (mod P_i)) (mod P_i) = (x_{i j} k _{i j} (mod P_i)) (mod P_i) .

Таким образом, для нахождения остатка числа X по модулю P_i , необходи- мо сложить попарные произведения остатков цифр x_j и весов k ^j. При этом все сложе­ния и умножения выполняются по модулю P_i.

Рассмотренный метод перевода применяется и в другом варианте, исполь- зующем не только свойства (4), но и следующее свойство:

rest AB (mod P_i) = (A rest B (mod P_i)) (mod P_i) .

В этом случае для вычисления Х_i достаточно иметь представление в остат- ках либо только степеней основания k^j, либо только цифр х_j, т.е.

X_i = (x _j k _{i j} (mod P_i)) (mod P_i) = (x_{i j} k ^j (mod P_i)) (mod P_i) . (5)

Пример 13. Перевести число X₍₁₀₎= 839 в СОК с модулями Р₁= 3, Р₂ = 5, Р₃= 7, P₄=11. Для степеней основания и заданных цифр позиционной десятич- ­ной системы имеем

10²= (1, 0, 2, 1); 8 = (2, 3, 1, 8);

10¹=(1, 0, 3, 10); 3 = (0, 3, 3, 3);

10⁰= (1, 1, 1, 1); 9 = (0, 4, 2, 9).

Далее находим остатки X_i :

Х₁= (1ּ2 +1ּ0 +1ּ0) (mod 3) = 2;

X₂ = (0ּ3 + 0ּ3 + 1ּ 4) (mod 5) = 4;

Х₃= (2ּ1 + 3ּ3 +1ּ2) (mod 7) = 6;

Х₄= (1ּ8 +10ּ3 +1ּ9) (mod 11) = 3.

Следовательно, X = (2, 4, 6, 3). Такой же результат получается и при ис- пользовании формул (5).

Наиболее простой и естественный путь перевода чисел из СОК в позици- онную систему, состоящий в решении системы уравнений вида

X = l₁ P₁ + X₁ ; X = l₂ P₂ + X₂ , … ; X = l_i P_i + X_i ,

на практике не может быть использован, так так число неизвестных X, l₁, l₂ , … , l_m здесь больше числа уравнений и, следовательно, система уравне­ний имеет беско- нечное множество решений. Поэтому для этих целей используются более сложные методы, обеспечивающие однозначность перевода.

Метод ортогональных базисов основан на использовании констант (ортого­нальных базисов) В₁ , В₂ , … , В_m , представление которых в СОК при заданном на­боре модулей P_i (i = ) имеет вид

В₁ = (1, 0, 0, … , 0);

В₂ = (0, 1, 0, … , 0);

…………………...;

В_m = (0, 0, 0, … , 1).

Представление числа X в позиционной k-ичной системе в этом случае мо- жет быть получено следующим образом:

где . Для фиксированного набора модулей Р_i k-ичные представления констант B_i(k) могут быть вычислены заранее по формуле

B_i(k) = .

Здесь — вес i-го ортогонального базиса, выбираемый из условия

rest (mod P_i) = 1 .

Пример 14. Перевести в десятичную систему число X = (2, 3, 4, 5), пред­ставленное в СОК с основаниями Р₁= 3, Р₂ = 5, Р₃ = 7, Р₄ = 11. В этом случае N = 3ּ5ּ7ּ11 = 1155; = 1, = 1, = 2, = 2; В₁= 385, B₂= 231, B₃ = 330, B₄ = 210. Следовательно,

X₍₁₀₎ = 2ּ385 + 3ּ231 + 4ּ330 + 5ּ210 (mod 1155) = 3833 (mod 1155) = 368 .

Кроме метода ортогональных базисов для перевода чисел из СОК в пози- цион­ную систему используются также методы, основанные на промежуточном представ­лении числа в полиадической системе счисления. В такой системе при за-данном наборе модулей P_i (i = )вес q_i каждого i-горазряда равен q_i-1P_i ,a q_o=1. Поэтому представление числа X в полиадической системе имеет вид

,

где b_i — цифры полиадической системы. При переводе из СОК b₀= Х₁ ,а осталь- ные цифры b_i вычисляются по формулам

b_i = rest a_i (mod P_i+1) ,

,

.

Здесь – цифра b_{i -1} ,представленная остатками по всем основаниям, номер которых выше номера i–1; – так называемая формальная обратная величина модуля P_i по основаниям Р_j ; (i ≠ j). Остатки , которыми в СОК пред­ставляется формальная обратная величина P_i , выбираются из условия

rest P_i (mod Р_j) = 1 .

Пример 15. Перевести из СОК с основаниями Р₁= 5, Р₂ = 9, Р₃= 11 в де­сятичную систему число X = (3, 6, 10). Перед вычислением цифр b_i полиадичес- кой системы найдем формальные обратные величины модулей Р_ij . Из условий

rest 5P₁₂ (mod 9) = 1; rest 9P₂₁ (mod 5) = 1;

rest 5P₁₃ (mod 11) = 1; rest 9P₂₃ (mod 11) = 1

следует Р₁₂ = 2, P₁₃= 9; Р₂₁ = 6, Р₂₃= 5. Кроме того, b₀= 3, = (3, 6, 10); = (3, 3, 3); = (0, 2, 9) .

Следовательно, а_1(С0К) = ((3, 6, 10) - (3, 3, 3)) (0, 2, 9) = (0, 3, 7) (0, 2, 9) = (0,6, 8),

b₁ = rest a₁ (mod 9) = 6;

а_2(С0К) = ((0, 6, 8) - (0, 6, 6)) (6, 0, 5) = (0, 0, 2) (6, 0, 5) = (0,0, 10),

b₂ = rest a₂ (mod 11) = 10 .

Таким образом, X₍₁₀₎ = b₀ + b₁P₁ + b₂ P₁ P₂ = 3 + 6ּ5 + 10ּ5ּ9 = 483 .