Часть 5 Вопросы 13-15

Кодирование целых чисел, имеющих знак.

Кодирование целых чисел, имеющих знак, можно осуществить двумя способами. В первом варианте один (старший) разряд машинном слове отводится для записи знака числа; при этом условились кодировать знак «+» нулем, знак «–» - единицей. Под запись самого числа, очевидно, остается 15 двоичных разрядов, что обеспечивает наибольшее значение числа Z^max = 2¹⁵ - 1 = 32767₁₀. Такое представление чисел называется прямым кодом. Однако его применение усложняет порядок обработки чисел; например, операция сложения двух чисел с разными знаками должна быть заменена операцией вычитания меньшего из большего с последующим присвоением результату знака большего по модулю числа. Другими словами, операция сопровождается большим количеством проверок условий и выработкой признаков, в соответствии с которыми выбирается то или иное действие.

Альтернативным вариантом является представление чисел со знаком в дополнительном коде. Идея построения дополнительного кода достаточно проста: на оси целых положительных чисел, помещающихся в машинное слово (0÷65535), сместим положение «0» на середину интервала; числа, попадающие в первую половину (0÷32767) будем считать положительными, а числа из второй половины (32768÷65535) - отрицательными. В этом случае судить о знаке числа можно будет по его величине и в явном виде выделение знака не потребуется. Например, 100000000000001₂ = 32769₁₀ является кодом отрицательного числа, а 000000000000001₂ = 1₁₀ - кодом положительного. Принадлежность к интервалу кодов положительных или отрицательных чисел видна по состоянию старшего бита - у кодов положительных чисел его значение «0», отрицательных - «1». Это напоминает представление со знаком, но не является таковым, поскольку используется другой принцип кодирования. Его применение позволяет заменить вычитание чисел их суммированием в дополнительном коде.

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

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

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

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

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

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

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

Пример: Построить дополнительные двоичные коды чисел (a) 3₁₀ и (b) –3₁₀.

Проверка:

Дополнительных кодов оказывается на один больше, чем прямых, и интервал целых чисел со знаком при их размещении в 2-байтном машинном слове составляет [–32768; 32767] - именно такими являются граничные значения целых чисел типа Integer в языке PASCAL, что свидетельствует об использовании дополнительного кодирования в представлении чисел. Перевод в дополнительный код происходит автоматически при вводе чисел; в таком виде числа хранятся в ОЗУ и затем участвуют в арифметических операциях. При этом, как уже было сказано, операция вычитания двух чисел как самостоятельная отсутствует – она заменяется сложением первого числа с дополнительным кодом второго, т.е. просто сложением содержимого двух ячеек памяти. Убедимся в правомочности этого.

Пример: Найти значение (27 – 3)₁₀ в двоичной кодировке.

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

Подобным же образом число из дополнительного кода переводится в прямой при выполнении операции умножения; перемножаются всегда положительные числа по рассмотренным выше правилам; знаковый бит результата, очевидно, будет содержать 0, если знаки чисел одинаковы, и 1 при противоположных знаках.

Над множеством целых чисел со знаком операция деления не определена, поскольку в общем случае ее результатом будет вещественное число. Однако допустимыми являются операции целочисленного деления и нахождения остатка от целочисленного деления (те, что мы немного ранее обозначили div и mod).

Вещественные числа.

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

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

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

|X₂|^max = 0,111111111111111111111111₂· 2¹¹¹¹¹ 2,147₁₀·10⁹

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

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

2 бита расходуется на запись знака числа и порядка;

согласно формуле, k₂ = 3.322·k₁₀; поскольку k₁₀ = 38, очевидно, максимальный показатель порядка двоичного числа k₂ = 3.322·38 126₁₀, что требует в двоичном представлении, согласно формуле Хартли, 7 бит;

под запись мантиссы отводится 48 - 2 - 7 = 39 бит;

с учетом скрытого разряда точность обработки составит (39 + 1)/3,322 12 десятичных разрядов.

Изначальной причиной возникновения погрешности обработки кодов вещественных чисел является ограниченность разрядной сетки при их представлении и, следовательно, наличие погрешности неизбежно. Однако ее величина зависит от количества имеющихся разрядов и, в частности, уменьшить погрешность можно за счет расширения разрядной сетки, т.е. выделения большего количества ячеек памяти для записи числа. Например, в языке PASCAL определен вещественный тип Extended, числа которого занимают 10 байт, что обеспечивает точность мантиссы до 20 десятичных знаков и значение модуля порядка до 4932. Несколько вариантов представления вещественных чисел в языках программирования высокого уровня используется как одно из средств оптимизации программы. Повышение точности вычислений требует больших ресурсов памяти компьютера; одновременно с этим возрастает и время вычислений. Таким образом, при составлении программы для практической задачи решается проблема нахождения компромисса между точностью результата и временем обработки.

Арифметические действия с нормализованными числами

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

Сложение нормализованных чисел.

Пусть имеются два числа X₁ = M₁·p^k1 и X₂ = M₂·p^k2 (здесь индексы у мантиссы и порядка означают не систему счисления, а служат номерами чисел).

Сложение должно начинаться с выявления большего из k₁ и k₂, нахождения модуля их разности k =|k₁ - k₂| и сдвига вправо на k разрядов мантиссы того числа, у которого k оказался меньше. После этого выполняется сложение мантисс, порядку результата присваивается значение большего из имеющихся и при необходимости производится нормализация результата. При сдвиге вправо мантиссы меньшего числа происходит потеря k младших значащих цифр, что приводит к появлению погрешности сложения.

Рассмотрим действие алгоритма на примере сложения десятичных чисел в ограниченной разрядной сетке.

Пример: Найти сумму X₁=0,87654·10¹, а X2=0,94567·10², если для записи мантиссы отводится 5 разрядов.

Согласно алгоритму k = 1 и k₁<k₂. Следовательно, k=k₂=2, а мантисса числа X₁ должна быть сдвинута на 1 разряд вправо (при этом из-за ограниченности разрядно сетки пропадет цифра 4). Новая мантисса получается суммированием M=0,94567+0,08765=1,03332; поскольку она выходит за допустимый интервал представления мантисс, необходимо его нормализовать M ’ = 0,10333 (при этом теряется цифра 2 в младшем разряде); k ’ = k+1=3. Окончательно получаем: X=0,10333·10³. Точный результат суммирования оказался бы 103,3324.

Следствием существования погрешности сложения (и, в равной мере, вычитания) кодов вещественных чисел оказывается то, что такое суммирование не обладает ассоциативностью, т.е. в общем случае (X₁ X₂) X₃ X₁ (X₂ X₃).

Вычитание нормализованных чисел как и чисел целых, не является самостоятельной операцией и сводится к сложению с дополнительным кодом числа.

Умножение нормализованных чисел X₁ X₂ производится в соответствии с правилами: если по-прежнему X₁ = M₁·p^k1 и X₂ = M₂·p^k2, то, очевидно, мантисса произведения M=M₁·M₂, а порядок k=k₁+k₂; при необходимости полученное число нормализуется.

Операция деления, проводимая как над целыми, так и вещественными числами, приводит в общем случае к появлению вещественного числа, поэтому целые числа предварительно преобразуются в вещественный тип, т.е. переводятся в нормализованную форму. Очевидно, при делении X₁ X₂ мантисса частного M = M₁/M₂, а порядок k = k₁-k₂. При этом непосредственно операция деления сводится к сдвигу делителя вправо и последовательному вычитанию его из делителя (т.е. сложения с дополнительным кодом вычитаемого). Как и в предыдущих операциях, результат деления при необходимости нормализуется.

Замечания:

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