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

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

Альтернативным вариантом является представление чисел со знаком в дополнительном коде. Идея построения дополнительного кода достаточно проста: на оси целых положительных чисел, помещающихся в машинное слово (%%0 ÷ 65535%%), сместим положение «0» на середину интервала; числа, попадающие в первую половину (%%0 ÷ 32767%%) будем считать положительными, а числа из второй половины (%%32768 ÷ 65535%%) - отрицательными. В этом случае судить о знаке числа можно будет по его величине и в явном виде выделение знака не потребуется. Например, %%100000000000001_2 = 32769_{10}%% является кодом отрицательного числа, а %%000000000000001_2 = 1_{10}%% - кодом положительного. Принадлежность к интервалу кодов положительных или отрицательных чисел видна по состоянию старшего бита - у кодов положительных чисел его значение «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_{10}%%, %%FFF_{16}%% или %%1111111_2%%. Поэтому %%(p^k - 1) - Z%% можно получить путем дополнения до %%р-1%% каждой цифры числа %%Z%% и последующим прибавлением к последнему разряду 1.

Пример. Построить дополнение числа %%278_{10}%%. В данном случае %%р = 10%%, %%k = 3%%.

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

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

722+278=1000

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

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

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

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

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

Пример. Построить дополнительные двоичные коды чисел (а) %%3_{10}%% и (b) %%-3_{10}%%.

(a) Так как %%Z>0%% - DK = 0000 0000 0000 0011

(b) Так как %%Z<0%%:

1. Модуль числа 0000 0000 0000 0011
2. Инверсия числа 1111 1111 1111 1100
3. DK=1111 1111 1111 1101

Проверим:

Убеждаемся, что %%DK(Z)+DK(-Z)=0%%

Сопоставление прямых и дополнительных кодов представлено в виде таблицы:

Прямой десятичный код	Прямой двоичный код с 16 разрядами	Дополнительный двоичный код с 16 разрядами
-32769	-	-
-32768	-	1000 0000 0000 0000
-32767	1111 1111 1111 1111	1000 0000 0000 0001
-32766	1111 1111 1111 1110	1000 0000 0000 0010
...	...	...
-3	1000 0000 0000 0011	1111 1111 1111 1101
-2	1000 0000 0000 0010	1111 1111 1111 1110
-1	1000 0000 0000 0001	1111 1111 1111 1111
0	0000 0000 0000 0000	0000 0000 0000 0000
1	0000 0000 0000 0001	0000 0000 0000 0001
2	0000 0000 0000 0010	0000 0000 0000 0010
...	...	...
32766	0111 1111 1111 1110	0111 1111 1111 1110

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

Над множеством целых чисел со знаком операция деления не определена, поскольку в общем случае ее результатом будет вещественное число. Однако допустимыми являются операции целочисленного деления и нахождения остатка от целочисленного деления (те, что немного ранее было обозначено div и mod). Точнее, значения обеих величин находятся одновременно в одной процедуре, которая в конечном счете сводится к последовательности вычитаний или, еще точнее, сложений с дополнительным кодом делителя. Примем обозначения: %%Z^{(1)}%% - делимое; %%Z^{(2)}%% -делитель; L - результат целочисленного деления %%Z^{(1)}%% на %%Z^{(2)}%%; R - остаток от целочисленного деления %%Z^{(1)}%% на %%Z^{(2)}%%. Эти величины связаны между собой довольно очевидным соотношением:

%%Z^{(1)}=L\cdot Z^{(2)}+R%%

из которого следует алгоритм нахождения значений %%L%% и %%R%% для заданных %%Z^{(1)}%% и %%Z^{(2)}%%; его блок-схема для положительных %%Z^{(1)}%% на %%Z^{(2)}%% представлена на рисунке:

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