AOP_Tom2 (1021737), страница 99
Текст из файла (страница 99)
В разделе 7.1 описываются приемы оперирования битами. Операция 1. Задать число 2. Прибавить 3 к каждому РВЭРЯЛУ 3. Извлечь каждый старший бит 4. Сдвинуть вправо иа 2 разряда и вычесть 5. Прибавить исходное числа 6. Прибавить исеодиае число хм хп х19 хв хв хт хе хз х4 хз хз х1 хе 0 0111 0011 1000 = 73 8 Присвоить У < — т — 1.
Присвоить 11 < — и,. М-1 1ИРВТ+М =10= 5 1ИРВТ, 1 1 1В ЕИТ1 ЫА 1Н МШ. БЕАХ А00 ВЕС1 ЛИИ (б) 11 +- 1011+ и,. Повторить при т ) У > О, 1 Операция умножения на 10 может быть заменена операциями сдвига и сложения. В упр. 19 рассмотрен более быстрый, возможно, способ преобразования, в котором вместо т — 1 операций умножения используется примерно 1кт операций умножения, маскирования и сложения.
Для преобразования в двоичный формат десятичных дробей (О.и ги-э . и-~~)го можно воспользоваться методом 2, Ь или, в более общем случае, сначала преобразовать целое число (и ~и т... и )ш при помощи метода 1, а, а затем разделить результат на 10 С. Вычисления вручную. Иногда в процессе программирования возникает необходимость выполнить преобразование чисел вручную, а поскольку в обычных школах этому пока что не учат, имеет смысл кратко обсудить здесь этот вопрос. Известны простые методы преобразования чисел из десятичного формата в восьмеричный и обратно, выполняемые вручную; этим методам легко научиться, так что они должны стать известными более широко. Преобразование целых чисел нз восьмеричной системы счисления в десятичную.
Простейшим является преобразование из восьмеричного формата в десятичный, Этот способ, по-видимому, впервые опубликовал Уолтер Соден (Туа!1ег Боден) в Май. Сошр. 7 (1953), 273 — 274. Чтобы выполнить преобразование, нужно записать данное восьмеричное число, удвоить на й-м шаге й ведущих разрядов, И наконец, для преобразования целых чисел, представленных в двоичном формате, в целые числа, представляемые в десятичном формате, можно использовать даже метод 2, Ь. Можно найти о, как в (2), а затем имитировать операцию десятичного деления д-ь1 наш, используя процесс "уполовинивания" (упр.
10), аналогичный описанному выше процессу удваивания, сохраняя при этом в результате только первые и разрядов справа от разделяющей точки. Похоже, что в этом случае метод 2, Ь не имеет каких-либо преимуществ по сравнению с остальными тремя методами, проанэлизированными выше, тем не менее подтверждается высказанный выше тезис о том, что для преобразования целых чисел из одной системы счисления в другую существует четыре различных метода.
Теперь рассмотрим преобразование из десятичной системы счисления в двоичную (т. е, 6 = 10, В = 2). Метод 1, а позволяет имитировать операцию десятичного деления на 2, что допустимо, но предпочтительнее реализовать ее аппаратно, а не программно (см. упр. 10). В большинстве случаев наиболее удобным методом преобразования из десятичной системы счисления в двоичную является метод 1, Ь. В приводимой ниже М1Х-программе принято, что число (и, ...и~ив)~э содержит по крайней мере два разряда, подлежащих преобразованию, и неравенство 10 +' < ю выполняется так, чтобы не возникало переполнение. используя десятичную арифметику, и вычесть полученный результат из (й + 1) ведущих разрядов при помощи опять же десятичной арифметики.
Если заданное число содержит (гп+ 1) разрядов, то процесс прекращается через гп шагов. Удачной оказалась идея ввода разделяющей точки для того, чтобы выделить удваиваемые Разряды, как показано в следующем примере. Это помогает исключить возможные ошибки. Пример 1. Преобразовать число (5385181)э в десятичный формат. 5.985181 — 1 О 43.85181 — 8 6 346.5181 — 692 2773181 — 5546 2218581 — 44370 177482.1 — 354964 Реэульэпапи (1419857) ьо 1419857 Достаточно надежный способ проверки вычислений состоит в "выбрасывании девяток": сумма разрядов десятичного числа должна быть конгруэнтной по модулю 9 попеременно сумме и разности разрядов числа, представленного в восьмеричном формате, причем крайний справа разряд последнего числа берется со знаком "плюс". В вышеприведенном примере имеем 1+ 4+ 1+ 9+ 8+ 5+ 7 = 35 и 1 — 2+ 1 — 5+ 2 — 3+ 5 = — 1; разность равна 36 (кратна 9).
Если проверка дала отрицательный результат, то она повторяется с (к + 1) ведущими Разрядами после к-го шага и местоположение ошибки определяется при помощи процедуры двоичного поиска. Другими словами, можно определить, где произошла ошибка, начав с проверки среднего результата, и затем в зависимости от того, верен ли результат, применить ту же процедуру к первой или второй части вычислений. Ввиду того, что существует один шанс из девяти, что два случайных целых числа будут отличаться по модулю девять, надежность процелуры выбрасывания девяток равна только 89%.
Более надежный способ проверки — преобразовать результат обратно в восьмеричный формат с использованием обратного метода, который и будет сейчас рассмотрен. Преобразование целых чисел, представленных и десятичном формате, в восьмеричный формат.
Для выполнения обратного преобразования можно использовать аналогичную процедуру. Запишем заданное в десятичном формате число, удвоим на Й-м шаге Й ведущих разрядов, используя представление в восьмеричном формате, и сложим полученные (Й + 1) ведущих разрядов, опять же используя представление в восьмеричном формате. Для заданного числа, содержащего (гл + 1) разрядов, процесс заканчивается через тп шагов. Пример 2. Преобразовать число (1419857) ю в восьмеричный формат. 1,4 1 9 8 5 7 + 16.19857 + 64 81 5.98 5 7 + 458 8615.857 + 5406 Я Я 5 б 6.5 7 + 67554 4 85841.7 +1058508 Резулыпапп (56851я1 )а.
5685181 (Заметим, что при вычислении восьмеричного представления присутствуют невосьмеричные цифры 8 и 9.) Проверка результата может быть выполнена описанным выше способом. Этот метод был опубликован Шарлем П. Розье (СЬаг1ее Р, Вогбег), 1ЕЕЕ Тгапз. СЕ-11 (1962), 708-709. Обе описанные процедуры представляют собой, по существу, вариации метода 1, Ь обобщенного преобразования из одной системы счисления в другую. Операции удваивания и вычитания в десятичной системе счисления подобны умножению на 10 — 2 = 8. Операции удваивания и вычитания в восьмеричной системе счисления подобны умножению на 8 + 2 = 10.
Аналогичный метод существует и для преобразования из шестнадцатеричной системы счисления в десятичную, но это преобразование выполняется немного сложнее, так,как вместо операции умножения на 2 оно включает операцию умножения на б. Чтобы запомнить оба этих метода, нужно уяснить, что при переводе числа из восьмеричной системы счисления в десятичную выполняется вмчитпание, так как представление чисел в десятичном формате короче, чем в восьмеричном. Аналогично при переводе числа из представления в десятвчном формате в восьмеричный необходимо выполнять сложение.
Вычисления выполняются в формате представления резрльшаша, а не в исходном формате представления числа; в противном случае требуемый результат получен не будет. Преобразование дробей. Аналогичные методы, пригодные для столь же быстрого преобркювания вручную дробей, неизвестны. Похоже, что наилучшим является метод 2, а, в котором с целью упрощения операций умножения на 10 или 8 выполняются операции удвоения и сложения. В этом случае критерий выбора сложения и/или вычитания меняется на обратный — при преобразовании чисел в десятичный формат выполняется сложение, а при преобразовании чисел в восьмеричный формат выполняется вычитание.
Кроме того, при вычислениях используется формат, в котором представлено исходное число, а не формат, в котором подставляется результат (см. приведенные ниже примеры 3 и 4). Реализация этого процесса требует примерно в два раза больше вычислений, чем рассмотренный выше метод преобразования целых чисел.
Пример 3. Преобразование числа (.14159)во в восьмеричный формат. 14159 28318— 1.1 3 2 7 2 26544— 1.0 б 1 7 б 12352— 049408 9 8 8 16в 3.9 5 2 4 б 190528— 762112 124224— 4.9 б 8 9 б Результат: (. П0374...)в. Пример 4. Преобразование числа (,110374)в в десятичный формат.
.1 1 0 Э 7 0607 1.334 7 651 П. Преобразование чисел с плавающей точкой. При выполнении преобразований чисел с плавающей точкой необходимо одновременно выполнять операции как с целой частью числа, так и с дробной, поскольку преобразование целой части числа оказывает влияние на дробную часть. Для преобразования числа 7' 2' в десятичный формат можно сначала представить 2' в виде Е . 10в (обычно при помощи вспомогательных таблиц) и затем уже преобразовать гУ в десятичный фоРмат.
Аналогично можно Умножить е на 1об,о2 и затем окРУглить РезУльтат до ближайшего целого числа Е; после этого разделить 7' 2' на 10к и преобразовать результат. Обратно, для преобразован я числа Р'. 10Я в двоичный формат можно преобразовать Р', а затем умножить то на по ю зо-, прелставленное в формате с плавающей точкой (снова используя вспомогательные таблицы). Для уменьшения максимальных размеров вспомогательных таблиц используется обычная методика, основанная на применении нескольких операций умножения и/или деления, хотя это 4.1 91 64 14 5 1 1 5.6 1 8 7 О+ Э 0 6 6 О+ 160 0340+ 4140 Э О 3 О О+ 71700 553600+ 500600 1605400+ 6.3 3 Э 5 0 О Реву ъьгпат: (.141586...)ьо. может привести к распространению ошибки вследствие округления промежуточных результатов.
Вопросы минимизации таких ошибок рассмотрены в упр. 17. Е. Преобразование с многократной точностью. Начинать преобразование очень длинных чисел удобнее всего с преобразования блоков разрядов, операции с которыми можно выполнять с однократной точностью. Затеи следует объединить эти блоки, пользуясь простыми способами, которые специфичны для многократной точности. Например, пусть 10" — наивысшая степень 10, меньшая, чел1 размер машинного слова. Тогда: а) чтобы преобразовать целое число с многократной точностью из двоичного формата в десятичный, необходимо многократно разделить его на 10" (выполняя таким образом преобразование из двоичной системы счисления в десятичную с основанием 10" по методу 1, а); при помощи операций с однократной точностью получим п десятичных разрядов для каждой единицы представления в системе счисления с основанием 10"; Ь) чтобы преобразовать дробную часгиь числа с многократной точностью из двоичного формата в десятичный, поступим подобным образоьц умножив его на 10" (т.
е. использовав метод 2, а, где В = 10"); с) чтобы преобразовать целое чигло с многократной точностью из десятичной системы счисления в двоичную, преобразуем сначала блоки по и разрядов; затем для перехода из системы счисления с основанием 10" в двоичный формат используем метод 1, Ь; Й) для преобразования дробной части с многократной точностью из представления в десятичном формате в двоичный сначала выполним преобразование в систему с основанием 10", как и в процедуре (с), а затем используем метод 2, Ь.
Р. История и библиография. Приемы преобразования чисел из одной системы счисления в другую использовались еще в древности в задачах, связанных с мерами, весами и деньгами, когда обычно приходилось иметь дело с системами счисления со смешанными основаниями. Эти преобразования обычно выполнялись с помощью вспомогательных таблиц. В 17 веке, когда шестидесятеричные дроби были вытеснены десятичными, возникла необходимость выполнять преобразование из одной системы счисления в другую с тем, чтобы можно было пользоваться имеющимися книгами астрономических таблиц. В 1667 году в книге под редакцией Вильяма Отреда (ЪЪ'1111аш ОпйЬ1гео) С!аг1э Масйешайсш (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
