Дополнительный код (представление числа)

Дополнительный код (англ. two’s complement, иногда twos-complement) — наиболее распространённый способ представления отрицательных целых чисел в компьютерах. Он позволяет заменить операцию вычитания на операцию сложения и сделать операции сложения и вычитания одинаковыми для знаковых и чисел, чем упрощает архитектуру ЭВМ. В англоязычной литературе обратный код называют первым дополнением, а дополнительный код называют вторым дополнением.

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

Дополнительный код (второе дополнение) двоичного числа получается добавлением 1 к младшему значащему разряду его первого дополнения.

Второе дополнение двоичного числа определяется как величина, полученная вычитанием числа из наибольшей степени двух (из 2^N для N-битного второго дополнения).

Представление отрицательного числа в дополнительном коде

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

Двоичное 8-разрядное число со знаком в дополнительном коде может представлять любое целое в диапазоне от −128 до +127. Если старший разряд равен нулю, то наибольшее целое число, которое может быть записано в оставшихся 7 разрядах, равно <math>2^7-1=127</math>.

Примеры:

Десятичное представление	Двоичное представление (8 бит)
	прямой	обратный	дополнительный
127	0111 1111	0111 1111	0111 1111
1	0000 0001	0000 0001	0000 0001
0	0000 0000	0000 0000	0000 0000
-0	1000 0000	1111 1111	---
-1	1000 0001	1111 1110	1111 1111
-2	1000 0010	1111 1101	1111 1110
-3	1000 0011	1111 1100	1111 1101
-4	1000 0100	1111 1011	1111 1100
-5	1000 0101	1111 1010	1111 1011
-6	1000 0110	1111 1001	1111 1010
-7	1000 0111	1111 1000	1111 1001
-8	1000 1000	1111 0111	1111 1000
-9	1000 1001	1111 0110	1111 0111
-10	1000 1010	1111 0101	1111 0110
-11	1000 1011	1111 0100	1111 0101
-127	1111 1111	1000 0000	1000 0001
-128	---	---	1000 0000

Дополнительный код для десятичных чисел

Тот же принцип можно использовать и в компьютерном представлении десятичных чисел: для каждого разряда цифра X заменяется на 9−X, и к получившемуся числу добавляется 1. Например, при использовании четырёхзначных чисел −0081 заменяется на 9919 (9919+0081=0000, пятый разряд выбрасывается).

При применении той же идеи к привычной 10-тичной системе счисления получится (например, для гипотетического процессора, использующего 10-тичную систему счисления):

10-тичная система счисления ("обычная" запись)	10-тичная система счисления, дополнительный код
...	...
13	0013
12	0012
11	0011
10	0010
9	0009
8	0008
...	...
2	0002
1	0001
0	0000
-1	9999
-2	9998
-3	9997
-4	9996
...	...
-9	9991
-10	9990
-11	9989
-12	9988
...	...

Преобразование в дополнительный код

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

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

Пример. Преобразуем отрицательное число −5, записанное в прямом коде, в дополнительный код. Прямой код отрицательного числа -5:

1101 

Инвертируем все разряды числа, кроме знакового, получая таким образом обратный код (первое дополнение) отрицательного числа -5:

1010

Добавим к результату 1, получая таким образом дополнительный код (второе дополнение) отрицательного числа -5:

1011

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

1011

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

0100

Добавив к результату 1 получим положительное число 5 в прямом коде:

0101

И проверим, сложив с дополнительным кодом

 0101 + 1011 = 10000, пятый разряд выбрасывается.

p-адические числа

В системе p-адических чисел изменение знака числа осуществляется преобразованием числа в его дополнительный код. Например, если используется 5-ричная система счисления, то число, противоположное 0001₅ (1₁₀), равно 4444₅ (−1₁₀).

Реализация алгоритма преобразования в дополнительный код (для 8-битных чисел)

Pascal

if a<0
  then a:=((not a) or 128) + 1;

C/C++

int convert(int a) {
  if (a < 0)
    a = ( ~-a|128 ) + 1;
  return a;
}

Преимущества и недостатки

Преимущества

• Общие инструкции (процессора) для сложения, вычитания и левого сдвига для знаковых и беззнаковых чисел (различия только в арифметических флагах, которые нужно проверять для контроля переполнения в результате).
• Отсутствие числа «минус ноль».

Недостатки

• Представление отрицательного числа не читается по обычным правилам, для его восприятия нужен особый навык или вычисления
• В некоторых представлениях (например, двоично-десятичный код) или их составных частях (например, мантисса числа с плавающей запятой) дополнительное кодирование неудобно
• Модуль наибольшего числа не равен модулю наименьшего числа. Например, для восьмибитного целого со знаком, максимальное число: 127₁₀ = 01111111₂, минимальное число: -128₁₀ = 10000000₂. Соответственно, не для любого числа существует противоположное. Операция изменения знака может потребовать дополнительной проверки.

Пример программного преобразования

Если происходит чтение данных из файла или области памяти, где они хранятся в двоичном дополнительном коде (например, файл WAVE), может оказаться необходимым преобразовать байты. Если данные хранятся в 8 битах, необходимо, чтобы значения 128-255 были отрицательными.

C# .NET / C style

byte b1 = 254; //11111110 (бинарное)
byte b2 = 121; //01111001 (бинарное)
byte c = 1<<(sizeof(byte)*8-1);  //2 возводится в степень 7. Результат: 10000000 (бинарное)
byte b1Conversion=(c ^ b1) - c;  //Результат: -2. А фактически, двоичный дополнительный код.
byte b2Conversion=(c ^ b2) - c;  //Результат остаётся 121, потому что знаковый разряд - ноль.

Расширение знака

Расширение знака (англ. Sign extension) — операция над двоичным числом, которая позволяет увеличить разрядность числа с сохранением знака и значения. Выполняется добавлением цифр со стороны старшего значащего разряда. Если число положительное (старший разряд равен 0), то добавляются нули, если отрицательное (старший разряд равен 1) — единицы.

Пример

Десятичное число	Двоичное число (8 разрядов)	Двоичное число (16 разрядов)
10	0000 1010	0000 0000 0000 1010
−15	1111 0001	1111 1111 1111 0001

См. также

• Обратный код
• Прямой код
• Целый тип
• Алгоритм Бута — специализированный алгоритм умножения для чисел в дополнительном коде

Литература

• Behrooz Parhami. 2.3. Complement Representation, 2.4. Two's- and 1's-complement numbers // [www.ece.ucsb.edu/~parhami/text_comp_arit.htm Computer Arithmetic: Algorithms and Hardware Designs]. — New York: Oxford University Press, 2000. — P. 22-27. — 510 p. — ISBN 0-19-512583-5.
• Самофалов К.Г., Романкевич А.М., Валуйский В.Н., Каневский Ю.С., Пиневич М.М. Прикладная теория цифровых автоматов. — К.: Вища школа, 1987. — 375 с.

Отрывок, характеризующий Дополнительный код (представление числа)

– От тебя блохи, стрекозы, кузнецы, – отвечал шут.
– Боже мой, Боже мой, всё одно и то же. Ах, куда бы мне деваться? Что бы мне с собой сделать? – И она быстро, застучав ногами, побежала по лестнице к Фогелю, который с женой жил в верхнем этаже. У Фогеля сидели две гувернантки, на столе стояли тарелки с изюмом, грецкими и миндальными орехами. Гувернантки разговаривали о том, где дешевле жить, в Москве или в Одессе. Наташа присела, послушала их разговор с серьезным задумчивым лицом и встала. – Остров Мадагаскар, – проговорила она. – Ма да гас кар, – повторила она отчетливо каждый слог и не отвечая на вопросы m me Schoss о том, что она говорит, вышла из комнаты. Петя, брат ее, был тоже наверху: он с своим дядькой устраивал фейерверк, который намеревался пустить ночью. – Петя! Петька! – закричала она ему, – вези меня вниз. с – Петя подбежал к ней и подставил спину. Она вскочила на него, обхватив его шею руками и он подпрыгивая побежал с ней. – Нет не надо – остров Мадагаскар, – проговорила она и, соскочив с него, пошла вниз.
Как будто обойдя свое царство, испытав свою власть и убедившись, что все покорны, но что всё таки скучно, Наташа пошла в залу, взяла гитару, села в темный угол за шкапчик и стала в басу перебирать струны, выделывая фразу, которую она запомнила из одной оперы, слышанной в Петербурге вместе с князем Андреем. Для посторонних слушателей у ней на гитаре выходило что то, не имевшее никакого смысла, но в ее воображении из за этих звуков воскресал целый ряд воспоминаний. Она сидела за шкапчиком, устремив глаза на полосу света, падавшую из буфетной двери, слушала себя и вспоминала. Она находилась в состоянии воспоминания.
Соня прошла в буфет с рюмкой через залу. Наташа взглянула на нее, на щель в буфетной двери и ей показалось, что она вспоминает то, что из буфетной двери в щель падал свет и что Соня прошла с рюмкой. «Да и это было точь в точь также», подумала Наташа. – Соня, что это? – крикнула Наташа, перебирая пальцами на толстой струне.
– Ах, ты тут! – вздрогнув, сказала Соня, подошла и прислушалась. – Не знаю. Буря? – сказала она робко, боясь ошибиться.
«Ну вот точно так же она вздрогнула, точно так же подошла и робко улыбнулась тогда, когда это уж было», подумала Наташа, «и точно так же… я подумала, что в ней чего то недостает».
– Нет, это хор из Водоноса, слышишь! – И Наташа допела мотив хора, чтобы дать его понять Соне.
– Ты куда ходила? – спросила Наташа.
– Воду в рюмке переменить. Я сейчас дорисую узор.
– Ты всегда занята, а я вот не умею, – сказала Наташа. – А Николай где?
– Спит, кажется.
– Соня, ты поди разбуди его, – сказала Наташа. – Скажи, что я его зову петь. – Она посидела, подумала о том, что это значит, что всё это было, и, не разрешив этого вопроса и нисколько не сожалея о том, опять в воображении своем перенеслась к тому времени, когда она была с ним вместе, и он влюбленными глазами смотрел на нее.
«Ах, поскорее бы он приехал. Я так боюсь, что этого не будет! А главное: я стареюсь, вот что! Уже не будет того, что теперь есть во мне. А может быть, он нынче приедет, сейчас приедет. Может быть приехал и сидит там в гостиной. Может быть, он вчера еще приехал и я забыла». Она встала, положила гитару и пошла в гостиную. Все домашние, учителя, гувернантки и гости сидели уж за чайным столом. Люди стояли вокруг стола, – а князя Андрея не было, и была всё прежняя жизнь.
– А, вот она, – сказал Илья Андреич, увидав вошедшую Наташу. – Ну, садись ко мне. – Но Наташа остановилась подле матери, оглядываясь кругом, как будто она искала чего то.
– Мама! – проговорила она. – Дайте мне его , дайте, мама, скорее, скорее, – и опять она с трудом удержала рыдания.
Она присела к столу и послушала разговоры старших и Николая, который тоже пришел к столу. «Боже мой, Боже мой, те же лица, те же разговоры, так же папа держит чашку и дует точно так же!» думала Наташа, с ужасом чувствуя отвращение, подымавшееся в ней против всех домашних за то, что они были всё те же.
После чая Николай, Соня и Наташа пошли в диванную, в свой любимый угол, в котором всегда начинались их самые задушевные разговоры.


– Бывает с тобой, – сказала Наташа брату, когда они уселись в диванной, – бывает с тобой, что тебе кажется, что ничего не будет – ничего; что всё, что хорошее, то было? И не то что скучно, а грустно?
– Еще как! – сказал он. – У меня бывало, что всё хорошо, все веселы, а мне придет в голову, что всё это уж надоело и что умирать всем надо. Я раз в полку не пошел на гулянье, а там играла музыка… и так мне вдруг скучно стало…
– Ах, я это знаю. Знаю, знаю, – подхватила Наташа. – Я еще маленькая была, так со мной это бывало. Помнишь, раз меня за сливы наказали и вы все танцовали, а я сидела в классной и рыдала, никогда не забуду: мне и грустно было и жалко было всех, и себя, и всех всех жалко. И, главное, я не виновата была, – сказала Наташа, – ты помнишь?
– Помню, – сказал Николай. – Я помню, что я к тебе пришел потом и мне хотелось тебя утешить и, знаешь, совестно было. Ужасно мы смешные были. У меня тогда была игрушка болванчик и я его тебе отдать хотел. Ты помнишь?
– А помнишь ты, – сказала Наташа с задумчивой улыбкой, как давно, давно, мы еще совсем маленькие были, дяденька нас позвал в кабинет, еще в старом доме, а темно было – мы это пришли и вдруг там стоит…
– Арап, – докончил Николай с радостной улыбкой, – как же не помнить? Я и теперь не знаю, что это был арап, или мы во сне видели, или нам рассказывали.
– Он серый был, помнишь, и белые зубы – стоит и смотрит на нас…
– Вы помните, Соня? – спросил Николай…
– Да, да я тоже помню что то, – робко отвечала Соня…
– Я ведь спрашивала про этого арапа у папа и у мама, – сказала Наташа. – Они говорят, что никакого арапа не было. А ведь вот ты помнишь!
– Как же, как теперь помню его зубы.
– Как это странно, точно во сне было. Я это люблю.
– А помнишь, как мы катали яйца в зале и вдруг две старухи, и стали по ковру вертеться. Это было, или нет? Помнишь, как хорошо было?
– Да. А помнишь, как папенька в синей шубе на крыльце выстрелил из ружья. – Они перебирали улыбаясь с наслаждением воспоминания, не грустного старческого, а поэтического юношеского воспоминания, те впечатления из самого дальнего прошедшего, где сновидение сливается с действительностью, и тихо смеялись, радуясь чему то.
Соня, как и всегда, отстала от них, хотя воспоминания их были общие.
Соня не помнила многого из того, что они вспоминали, а и то, что она помнила, не возбуждало в ней того поэтического чувства, которое они испытывали. Она только наслаждалась их радостью, стараясь подделаться под нее.
Она приняла участие только в том, когда они вспоминали первый приезд Сони. Соня рассказала, как она боялась Николая, потому что у него на курточке были снурки, и ей няня сказала, что и ее в снурки зашьют.
– А я помню: мне сказали, что ты под капустою родилась, – сказала Наташа, – и помню, что я тогда не смела не поверить, но знала, что это не правда, и так мне неловко было.
Во время этого разговора из задней двери диванной высунулась голова горничной. – Барышня, петуха принесли, – шопотом сказала девушка.
– Не надо, Поля, вели отнести, – сказала Наташа.
В середине разговоров, шедших в диванной, Диммлер вошел в комнату и подошел к арфе, стоявшей в углу. Он снял сукно, и арфа издала фальшивый звук.
– Эдуард Карлыч, сыграйте пожалуста мой любимый Nocturiene мосье Фильда, – сказал голос старой графини из гостиной.
Диммлер взял аккорд и, обратясь к Наташе, Николаю и Соне, сказал: – Молодежь, как смирно сидит!
– Да мы философствуем, – сказала Наташа, на минуту оглянувшись, и продолжала разговор. Разговор шел теперь о сновидениях.
Диммлер начал играть. Наташа неслышно, на цыпочках, подошла к столу, взяла свечу, вынесла ее и, вернувшись, тихо села на свое место. В комнате, особенно на диване, на котором они сидели, было темно, но в большие окна падал на пол серебряный свет полного месяца.
– Знаешь, я думаю, – сказала Наташа шопотом, придвигаясь к Николаю и Соне, когда уже Диммлер кончил и всё сидел, слабо перебирая струны, видимо в нерешительности оставить, или начать что нибудь новое, – что когда так вспоминаешь, вспоминаешь, всё вспоминаешь, до того довоспоминаешься, что помнишь то, что было еще прежде, чем я была на свете…
– Это метампсикова, – сказала Соня, которая всегда хорошо училась и все помнила. – Египтяне верили, что наши души были в животных и опять пойдут в животных.
– Нет, знаешь, я не верю этому, чтобы мы были в животных, – сказала Наташа тем же шопотом, хотя музыка и кончилась, – а я знаю наверное, что мы были ангелами там где то и здесь были, и от этого всё помним…
– Можно мне присоединиться к вам? – сказал тихо подошедший Диммлер и подсел к ним.
– Ежели бы мы были ангелами, так за что же мы попали ниже? – сказал Николай. – Нет, это не может быть!
– Не ниже, кто тебе сказал, что ниже?… Почему я знаю, чем я была прежде, – с убеждением возразила Наташа. – Ведь душа бессмертна… стало быть, ежели я буду жить всегда, так я и прежде жила, целую вечность жила.
– Да, но трудно нам представить вечность, – сказал Диммлер, который подошел к молодым людям с кроткой презрительной улыбкой, но теперь говорил так же тихо и серьезно, как и они.
– Отчего же трудно представить вечность? – сказала Наташа. – Нынче будет, завтра будет, всегда будет и вчера было и третьего дня было…
– Наташа! теперь твой черед. Спой мне что нибудь, – послышался голос графини. – Что вы уселись, точно заговорщики.
– Мама! мне так не хочется, – сказала Наташа, но вместе с тем встала.
Всем им, даже и немолодому Диммлеру, не хотелось прерывать разговор и уходить из уголка диванного, но Наташа встала, и Николай сел за клавикорды. Как всегда, став на средину залы и выбрав выгоднейшее место для резонанса, Наташа начала петь любимую пьесу своей матери.