Кодирование и обработка в компьютере целых чисел со знаком

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

В первом варианте один (старший) разряд машинном слове отводится для записи знака числа;

При этом условились кодировать знак "+" нулем, знак "–" - единицей.

Под запись самого числа, очевидно, остается 15 двоичных разрядов, что обеспечивает наибольшее значение числа Zmax = 2^{15 - 1} = 32767₁₀.

Такое представление чисел называется прямым кодом.

Однако его применение усложняет порядок обработки чисел;

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

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

Альтернативным вариантом является представление чисел со знаком в дополнительном коде.

Идея построения дополнительного кода заключается в следующем:

· на оси целых положительных чисел, помещающихся в машинное слово (0÷65535), сместим положение "0" на середину интервала;

положительные 0 отрицательные

0 32767,32768 65535

· числа, попадающие в первую половину (0÷32767) будем считать положительными, а числа из второй половины (32768÷65535) - отрицательными.

В этом случае судить о знаке числа можно будет по его величине и в явном виде выделение знака не потребуется.

Например, число 100 0000 0000 0001₂ = 32769₁₀ является кодом отрицательного числа,

А число 000 0000 0000 0001₂ = 1₁₀ - кодом положительного.

Принадлежность к интервалу кодов положительных или отрицательных чисел видна по состоянию старшего бита кодов:

· у положительных чисел его значение "0",

· у отрицательных - "1".

Это напоминает представление со знаком, но не является таковым, поскольку используется другой принцип кодирования. Его применение позволяет заменить вычитание чисел их суммированием в дополнительном коде.

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

D (Z_p , k) = p^k - Z.

Данную формулу можно представить в ином виде:

D(Z_p, k) = ((p^k - 1) - Z) + 1.

Число p^k - 1, состоит из k наибольших в данной системе счисления цифр (p - 1), например, 9999₁₀, FFFF₁₆ или 1111₂.

Поэтому (p^k - 1) - Z можно получить путем дополнения до p-1 каждой цифры числа Z и последующим прибавлением к последнему разряду 1.

Пример 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, построение D(Z₂, k) сводится к инверсии данного числа, т.е. замена нулей единицами и единиц нулями, и прибавлением 1 к последнему разряду.

Другими словами, дополнение двоичного числа формируется в два этапа:

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

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

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

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

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

Пример 14. Построить дополнительные двоичные коды чисел

(a) 3₁₀

(b) -3₁₀.

(a) Так как Z>0, DK: 0000 0000 0000 0011.

(b) Так как Z<0,

Проверка:

Вновь убеждаемся, что

DK(Z) + DK(–Z) = 0 (14).

Видно, что общее количество кодов совпадает и, следовательно, одинаковым будет количество кодируемых чисел в обоих способах.

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

Перевод в дополнительный код происходит автоматически при вводе чисел; в таком виде числа хранятся в ОЗУ и затем участвуют в арифметических операциях.

При этом, как уже было сказано, операция вычитания двух чисел как самостоятельная отсутствует – она заменяется сложением первого числа с дополнительным кодом второго, т.е. просто сложением содержимого двух ячеек памяти. Убедимся в правомочности этого.

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

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

Порядок проверок и анализа корректности операций сложения-вычитания

Z = Z(1) + Z(2)

можно представить в виде таблицы:

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

Подобным же образом число из дополнительного кода переводится в прямой при выполнении операции умножения;

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

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

Однако допустимыми являются операции целочисленного деления и нахождения остатка от целочисленного деления

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

Примем обозначения:

· Z⁽¹⁾ – делимое;

· Z⁽²⁾ – делитель;

· L – результат целочисленного деления Z⁽¹⁾ на Z⁽²⁾;

· R – остаток от целочисленного деления Z(1) на Z⁽²⁾.

Эти величины связаны между собой соотношением:

Z⁽¹⁾ = L· Z⁽²⁾ + R,

из которого следует алгоритм нахождения значений L и R для заданных Z⁽¹⁾ и Z⁽²⁾; его блок-схема для положительных Z⁽¹⁾ на Z⁽²⁾ представлена на рисунке 1.

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

При этом уровень программной реализации может быть различным.

Если реализация выполнена на уровне команд центрального процессора, то эти операции оказываются доступны из любого приложения (любой прикладной программы).

Если же в системе команд процессора эти микропрограммы отсутствуют, их приходится описывать в виде процедур в самих приложениях и, следовательно, они будут доступны только в этих приложениях.