lekcii2 (Лекции), страница 10

Последнее представляет все математические целыс, оставшиеся за пределом диапазона ~МЕХ, МАХ] Езначение переполнения). Присваивание этих метазначений некоторому объекту может приводить к возникновению особых ситуаций, которые должны воспрепятствовать дальнейшему выполнению программы ввиду его некорректности. Таким образом, множество значений целого типа, в отличие от множества целых чисел, конечно К = ~ Е,'Е ! МЕЛ1 < в < МАХ) 0 т~Е., Т) Е1ад значениями целого типа определены обычные целочисленные арифметические операции, а именно: сложение Е+), вычитание Е-), умножение (Ф), целочисленное деление (/ (для целочисленных операндов!) в Си или сЕЕ)1 в Паскале).

То есть в Паскале операция деления для целого типа изображается отдельным символом сЕзл, а в Си оба деления изображаются одним символом /, что может ввести в заблуждение начинающего программиста. Кроме этих операций дополнительно определены одноместная операция изменения знака числа па противоположный (эту операцию мы будем обозначать знаком «-> либо.

чтобы не путать с бинарным минусом, символом пея (противоположный)) и двуместная операция вычисления остатка от целочисле)пюго деления ЕшосЕ в Паскале или % в Си). Для значений целого типа Опр1делены Отношш1иЯ порЯдка 1», , (, () и ОтнОшениЯ равенства (=, у1). Операнды отношений целочисленные, результаты логические, т, е.

отношения размыкак)т целый тип, отображая пары целочисленных значений в истинности)~)е значш)ия зна11)ния друг1)го Ело)ичсского) типа., Н Огличие От к)ги~)еск1)го типа, отношения операциями не являются, т. к. результат операции должен принадлежать тому же типу, что и операнд. Цслочислс нное деление реализовано без остатка., чтобы не размыкать целый тип для получения дробного частного более сложного вещественного типа, Здесь и выше размыкание понимается в алгебраи 1ески-кольцевом смысле; результат операции над любыми допустимыми операндами должен оставаться в том жс самом множестве (кольце).

Некоторые свойства операций и отношений: 1, коммутативность сложения иумножения; ))Х,У Е К Х+) = УЕ Л,Х*Е' = Е *Х; 2, если Л > У > О или Х ( У < О, то ЕХ вЂ” У) + У = Х; 3, монотонность операций: ЧХ, У Е У из О < Х < А и О < У ( В следует Х+У<А Е В: Л вЂ” В<А — Е; Х*У<А*В; Х ~ В<АЕУ: Все это верно только если А + В < МАХ и А э В < МАХ соответственно. 1, если хотя бы один из операндов операции цслого типа имеет значение 1 или Т, то результат операции тоже имеет значение 1 или Т соответственно.

Если один операнд двуместной операции имеет значение 1., а другой Т, то результат операции имеет значение 5, если один из операндов отношения целого типа имеет значение 1 или Т, то результат имеет значение 1. Строго говоря, это неопределенное значение принадлежит логическому типу. Отметим, что наличие значений 1 и Т со сформулированными выше свойствами приводит к тому, что для операций целого типа не выполняются законы ассоциативности и дистрибутивности.

Это тоже жертвы эф>рективной вычислимости по фон Нейману. Например, ассоциативный закон (Х 1 У) 1 Я = Х !- (1 + Л) не выполняется, если результатом хотя бы одной из операций в левой части является Т, а, в правой части нет операций, имеющих результатом значение Т, и наоборот. Если для некоторого процессора Л1ЛХ = 32 767, то 20000 + (30000 -1 ( — 25000)) = 20000 1- 5000 = 25000, а результат нь> пн:ленин (20 000 1 30 000) 1 ( — 25 000) = Т, так как 20 000 ~ 30 000 = Т, Т вЂ” 25 000 = Т. 16-разрядный целочисленный процессор с дополнительным кочированием целых имеет следунпций диапазон: [ — 32 768..32 767); его верхняя граница является предопределенной константой МАХ?ХТ для короткого целого (О, Вог1апс1!). Диапазон 32-разрядного процессора существенно шире: [ — 2!47483 648..2 147483 647).

Это число является значением константы ИАХ1ИТ в СМГ и Соп>рас1 Разса1. Аналогичная константа 1ХТ МАХ хк>жег быть извлечена из стандартной библиотеки языка С (файл <11шйтв.1»). В 64-разрядном процессоре представимы числа в диапазоне [ — 9 223 372 036 854 775 808 .. 9 223 372 036 854 775 807], или [ — шахш$64 — 1..шнхш$64~, для чего приходится применять песта>>дартный тип пйевег64 в Сотрас1 Рааса! или стандартный тип 1опп 1опп ш$ л„ля 64-битных версий Сошрас1 С (сс) и С>%1 С (йсс).

Эти типы имеют аппаратную поддержку на соответствук>- щих процессорах. Кроме того, беззнаковая версия целого типа используется д.чя вычисления адресов (адресная арифметика). Таким образом, 64-битный процессор имеет адресное пространство 16777216 терабайт, или 16384 петабайт, или 16 экзабайт, что составляет 18 446 744 073 709 551 616 байт! Рассмотренные операции и отношения позволяют опрсделить двоичный целочисленный процессор Е1>1Т%) с множеством изображений И'в = (адяз...

аь!а, Е (0,1), г = 1, 2,..., Ус) О [11... 1, ТТ... Т), Функция интерпрста>ши р следуклцая: Ь букв Ь букв 1. Слово из букв 0 и 1 является записью пелого числа с использованием дополнительного кода,. 2. Слово из букв 3 соответствует неопределенному значению.

3. Слово из букв Т соответствует переполнению. 145 Ярес1пс ЯресРес Эти машины в обычном тьюринговском смысле пенормированы. Но при построении машины фон Неймана мы у'кс прибегали к подобной перенормировке. На базе этих машин построим перенормированные (в смысле положения головки МТ, неизменность аргументов не соблюдается) МТ для инкремента и декремента. Опи соответствуют префиксным формам этих операторов в С!Сч -~ .

Нь 1. Брес1пс. К 3~ 1 Брес11ес В. Операция сложения с одновременной записью результата в правый операнд аналогична операторам а= в С1С+ — (а - одна из операций +, —, *, /, %, Й, [,, «, »): Бинарное сложение теперь реализуется очень просто через уже введенную МТ ЕЛу„.. П~, [Ли,',Лиг(Л)Л) =~' [Лиз,Ли~зЛи~(Л)Л), где р(ю) =,р(го~) ! р(п~з), и, ид, и'г Е И'ь. Н, к.,ЕЛ,. То есть мы вручную отнормировали результат ненормированного сложения.

С целью простоты реализации переполнение не отслеживается. Ненормированный оператор унарный минус меняет на месте знак числа в дополни- Е~, тельном коде: [Лш(Л)Л) =~* [Лп~(Л)Л), где р(ю) = — р(гп), гп Е И'ь. 1!ри таком определении процессора 1ХТ(1с) константы ЛХ1М и ИАХ имеют значения — 2 и 2 ' — 1 соответственно. — ° ь-~ Алгоритмы выполнения операций и вычисления отношений процессора !КТО можно конструктивно описать диаграммами Тьюринга. Опишем сначала, специальные машины инкрсмента и дскремента.

Они необходимы для выполнения рутинных повторяюшихся операций в более сложных арифметических машинах. Е~,,-Ьг 0 Опера»»ия вычитания с одновременной записью результата в правый операнд аналогична вышеупомянутым операторам вида а= в С,'С» +. В данном случае левый опсра,нд является вычитаемым, в правый уменьшасмым.

При этом результат помещается в правый операнд, т. к, в силу полубесконсчности ленты МТ удобно (для дальнсй»пего использования) все результаты помещать справа от операндов. Эта машина, хотя и не создает ~о~~к слов, помещае~ резул~~а~ ~~си~о так для од~собрали~ и унифи»сации с друг~~и машинами. Ес операнды записаны в обратном порядке, т. к. в С,'С'; Ь а — -- Б означает а а — Ь, то есть операнд-результат является уменыпасмым. Пь - БП», Е:1,. БН»л В. Бинарный оператор вычитания с записью результата в новое с:»ово. Нь - к,Н,. Теперь о»»ишем принцип работы машины двоичного умножения. Пусть слова фиксированной длины к и»» и ш2 — — 6»6»,...

Ь, содержат два двоичных числа. Поскольку гюзиционная система счисления является полиномиалыюй интерпретацией последовательности цифр числа, то умножение чисел, по сути, есть умножение соответствующих многочленов с двоичными коэффиписнтами, вычисленных в точке 2. Тогда,р(ий) р(и~2) р(гю») 2; 6,2' ' = 2;;э(и~»)6»2* ". Умножение на многочлен проще делать почленно, причем ввиду,чвоичности используемой сис:темы счисления слагаемые этой суммы либо будут присутствовать (с коэффициентом 1), либо нет, если соответствухлцая двоичная цифра Ь, равна О. Таким образом, можно получить произведение двух чисгел путем однократных сложений (если на данном месте в записи числа стоит 1) и сдвигов влево.

В отличие с>т машин сложения, машина умножения использует дополнительное слово для хранения результата. Вот схема с'е работы; [Ли~2Ли»»(Л)Л) =:- [Ли»2Ли»»ЛО(Л)Л) ~ [Ли»эЛи»,Ли»(Л)Л) => [Лй»2Ли»1Л)Л). Для реализации работы машины по приведенной схеме необходимо описать несколько вспомогательных машин. Первой такой машиной является машина, ненормированного арифметического сдвига разрядов в машинном слове и» влево на один разряд ([(Л)и»Л) ~ [Лиу(Л))), где и» = 6»6»»...

Ь~Ь», а и" = 6»6» эЬ» в... ЬэЬ»0. Здесь Ьь — «знаковый» разряд дополнительного кода. о 10»2 БЫМ» г ге~' ~> гОг 11 147 Действие в скобках это перенос одного бита справа на.л:во, Однако при этом машина находится не на той позиции, куда будет скопирован очередной бит. Можно слегка изменить диаграмму (отказавшись от двух машин г в начале итерации), чтобы она копировала правый бит на текугпую позицию и передвигалась влево, вместо того, чтобы сначала передвигаться влево, а потом копировать биты, как это реализовано вьпгю.