Дополнительный код для представления целых чисел со знаком

Числа без знака

Представление положительных чисел в ЭВМ основано на выражении числа в виде суммы степеней двойки с коэффициентами, равными нулю или единице:

Ã=an2n+an-12n-1+...+a121+a020,

где коэффициенты  a0, an,... an могут принимать только два значения: 0 или 1.

Этот [конечный] ряд может быть однозначно определён набором коэффициентов ak={1|0}, k=0,1,... n (с соблюдением порядка их следования). Записывая набор коэффициентов в двоичное "слово", получаем традиционное "двоичное число", например, число 89  представляется в восьмиразрядном слове (байте) в виде двоичного числа так:

старшие <-----                         разряды слова                     -----> младшие

7 6 5 4 3 2 1 0
Представляемая разрядом степень двойки 27 26 25 24 23 22 21 20
89 = 0 1 0 1 1 0 0 1

В одном байте (в современной терминологии байт -- это 8-разрядное слово), используя все разряды, можно записать 256 целых чисел от 0 до 255. 

Такие числа в программировании называют "целое число без знака" или "слово" (Byte (1 байт), Word (2 байта)).

Числа со знаком

Если возникает необходимость выражать как положительные, так и отрицательные целые числа, то обычно прибегают к записи целых чисел в так называемом дополнительном коде. Смысл слова "дополнительный" станет ясен из дальнейшего. Такие числа в программировании называют "целое число со знаком" (Integer (2 байта), LongInt (4 байта), ShortInt (1 байт)).

Основной смысл использования дополнительного кода -- это одинаковость операций сложения и вычитания с положительными и отрицательными числами, что упрощает аппаратную реализацию и программирование ЭВМ. Более того, использование дополнительного кода также делает и сами операции сложения и вычитания одинаковыми.

Свойства дополнительного кода

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

1) отрицательные числа имеют значение старшего разряда слова ("знаковый разряд") 1, а положительные -- 0

2) целое число 0 (ноль) представляется словом, все разряды которого равны нулю ("машинный ноль"), причём существует только один "машинный ноль"

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

4) сумма положительного и равного ему по абсолютному значению отрицательного числа равна машинному нулю. 

Ещё свойства>>>

Свойства 2 и 4 можно рассматривать как определение дополнительного кода.

Таблица сложения одноразрядных двоичных чисел

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

+ 0 1
0 0 1
1 1 10*)

*) 10 означает единицу в переносе ("в уме"), то есть количество разрядов  в сумме стало на один разряд больше, чем в каждом из слагаемых

Таблица сложения двухразрядных двоичных чисел

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

Двухразрядных чисел всего четыре. Забегая вперёд, ранжируем все двухразрядные числа по нарастанию:

  Отрицательные Ноль Поло- житель- ные
Двоичная запись 10 11 00 01
Значение в десятичной записи -2 (минус два) -1(минус один) 0(ноль) +1(плюс один)

Из двух разрядов слова старший разряд "является знаком", а младший -- отображает "значение числа". На самом деле, в дополнительном коде знак не может быть отделён от абсолютной величины., Именно всё слово целиком отображает в дополнительном коде одновременно и знак и абсолютную величину числа. Просто у отрицательных чисел старший (знаковый) разряд непременно равен единице.

На основе таблицы сложения одноразрядных чисел составим полную таблицу сложения двухразрядных двоичных чисел:

+ 00 01 10 11
00 00 01 10 11
01 01 10***) 11 100**)
10 10 11 100*) 100*)
11 11 100**) 100*) 100**)

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

**) Подчёркнутый старший (знаковый) разряд означает перенос в этот разряд в пределах двухразрядной сетки

***)Перечёркнутое число означает переполнение

 

Рассматривая полученные результаты можно сделать вывод, что проведённое чуть выше ранжирование двухразрядных чисел, сделано правильно, то есть:

Можно также убедиться в выполнении заявленных выше свойств дополнительного кода.

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

Здравый смысл  Получено по таблице Перенос в знаковый разряд Перенос за пределы разрядной сетки Переполнение
"ноль"+"ноль"="ноль" 00+00=00 - - -
"ноль"+"один"="один" 00+01=01 - - -
"ноль"+"минус один"="минус один" 00+11=11 - -
"ноль"+"минус два"="минус два" 00+10=10 - - -
"один"+"один"="два" 01+01=1 + - !
"один"+"минус один"="ноль" 01+11=100 + + -
"один"+"минус два"="минус один" 01+10=11 - - -
"минус один"+"минус один"="минус два" 11+11=110 + + -
"минус один"+"минус два"="минус три" 11+10=101 - + !
"минус два"+"минус два"="минус четыре" 10+10=100 - + !

Ещё два свойства дополнительного кода

Можно сформулировать ещё два  свойства дополнительного кода: 

5) количество отрицательных чисел равно количеству неотрицательных чисел (включая ноль); положительных чисел на одно меньше, чем отрицательных1)  

6) чтобы получить равное по абсолютной величине число обратного знака, следует заменить все нули в слове на единицы, а все единицы на нули и к полученному числу прибавить единицу.

 

Количество всех (отрицательных и неотрицательных) чисел равно 2n, где n -- количество разрядов в слове (в примере -- 2 разряда). Отрицательных чисел всего 2n-1, а  положительных чисел, соответственно, 2n-1-1, плюс ещё одно особое число -- "машинный ноль". 

___________

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

 Перенос и переполнение

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

При сложении чисел в дополнительном коде почти в половине случаев возникает перенос за разрядную сетку, причём результат сложения оказывается правильным . Переносом за разрядную сетку называют случай, при котором результат сложения не помещается в разрядную сетку слова (в примере -- двухразрядную). Эти случаи при операциях с числами в дополнительном коде, вообще говоря, не приводят к ошибочному результату. Более того, на игнорировании переноса за разрядную сетку основаны замечательные свойства дополнительного кода.

При подробном рассмотрении таблицы сложения двухразрядных чисел можно отметить, что ошибочный результат происходит в случаях, когда имеет место перенос за разрядную сетку, а переноса в старший (знаковый) разряд в процессе операции не происходит. И наоборот, при сложении происходит перенос в старший (знаковый) разряд, а переноса за разрядную сетку не происходит. Обозначая С -- логическое значение высказывания "Произошёл перенос за разрядную сетку", а С3 -- логическое значение высказывания "Произошёл перенос в знаковый разряд" , можно выразить логическое значение Ov высказывания "Произошло переполнение" следующей формулой:

Ov=(C&С3)|С3)=C][С3

где обозначено: & -- операция "И", | -- операция "ИЛИ", ][ -- операция "Исключающее ИЛИ", черта сверху -- операция "НЕ". 

Программисту микроЭВМ семейства mcs-51 нет нужды анализировать два переноса, так как факт переполнения в этой архитектуре при каждом сложении (вычитании) диагностируется аппаратно по приведённой формуле и отображается специальным битом OV в слове состояния программы.

Почему "дополнительный"

Рассмотренный код чисел без знака называют дополнительным, поскольку равные по абсолютной величине, но противоположные по знаку числа (противоположные числа) дополняют друг друга до числа, равного количеству всех чисел, которые можно записать в данном количестве разрядов слова. Для двухразрядных слов это число равно 4 (1 00 в двоичном коде), при восьмиразрядных слов (байтов) -- это 256 (1 0000 0000) и т.д. Дополнительность противоположных чисел -- это и  есть свойство равенства машинному нулю суммы противоположных чисел (при отбрасывании переноса за разрядную сетку).

Часто дополнительный код путают с обратным кодом, в котором у противоположных чисел все разряды обращены (0 заменён на 1 и наоборот) . В архитектуре mcs-51 даже команда обращения всех битов регистра-аккумулятора называется CPL (compliment -- дополнить). На самом деле, обратный код отрицательных чисел отличается от дополнительного кода тех же чисел на единицу, и сумма противоположных чисел в обратном коде не равна машинному нулю.

Знак числа в дополнительном коде

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

Это понимание особенно важно при преобразовании числа со знаком, представленного, например, в одном байте (ShortInt) в двухбайтовый формат (Integer):

Исходное число ShortInt, равное минус 38 , представленное в одном байте:

1 1 0 1 1 0 1 0

Правильно преобразованное в двухбайтовый формат представление того же самого числа "минус 38" в двухбайтовом формате (Integer):

старший байт младший байт
1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0

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

Содержание>>>