в методе 1, а используется операция деления на 10. В методе 2, а используется умножение на 10, так что программа, реализующая этот метод, может выполняться немного быстрее. Но, применяя метод 2, а, нужно иметь дело с дробями, а это приводит к интересной ситуации. Пусть w - размер машинного слова, и положим, что и < 10" < W. При помощи одного деления можно найти q и г, где

WU = 10"q + г, О < г < 10".

Если же применить метод 2, а к дроби (q + l)/w, то за п шагов получим разряды числа и слева направо, так как

W J

10"-г

- и.

(Эта идея предложена П. А. Саметом (Р. А. Samet) и опубликована в журнале Software Practice к Experience 1 (1971), 93-96.) Приведем соответствуюшую MIX-программу.

JOV LDA LDX DIV JOV

ENT1 п-1 2Н MOL =10=

OFLO О

=10" = =10"= ERROR

Удостовериться в отсутствии переполнения.

STA ANSWER,! SLAX 5 DECl 1 JINN 2В

гАХ-Н u)M--10". гА <- 5 -Ь 1, rX <- г. Переход при и > 10". Присвоить j <- п- 1. Представим, что разделяющая точка

находится слева, гА = х. Присвоить Uj <- [lOxJ. X {Wx}.

i<-j-i-

Повторить для п > j > 0. I

Данная программа немного длиннее предыдущей, и на ее выполнение требуется 16п + 19 цикпов, так что при п = М > 8 она вьшолняется быстрее программы (1). Однако при наличии ведщих нулей программа (1) будет выполняться быстрее.

Программа (4) в представленном виде при 10™ < w < 10"+ не может использоваться для преобразования целых чисел и > 10", так как нужно принять п = тп + 1. В этом случае ведущий разряд числа и можно получить, вычисляя [u/10"J; после этого можно преобразовать число и mod 10™ по приведенному выше методу при п = тп.

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

В методе 1, а деление на 10 можно заменить двумя умножениями. Это может оказаться существенным, поскольку преобразование оснований часто вьшолняется в компьютерах-"сателлитах", в которых отсутствует встроенная процедура деления. Если предположить, что х - приближение к так что

1 1 1

10<"<10 +

то легко доказать (см. упр. 7), что [их\ = [w/lOj или [w/lOj + 1, пока О < и < w. Поэтому при вычислении и - 10[ua:J можно определить значение [u/lOj:

[u/lOJ = [их\ -[и< 10[их\

Одновременно можно определить и mod 10. MIX-программа, выполняющая преобразование с использованием (5), приведена в упр. 8. На вычисление каждого разряда она затрачивает около 33 циклов.

Метод 1, а может быть с успехом применен и в компьютерах, в которых отсутствуют встроенные команды как деления, так и умножения, путем выполнения операций сдвига и сложения, как продемонстрировано в упр. 9.

Другой способ преобразования из двоичного представления в десятичное заключается в использовании метода 1, Ь, но при этом необходимо имитировать удвоение в десятичной системе счисления. Этот способ в общем случае наиболее подходит для аппаратной реализации в компьютере; тем не менее процесс удвоения в десятичной системе счисления можно и запрограммировать при помощи операций двоичного сложения, двоичного сдвига и двоичного извлечения или маскирования (побитовое AND), как показано в табл. 1, составленной Петером Л. Монтгомери (Peter L. Montgomery).

Таблица 1

УДВОЕНИЕ ДЕСЯТИЧНОГО ЧИСЛА, ЗАКОДИРОВАННОГО В ДВОИЧНОЙ СИСТЕМЕ

Операция

1. Задать число

2. Прибавить 3 к каждому разряду

3. Извлечь каждый старший бит

4. Сдвинуть вправо на 2 разряда и вычесть

5. Прибавить исходное число

6. Прибавить исходное число

Обилий вид

Пример

«11 UlO«9U8 U7 U6 U5 U4 U3 U2 «1 uo ООН ОНО 1001 = 369

111 110 Vg Vg V7 V6 V5 V4 V3 V2 Vl VO 0110 1001 1100

1Л1 0 0 0 17 0 0 0 13 0 0 0 0000 10001000

О1Л11Л1О 0 17 17 0 OV3V3O 000001100110

wuwiowgwg W7W6WbWi W3W2W1W0 ООП 1100 nil

X12 xiixioxgxg Х7Х6Ж5Ж4 Х3Х2Ж1Х0 001110011 1000 = 738

При помощи этого метода значение каждого разряда d заменяется на 2d при О < d < 4 и на б -f 2d = (2d - 10) -f 2 при 5 < d < 9, что и требуется для удвоения десятичных чисел, каждый разряд которых закодирован четырьмя битами.

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

и наконец, для преобразования целых чисел, представленных в двоичном формате, в целые числа, представляемые в десятичном формате, можно использовать даже метод 2, Ь. Можно найти q, как в (2), а затем имитировать операцию десятичного деления q+1 на W, используя процесс "уполовинивания" (упр. 10), аналогичный описанному выше процессу удваивания, сохраняя при этом в результате только первые п разрядов справа от разделяющей точки. Похоже, что в этом случае метод 2, b не имеет каких-либо преимуществ по сравнению с остальными тремя методами, проанализированными выше, тем не менее подтверждается высказанный выше тезис о том, что для преобразования целых чисел из одной системы счисления в другую существует четыре различных метода.

Теперь рассмотрим преобразование из десятичной системы счисления в двоичную (т. е. 6 = 10, Б = 2). Метод 1, а позволяет имитировать операцию десятичного деления на 2, что допустимо, но предпочтительнее реализовать ее аппаратно, а не программно (см. упр. 10).

В большинстве случаев наиболее удобным методом преобразования из десятичной системы счисления в двоичную является метод 1, Ь. В приводимой ниже MIX-программе принято, что число («„... uiUo)io содержит по крайней мере два разряда, подлежащих преобразованию, и неравенство Ю" < w вьшолняется так, чтобы не возникало переполнение.

ENT1 М-1 Присвоить j <- тп - 1.

LDA INPOT+M Присвоить t/<-Um-IH MOL =10=

SLAX 5 (6)

ADD INPOT ,1 и i-WU + uj. DECl 1

JINN IB Повторить При m > j > 0.

Операция умножения на 10 может быть заменена ойерациями сдвига и сложения.

В упр. 19 рассмотрен более быстрый, возможно, способ преобразования, в котором вместо тп - 1 операций умножения используется примерно Igm операций умножения, маскирования и сложения.

Для преобразования в двоичный формат десятичных дробей (О )io

можно воспользоваться методом 2, b или, в более общем случае, сначала преобразовать целое число (u iu 2... u m)io при помощи метода 1, а, а затем разделить результат на Ю™.

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

Преобразование целых чисел из восьмеричной системы счисления в десятичную. Простейши.м является преобразование из восьмеричного формата в десятичный. Этот способ, по-видимому, впервые опубликовал Уолтер Соден (Walter Soden) в Math. Сотр. 7 (1953), 273-274. Чтобы выполнить преобразование, нужно записать данное восьмеричное число, удвоить на fc-м шаге fc ведущих разрядов.