Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 98
Текст из файла (страница 98)
существует вазможность выполнять преобразовании целых чисел в дробные и наоборот путем умножения или деления на соответствующую степень Ь или В. Поэтому для выполнения преобразования имеется на выбор па крайней мере четыре метода. В. Преобразование с однократной точностью. Чтобы проиллюстрировать эти методы, предположим, что И1Х - — двоичный компьютер и нужно преобразовать неотрицательное целое число и., представленное в двоичном формате, в десятичный фарг«ат, т.
е. получить Ь = 2 и В = 10. Метод 1, а можно запрограммировать следующим образом. ЕЯТ1 0 Присвоить Х «- О. ЬОХ О ЕИТА 0 Присвоить гАХ « — и. 1Н 01Ч =10 (гА,гХ) «- (~гАХ/10), гАХ шо«1 10). НТХ ЛИВНЕВ,1 Ц «- гХ 1ИС1 1 Х «-/+1. НИАХ б гЛХ « — гЛ. ЗХР 1В Повторять до тех пор, пока в результате не получим нуль. $ Для вычисления М разрядов необходима затратить 1861 + 4 циклов. В методе 1, а используется операция деления на 10. В методе 2, а используется умнолсение на 10, так что программа, реализующая этот метод, может выполняться немного быстрее.
Но, применяя метод 2, а, нужно иметь дело с дробями, а это приводит к интересной ситуации. Пусть ю — размер машинного слова, и положим, что и < 10" < ю. При помощи одного деления можно найти 9 н г, где юи =10"д+г, О < г< 10". (2) Если же применить метод 2, а к дроби (в + 1)/ю, то за и шагов получим разряды числа и слева направо, так как (3) (Эта идея предложена П. А. Саметом (Р. А. Башес) и опубликована в журнале Войв аге Ргасбсе Хх Ехрепепсе 1 (1971), 93-96.) Приведем соответствующую И1Х-программу.
30т' 1ОА ЬОХ 017 ЮОУ ЕИТ1 2Н ИШ. Здостовериться в отсутствия переполнения. Ог 1.0 О 1 ОВ =10"= НЕВОК п-1 10= тАХ < — ни+ 10", тА+- д+ 1, гХ+-г. Переход при к > 10". Присвоить У с- и — 1. Представим, что разделюощая точка находится слева, гА = х. Присвоить Ц т- (10х). х ~- (10х). У +- У вЂ” 1. Повторить для п > у > О.
$ (4) ЯТА АНТЕК,1 ЗЕАХ Ь ОЕС1 1 31ИИ 2В 1 1 1 — <х< — + —, 10 10 ю' Данная программа немного длиннее предылущей, и иа ее выполнение требуется 16п + 19 циклов, так что при и = ЛХ > 8 она выполняется быстрее программы (1). Однако при наличии ведущих нулей программа (1) будет выполняться быстрее. Программа (4) в представленном виде при 10 < ю < 10в+' не может использоваться для преобразования целых чисел и > 10"', так как нужно принять п = гп+ 1. В этом случае ведущий разряд числа в можно получить, вычисляя (и/10™) „после этого можно преобразовать число и щи 10"' по приведенному выше методу при и = гп. То обстоятельство, что разряды результата могут быть получены слева направо.
может оказаты:я полезным в некоторых приложениях (например, прн последовательном выводе разрядов результата на печать). Итак, метод, применимый для дробей, можно использовать и для преобразований целых чисел, хотя, применив неточное деление при преобразованиях, придется выполнять численный анализ метода, В методе 1, а деление на 10 можно заменить двумя умножениями. Это может оказаться существенным, поскольку преобразование оснований часто выполняется в компьютерах-"сателлитах", в которых отсутствует встроенная процедура деления. Если предположить, что х — приближение к —,'„, так что то легко доказать (см, упр. 7), что 1их) = '1и~10) или 1и/10) + 1, пока О < и < зе. Поэтому при вычислении и — 10(их) можно определить значение (и7'10): (и~10) = (их) — '(и < 10(их)).
Одновременно можно определить и шоз( 10. И1Х-программа, выполняющая преобразование с использованием (5), приведена в упр. 8. На вычисление калсдого разряда она затрачивает около 33 циклов. Метод 1, а может быль с успехом применен и в компьютерах, в которых отсутствуют встроенные команды как деления, так и умножения, путем выполнения операций сдвига и сложения, как продемонстрировано в упр. 9. Другой способ преобразования из двоичного представления в десятичное заключается в использовании метода 1, Ь, но при этом необходимо имитировать удвоение в деслизичнвй системе счисления.
Этот способ в общем случае наиболее подходит для аппаратной реализации в компьютере; тем не менее процесс удвоения в десятичной системе счисления можно и запрограммировать при помощи операций двоичного сложения, двоичного сдвига и двоичного извлечения или маскирования (побитовое айО), как показано в табл. 1, составленной Петером Л.
Монтгомери (Ревет 1. Моиз; бощегу). Таблица 1 УДВОЕНИЕ ДЕСЯТИЧНОГО ЧИСЛА, ЗАКОДИРОВАННОГО В ДВОИЧНОВ СИСТЕМЕ Пример Общий вид иззизоеоиз изивизщ изизизио 00110ПО1001 = 309 0110 1001 1100 езз еш ео ез ез ев ев ев ез ез ез ео 0000 1000 1000 еп О ОО,ООО ООО ОООО 0110 О! 10 О еп епО 0 из из О О из из 0 0011 1100 1111 шп шзозоошз зоззевзевзов звзшззо! ич При помощи этого метода значение каждого разряда д заменяется на 2д при О < д < 4 и на б+ 2д = (2д — 10) + 24 при 5 < д < 9 что и требуется для удвоения десятичных чисел, каждый разряд которых закодирован четырьмя битами. Другая идея состоит в том, чтобы хранить таблицу степеней двоек в десятичном формате и складывать соответствующие степени, имитируя операции десятичного сложения, В разделе 7.1 описываются приемы оперирования битами. Оиврвиил 1.
Задать число 2. Прибавить 3 к каисдому Разр"ду 3. Извлечь каждый старший бит 4. Сдвинуть вправо на 2 разряда и вычесть Ь. Прибавить исходное число б. Прибавить исходное число хм хпхзохохв хгхвхзхв хзхзхзхо 0011100111000= 738 И наконец, для преобразования целых чисел, представленных в двоичном формате, в целые числа, представляемые в десятичном формате, можно использовать даже метод 2, Ь. Можно найти о, как в (2), а затем имитировать операцию десятичного деления о+1 иа ш, используя процесс "уполовипивапия" (упр.
10), аналогичный описанному выше процессу удваиваиия, сохраняя при этом в результате только первые и разрядов справа от разделяющей точки. Похоже, что в этом случае метод 2, Ь ие имеет каких-либо преимуществ по сравнению с огульными тремя методами, проаиализированпыми выше, тем ие менее подтверждается высказанный выше тезис о том, что для преобразования целых чисел из одной системы счисления в другую существует четыре различных метода. Теперь рассмотрим преобразование из десятичной системы счисления в двоичную (т. е.
Ь = 10, В = 2), Метод 1, а позволяет имитировать операцию десятичного деления иа 2, что допустимо, ио предпочтительнее реализовать ее аппаратно, а ие программно (см. упр. 10). В большинстве случаев наиболее удобным методом преобразования из десятичной системы счисления в двоичную является метод 1, Ь.
В приводимой ниже М1Х-программе принято, что число (и ...игае)~е содержит по крайней мере два разряда, подлежащих преобразованию, и неравенство 10 +~ < ю выполняется так, чтобы ие возникало переполнение. ЕМТ1 М-1 Присвоить У ~- т — 1. ЫА 1МРОТ+М Присвоить У ~ — и 1Н КЛ. 10~ БЕЯХ б (6) 400 1МРОТ, 1 У <- 10о'+ ит. ОЕС1 1 ,11ММ 1В Повторить при гл > У > О. $ Операция умножения иа 10 может быть заменена операциями сдвига и сложения.
В упр. 19 рассмотрен более быстрый, возможно, способ преобразования, в котором вместо ш — 1 операций умножения используется примерно !Мт операций умпожеиия. маскирования и глажения. Для преобразования в двоичный формат десятичных дробей (О.и эи э... и м) ш можно воспользоваться методом 2, Ь или, в более общем случае, сначала преобразовать целое число (и эи э...
и,„)ц~ при помощи метода 1, а, а затем разделить результат иа 10"'. С. Вычисления вручную, Иногда в процессе программирования возникает необходимость выполнить преобразование чисел вручную, а поскольку в обычных школах этому пока что яе учат, имеет смысл кратко обсудить здесь этот вопрос. Известны простые методы преобразования чисел из десятичного формата в восьмеричный и обратно, выполняемые вручную; этим методаи легко научиться, так что оии должны стать известными более широко. Преобразование целых чисел из восьмеричной системы счисления в десятичную. Простейшим явлчется преобразование из восьмеричного формата в десятичный.
Этот способ, по-видимому, впервые опубликовал Уолтер Содеи (%аКег Яобеп) в Ма~й. Сошр. 7 (1953), 273-274. Чтобы выполнить преобразование, нужно записать данное восьмеричное число, удвоить на Й-м шаге й ведущих разрядов, используя десятичную арифметику, и вычесть полученный результат нз (Й+ 1) ведущих разрядов при помощи опять же десятичной арифметики. Если запанное число содержит (го+ 1) разрядов, то процесс прекращается через гл шагов. Удачной оказалась идея ввода разделяющей точки для того, чтобы выделить удваиваемые разряды, как показано в следующем примере.
Это помогает исключить возможные ошибки. Пример 1. Преобразовать число (О85181 )е в десятичный формат. 5.385181 — 1 0 4 З,Я 5 1 Я 1 86 346.5181 692 2 7 ? 3.1 Я 1 5546 22185.81 44370 1 7 7 4 8 2.1 3 5 4 9 6 4 Рвврльзпапзз (1419857)зо 1419857 Достаточно надежный способ проверки вычислений состоит в "выбрасывании девяток": сумма разрядов десятичного числа должна быть конгрузнтной по модулю 9 попеременно сумме и разности разрядов числа, представленного в восьмеричном формате, причем крайний справа разряд последнего числа берется со знаком "плюс". В вышеприведенном примере имеем 1+ 4+ 1+ 9+ 8+ 5+ 7 = 35 и 1 — 2+ 1 — 5+ 2 — 3+ 5 = -1; разность равна 36 (кратна 9). Если проверка дала отрицательный результат, то она повторяется с (Й + 1) ведущими разрядами после й-го шага н местоположение ошибки определяется прн помощи процедуры двоичного поиска.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
