37. Кодирование и обработка в компьютере целых чисел со знаком. Прямой и дополнительный код. Дополнение числа. Дополнительный код двоичного числа.

Кодирование целых чисел, имеющих знак, можно осуществить двумя способами. В первом варианте один (старший) разряд машинном слове отводится для записи знака числа; при этом условились кодировать знак "+" нулем, знак "–" - единицей. Под запись самого числа, очевидно, остается 15 двоичных разрядов, что обеспечивает наибольшее значение числа Zmax = 215 - 1 = 3276710. Такое представление чисел называется прямым кодом. Однако его применение усложняет порядок обработки чисел; например, операция сложения двух чисел с разными знаками должна быть заменена операцией вычитания меньшего из большего с последующим присвоением результату знака большего по модулю числа. Другими словами, операция сопровождается большим количеством проверок условий и выработкой признаков, в соответствии с которыми выбирается то или иное действие.

Альтернативным вариантом является представление чисел со знаком в дополнительном коде. Идея построения дополнительного кода достаточно проста: на оси целых положительных чисел, помещающихся в машинное слово (0÷65535), сместим положение "0" на середину интервала; числа, попадающие в первую половину (0÷32767) будем считать положительными, а числа из второй половины (32768÷65535) - отрицательными. В этом случае судить о знаке числа можно будет по его величине и в явном виде выделение знака не потребуется. Например, 1000000000000012 = 3276910 является кодом отрицательного числа, а 0000000000000012 = 110 - кодом положительного. Принадлежность к интервалу кодов положительных или отрицательных чисел видна по состоянию старшего бита - у кодов положительных чисел его значение "0", отрицательных - "1". Это напоминает представление со знаком, но не является таковым, поскольку используется другой принцип кодирования. Его применение позволяет заменить вычитание чисел их суммированием в дополнительном коде. Мы убедимся в этом чуть позднее после того, как обсудим способ построения дополнительного кода целых чисел.

Дополнением (D) k-разрядного целого числа Z в системе счисления p называется величина D (Zp , k) = pk - Z.

Данную формулу можно представить в ином виде: D(Zp, k) = ((pk - 1) - Z) + 1. Число pk- 1 согласно (8), состоит из k наибольших в данной системе счисления цифр (p - 1), например, 999910, FFF16 или 11111112. Поэтому (pk - 1) - Z можно получить путем дополнения до p-1 каждой цифры числа Z и последующим прибавлением к последнему разряду 1.

Пример 13. Построить дополнение числа 27810. В данном случае p = 10, k = 3.

D(27810 , 3) = {<9-2><9-7><9-8>}+1, т.е. 721+1=722.

Важным свойством дополнения является то, что его сумма с исходным числом в заданной разрядной сетке будет равна 0. В рассмотренном примере:

В разряде тысяч 1 должна быть отброшена, поскольку она выходит за отведенную разрядную сетку.

Так как в двоичной системе счисления дополнением 1 является 0, а дополнением 0 является 1, построение D(Z2, k) сводится к инверсии данного числа, т.е. замена нулей единицами и единиц нулями, и прибавлением 1 к последнему разряду. Другими словами, дополнение двоичного числа формируется в два этапа:

строится инвертированное представление исходного числа;

к инвертированному представлению прибавляется 1 по правилам двоичной арифметики.

Дополнительный код (DK) двоичных целых чисел строится по следующим правилам:

для Z20 дополнительный код совпадает с самим числом (DK = Z2);

для Z2<0 дополнительный код совпадает с дополнением модуля числа, т.е. DK = D(|Z2| ,k).

38. Проверка и анализ корректности операций сложения/вычитания целых чисел со знаком.

Порядок проверок и анализа корректности операций сложения-вычитания (Z = Z(1) + Z(2)) можно представить в виде таблицы:

Таблица 3. Проверка и анализ корректности результатов

Старший бит Z(1) Старший бит Z(2) Старший бит Z Регистр переполнения Комментарий

0 0 0 0 Сложение двух положительных чисел без переполнения. Результат корректен

0 0 1 0 Переполнение при сложении двух положительных чисел. Результат некорректен

1 1 1 1 Сложение двух отрицательных чисел без переполнения. Результат корректен

1 1 0 1 Переполнение при сложении двух положительных чисел. Результат некорректен

0 1 0 1 Сложение чисел с разными знаками; Z(1)>|Z(2)|. Результат корректен

0 1 1 0 Сложение чисел с разными знаками; Z(1)<|Z(2)|. Результат корректен

39. Кодирование и обработка в компьютере вещественных чисел. Понятие машинного нуля. Особенности обработки.

На этом шаге мы рассмотрим кодирование и обработку в компьютере вещественных чисел.

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

Ситуация радикальным образом меняется при представлении и обработке вещественных чисел. На математической числовой оси вещественные числа образуют непрерывное множество (континуум), т.е. два числа могут находиться сколь угодно близко друг к другу, и на любом отрезке содержится бесконечно много значений чисел. В машинном представлении количество возможных значений чисел конечно; для двоичной системы счисления оно определяется как 2k, где k – количество двоичных разрядов в представлении мантиссы. Т.е. вещественные числа в компьютере заменяются их кодами, которые образуют конечное дискретное множество; каждый код оказывается представителем целого интервала значений континуума.

Из данного обстоятельства вытекают ряд следствий.

Следствие 1 состоит в том, что строгие отношения между числами континуума превращаются в нестрогие для их компьютерных представителей, т.е.

если x(1)> x(2), то X(1) X(2);

если x(1) = x(2), то X(1) = X(2);

если x(1) < x(2), то X(1) X(2).

Следствие 2. Поскольку код вещественного числа в компьютере является приблизительным представителем многих чисел из интервала, то и результаты вычислений также будут заведомо неточными, содержащими неизбежную погрешность. В этом состоит главная особенность обработки вещественных чисел в компьютере – она всегда ведется с погрешностью (кстати, оценка этой погрешности – самостоятельная и непростая задача).

Следствие 3. Наряду с понятием наибольшего вещественного числа (из-за ограниченности разрядной сетки) появляется понятие наименьшего числа или машинного нуля. Например, в типе Real языка PASCAL любое десятичное число, по модулю меньшее 2,3·10-39 оказывается машинным нулем, т.е. считается равным 0 при сохранении и в операциях с ним. Таким образом, математическое понятие "0" как точное значение числа в компьютерном представлении заменяется понятием "машинный нуль" как значение числа меньшее некоторой определенной величины.

Как уже было сказано, основной формой представления кодов вещественных чисел в компьютере является двоичная нормализованная. При этом записываться и храниться в памяти компьютера должны все составляющие нормализованной формы (знак числа, мантисса, знак порядка и порядок), что требует нескольких ячеек памяти. Например, числа типа Real ("вещественный") из языка PASCAL размещаются в 6 байтах, т.е. 48 двоичных разрядах. Непосредственное распределение компонентов нормализованного числа по разрядам определяется конструктивными особенностями компьютера и программным обеспечением. Ниже приведен пример размещения числа в двух ячейках памяти (32 разряда):

Поскольку значение мантиссы лежит в интервале 0,12 M2<1, нуль в разряде целых и разделитель десятичных разрядов в представление не включается, т.е. мантисса содержит только цифры дробной части. Более того, можно не сохранять и первую значащую цифру мантиссы, поскольку она всегда 1 (но, естественно, восстанавливать ее при вычислениях) – это дает возможность хранить дополнительный "скрытый" разряд, т.е. несколько повысить точность обработки. В ходе выполнения арифметических операций, как указывалось ранее, производится нормализация промежуточных и конечного значений, состоящая в сдвиге мантиссы вправо или влево с одновременным изменением порядка, что эквивалентно смещению разделителя десятичных разрядов – именно по этой причине такая форма представления числа получила название "с плавающей запятой". Как и в случае целых чисел, для кодов вещественных чисел существует понятие переполнение, однако возникает оно не после заполнения разрядной сетки мантиссы – это приводит лишь к нормализации числа, а при заполнении всех разрядов порядка. Для представленного выше примера размещения числа в 32-х битах, очевидно,

|X2|max = 0,1111111111111111111111112· 2111112,14710·109

При этом точность обработки составит 7 десятичных разрядов. При |X2| > |X2|max возникнет переполнение, т.е. операция станет некорректной.

Пример 16. Установить распределение разрядов двоичного представления числа типа Real, если для его записи отводится 48 бит, а максимальное значение десятичного порядка 38. Какова точность обработки таких чисел?