Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 63
Текст из файла (страница 63)
Нистром разработал специальные правила произношения шестнадцатеричных чисел; например, (С0160)т следовало читать как "вибонг, бисантон" (туЬопй, Ьуяапсоп). Полная система была нм названа тональной и описана в д. Ргшй!!п !пяп 46 (1863), 263-275, 337-348„402-407. Аналогичная система, но использующая основание 8, была предложена Альфредом Б. Тэйлором (А1(гег! В. Тау)ог) и описана в Ргос. Атег. РЬагтасеия!сгг! Аяяос.
8 (1859), 115-216; Ргос. Атег. Р!и)ояорЫса! Бос. 24 (1887), 296-366. Со времен Лейбница двоичная система счисления становится хорошо известной диковинкой, и Р. К. Арчибальд (В. С. АгсЬ1ЬаЫ) собрал более 20 посвященных ей ранних работ [АММ 25 (1918), 139-142). Она применялась, главным образом, для вычисления степеней, как будет объяснено в разделе 4.6.3„а также при анализе некоторых игр и головоломок. Джузеппе Пеаио (О!пверре Реапо) использовал двоичную систему как базис "логического" алфавита из 256 символов [А!1! деНа Н.
Ассадегша де!1е Яс!епге 05 Тогщо 34 (1898), 47 — 55). Джозеф Боудеи (ЗоверЬ Вогедеп) предложил систему обозначений для шестнадцатеричных чисел [Бреси) Торги !и ТЬеогедсв1 Аг!ГЬтев!с (Оагдеп С!Гу, 1936), 49). В книге Антона Глэйзера (Апгоп О!авег) Н!в!агу ог Вгпагу апд Овйег Жопг1есипа1 Хигпегаг!оп (1лзв Апйе1ев; ТопгавЬ, 1981) приведена подробная информация и практически исчерпывающий анализ развития двоичной системы, включая перевод иа английский язык многих работ, процитировапиых выше (см.
Н!вгог!а Мавй. 10 (1983), 236-243). Большинство современных числовых систем связано с развитием вычислительных машин. Из заметок Чарльза Бзббиджа (СЬаг!ев ВаЬЬайе) 1838 года понятно, что ои задумывался иад использованием в своей аналитической машине иедесятичиых чисел (см. М. У. Ж!!Ьев, Н!ввопа Мавй. 4 (1977), 421). Повышеииый интерес к механическим устройствам для выполнения арифметических операций, особеиио умножения, побудил в ЗО-х годах ряд исследователей обратить внимание иа двоичную систему. Прекрасный отчет об этих исследоааииях вместе с записью дискуссии, состоявшейся после прочнтаииой им иа данную тему лекции приведен в статье Э.
Уильяма Филлипса (Е. %Ш!аш РЬШгрв) "Двоичные нычислеиияе [Юоигпа1 ог гйе 1пвдвпге ог" Асвиапев 67 (1936), 187 — 221[. Филлипс начал статью словами "Конечная цель (этой статьи) состоит в том, чтобы убедить весь цивилизованный мир отказаться от десятичной нумерации и заменить ее восьмеричной". Совремеииыо читатели статьи Филлипса, возможно, будут удивлены, обнаружив, что система счисления по осиоваиию 8 называлась в то время в соответствии со всеми словарями английского языка ьосгопагуе или носгопаГ, точно так, как система по основанию 10 называлась ндепагуь или ндесппа!".
Слово уосгаГ появилось в английском языке только после 1961 года, причем первоначально, скорее всего, как термин для описания конструкции цоколя определенного класса вакуумных электронных ламп. Слово "Ьехадесппа)", которое вкралось в английский язык еще позже, представляет собой смесь греческого и латинского корней.
Более корректными терминами должны были быть либо евеп!депагу", либо еведесппаГ, либо даже "вехадес!шаГ, ио последний, пожалуй, для программистов звучал бы слишком рисковаиио, Высказывание Ф. Х. Уэйлса, приведенное в качестве одного из эпиграфов к этой главе, извлечено из записи дискуссии, опубликованной вместе со статьей Филлипсш Другой слушатель лекции указал иа неудобства восьмеричной системы для деловых целей: 5% "превращается в 3.1463 рег 64, что звучит довольно ужасно"'". Филлипса вдохновила возможность реализации его идей в устройствах, работающих иа электронных лампах и способных выполнять вычисления в двоичном коде [С.
Е. Жупп-%!Шашв, Ргос. Воу. Яос. 1опдоп А136 (1932), 312-324[. Во второй половине ЗО-х годов Джон В. Атаяасофф (ЗоЬп У. Асапавой) и Джордж Р. П1тибитц (Оеогйе Н. Бг!Ыгв) в СП1, Л. Куффигивл (1. Сопййпа)) и Р. Валга (В.. Ъа!гав) во Франции, а также Гельмут П1рейер (Не!шц! БсЬгеуег) и * Поскольку елово "процент" на английсиом языке пигнется иан "рег сенс" (от лат.
"рег сенгннг'*), а "сенс" (!00) заменяется числом 64. — прим. нерее. Конрад Пузе (Копгас( Епэе) в Германии разработали первые электромеханическне и электронные машины для выполнения арифметических операций. Все они использовали двоичную систему счисления, хотя позже Штибитц разработал и двоичный код ис избьаткола 3" для десятичных цифр.
Обобщенный обзор этих ранних достижений, включая переводы и копии наиболее значимых современных документов, содержится в книге ВНап 11елс1ей Т!ае Ог!и!пз ог" О!к!Га! Сошрпсегэ (Вег!ш: Ярйпйег, 1973). В первых быстродействующих вычислительных машинах, созданных в США в начале 40-х годов, использовалась десятичная арифметика. Но в 1946 году в сьп равшем важную роль отчете А. В.
Веркса (А. %. Впг)сз), Г. Г. Голдстайна (Н. Н. Оо16- эс1пе) н Дж. фон Неймана (3. топ Неппшпп) о проекте первой вычислительной машины с хранимой в памяти программой были подробно изложены причины, которые побудили их порвать с традицией и перейти к системе счисления по основанию 2 (см. 3оЬп иоп Нешпапп, Со!!есгес! 1тог)гэ 6, 41-65). С тех пор двоичные вычислительные устройства получили всеобщее распространение.
После первой дюжины лет работы с двопчными машинами в статье В. Буххольца (%. ВпсЫло1з) иЕ1пбегз ог Р1эсэ".и (САСМ 2 (ВесешЬега 1959), 3 — 1Ц был выполнен анализ сравнительных достоинств и недостатков двоичной системы счисления. Структура компьютера И1Х, используемого в этой книге, такова, что машина может быть как двоичной, так н десятичной.
Интересно отметить, что почти все программы для этого компьютера можно написать, не зная, какая именно система используется (двоичная или десятичная), даже при выполнении вычислений с многократной точностью, Итак, лаы видим, что на методику программирования для компьютера выбор основания системы счисления не оказывает значительного влияния. (Заслуживает упоминания исключение из этого правила — операции "булевой"' алгебры, рассматриваемые в разделе 7,1; см, также алгоритм 4.5.2.) Ошрицагпельные числа могут быть представлены в компьютере несколькими способами. Выбор того или иного способа зачастую оказывает влияние на метод рылизации арифметических операций. Поясним сказанное. Сначала будем считать машину й1Х десятичной; тогда каждое слово состоит из десяти цифр и знака, например (2) -12345 67890.
Этот способ представления называется абсолюапнмм значением со знакам"'. Такое представление соответствует общепринятым обозначениям, и талому его предпочитают многие программисты. Возможное неудобство заключается в том, что допуска ется существование как "минус нуль", так н "плюс нуль", в то время как этн разные коды должны обозначать одно и то же число. На практике такая возможность требует принятия определенных мер предосторожности.
В большинстве механических счетных машин, выполняющих действия десятичной арифметики, используется другая спстема записи — допаяааение до деслпаиее. Если вычесть 1 из 00000 00000, в этой системе записи получим 99999 99999", другими * В обшепрннятой русскояэычной термннопогнн этому понятию соответствует термин прямое код.
— Прим. нерее. а* В обшепрннятой русскояэычной термяноногнн этому понятию соответствует термин доноянишеяинна код. — Прим. порее. словами, числу явно не приписывается знак, а вычисления выполняются по мцду- лю 10'о. Число -1234о 67890 в форме дополнения до десяти будет выглядеть так: (3) 87654 32110. В этой системе обозначений принято считать отрицательным любое число, ггзловная цифра которого — 5, б, 7, 8 нли 9, хотя с точки зрения сложения и умножения не будет большим грехом рассматривать (3), если это удобно, как число +87654 32110. Попутно отметим, что в такой системе не возникает проблема "минус нуль". На практике основное различие между двумя описанными формами представления заключается в том„что сдвиг вправо дополнения до десяти не эквивалентен делению на 10; к примеру, число — 11 =...
99989 после сдвига вправо на одну позицию превращается в ... 99998 = -2 (в предположении, что сдвиг вправо отрицательного числа порождает в головном разряде "9з). В общем случае результатом сдвига числа х, записанного в формате дополнения до десяти, на одну позицию вправо будет число (х/10), независимо от того, положительно или отрицательно число х. Одним из возможных неудобств записи в формате дополнения до десяти является несимметричность относительно нуля. Наибольшее отрицательное число, представимое р цифрами, есть 500...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
