Дополнительный код

2025-11-11T04:54:12Z

85.90.119.220: /* Преамбула */

'''Дополнительный код''' ({{lang-en|"two’s complement"}}, иногда ''"twos-complement"'') — наиболее распространённый способ представления [[отрицательное число|отрицательных целых чисел]] в [[компьютер]]ах. Он позволяет заменить операцию вычитания на операцию сложения и сделать операции сложения и вычитания одинаковыми для знаковых и {{d-|[[Беззнаковое число|беззнаковых]]}} чисел, что упрощает [[Архитектура компьютера|архитектуру ЭВМ]]. В англоязычной литературе «[[обратный код]]» (инверсия [[Прямой код|прямого кода]]) называют «первым дополнением» ({{lang-en|"ones' complement"}}), а «дополнительный код» называют «вторым дополнением» ({{lang-en|"two’s complement"}}).

Дополнительный код для отрицательного числа можно получить инвертированием его двоичного модуля (получается "первое дополнение") и прибавлением к инверсии единицы (получается "второе дополнение"), либо вычитанием числа из нуля (сразу получается "второе дополнение"). Дополнительный код для отрицательного числа определяется как величина, полученная вычитанием модуля числа из наибольшей степени двух (из <math>2^N</math> для <math>N</math>-битного второго дополнения).

== История ==
То, что отрицательные числа в дополнительном коде можно складывать на [[сумматор]]е, было известно ещё во времена [[Паскаль, Блез|Паскаля]], который и применил это свойство в своей [[Суммирующая машина Паскаля|суммирующей машине]] "Паскалина".

== Представление отрицательного числа в дополнительном коде ==
При записи числа в дополнительном коде старший разряд является знаковым. Если значение старшего разряда равно 0, то это значит, что в остальных разрядах записано положительное [[Двоичная система счисления|двоичное число]], совпадающее с [[прямой код (представление числа)|прямым кодом]].

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

Примеры:
{| class="standard"
! rowspan="2" align="center"| Десятичное представление
! align="center" colspan="3" | Двоичное представление (8 бит), код:
|-
! width="25%" align="center"| [[Прямой код|прямой]]
! width="25%" align="center"| [[Обратный код|обратный]]
! width="25%" align="center"| дополнительный
|-
| align="right"| 127       
| align="right" | <code>0111 1111</code>       
| align="right"| <code>0111 1111</code>       
| align="right"| <code>0111 1111</code>       
|-
| align="right"| 1       
| align="right"| <code>0000 0001</code>       
| align="right"| <code>0000 0001</code>       
| align="right"| <code>0000 0001</code>       
|-
| align="right"| 0       
| align="right"| <code>0000 0000</code>       
| align="right"| <code>0000 0000</code>       
| align="right"| <code>0000 0000</code>       
|-
| align="right"| −0       
| align="right"| <code>1000 0000</code>       
| align="right"| <code>1111 1111</code>       
| align="right"| —       
|-
| align="right"| −1       
| align="right"| <code>1000 0001</code>       
| align="right"| <code>1111 1110</code>       
| align="right"| <code>1111 1111</code>       
|-
| align="right"| −2       
| align="right"| <code>1000 0010</code>       
| align="right"| <code>1111 1101</code>       
| align="right"| <code>1111 1110</code>       
|-
| align="right"| −3       
| align="right"| <code>1000 0011</code>       
| align="right"| <code>1111 1100</code>       
| align="right"| <code>1111 1101</code>       
|-
| align="right"| −4       
| align="right"| <code>1000 0100</code>       
| align="right"| <code>1111 1011</code>       
| align="right"| <code>1111 1100</code>       
|-
| align="right"| −5       
| align="right"| <code>1000 0101</code>       
| align="right"| <code>1111 1010</code>       
| align="right"| <code>1111 1011</code>       
|-
| align="right"| −6       
| align="right"| <code>1000 0110</code>       
| align="right"| <code>1111 1001</code>       
| align="right"| <code>1111 1010</code>       
|-
| align="right"| −7       
| align="right"| <code>1000 0111</code>       
| align="right"| <code>1111 1000</code>       
| align="right"| <code>1111 1001</code>       
|-
| align="right"| −8       
| align="right"| <code>1000 1000</code>       
| align="right"| <code>1111 0111</code>       
| align="right"| <code>1111 1000</code>       
|-
| align="right"| −9       
| align="right"| <code>1000 1001</code>       
| align="right"| <code>1111 0110</code>       
| align="right"| <code>1111 0111</code>       
|-
| align="right"| −10       
| align="right"| <code>1000 1010</code>       
| align="right"| <code>1111 0101</code>       
| align="right"| <code>1111 0110</code>       
|-
| align="right"| −11       
| align="right"| <code>1000 1011</code>       
| align="right"| <code>1111 0100</code>       
| align="right"| <code>1111 0101</code>       
|-
| align="right"| −127       
| align="right"| <code>1111 1111</code>       
| align="right"| <code>1000 0000</code>       
| align="right"| <code>1000 0001</code>       
|-
| align="right"| −128       
| align="right"| —       
| align="right"| —       
| align="right"| <code>1000 0000</code>       
|}

== Дополнительный код в иной системе счисления ==
Тот же принцип можно использовать и в компьютерном представлении любой [[Система счисления|системы счисления]], например, для [[Десятичная система счисления|десятичных чисел]].

=== Преобразования на примере десятичной системы счисления<ref>{{Cite web |url=http://cs.fit.edu/~wds/classes/adm/Lectures/TensComplement.pdf |title=Florida Tech |access-date=2020-11-28 |archive-date=2016-10-08 |archive-url=https://web.archive.org/web/20161008132906/http://cs.fit.edu/~wds/classes/adm/Lectures/TensComplement.pdf |url-status=live }}</ref> ===

==== Положительное число ====
Изменение значений текущих разрядов числа не производится, но дописывается знаковый старший разряд, значение которого равно 0. Например число [+12'345] будет иметь следующее представление - [012'345]

==== Отрицательное число ====
Дописываем знаковый старший разряд, равный большей цифре данной [[Система счисления|системы счисления]], в нашем случае - это 9, а также изменяем остальные разряды по определённому правилу; пусть значение цифры каждого разряда будет представлено переменной <math>x</math>, кроме знакового, тогда представим следующий алгоритм действий:

# Присвоим переменной <math>x</math> новое значение, равное выражению <math>9 - x</math> (процесс получения обратного кода) - например отрицательное число [''-12345''] в прямом коде от старшего к младшему разряду будет иметь вид [9'''12345''], где <math>9</math> - знаковая цифра, а в обратном представлении кода будет иметь следующий вид - [9'87654].
# К результирующему числу прибавим <math>1</math>, так число [9'87654] (первое дополнение) будет иметь вид [987'655] (доп. код).
# Если возникла ситуация переноса разряда, в результате которого образовался новый разряд, то его (старший разряд) опускаем, а результирующее число считаем положительным. Результирующее положительное число будет одинаково представлено, как в прямом, так и в дополнительном коде. Например, имея возможность представить в таком виде отрицательный и положительный нуль, разберём их перевод в дополнительный код (1 знаковый и 4 дополнительных разряда):
#* [+0] в прямом коде [0'0000]. Первое и второе дополнения равны [0'0000].
#* [-0] в прямом коде [9'0000]. Первое дополнение - [9'9999]. При получении второго дополнения старший разряд числа [(1)0'0000] опускаем и получаем результирующее значение [0'0000], как у числа [+0].

Идея представления десятичного (как и любого другого) числа в дополнительном коде, идентична правилам для двоичной системы счисления и может использоваться в гипотетическом процессоре:
{| class="wikitable sortable"
! Привычное
представление
!Прямой
код
! Первое
дополнение
!Второе
дополнение
|-
|...
|...
|...
|...
|-
| +13
|0'0013
|0'0013
|0'0013
|-
| +12
|0'0012
|0'0012
|0'0012
|-
| +11
|0'0011
|0'0011
|0'0011
|-
| +10
|0'0010
|0'0010
|0'0010
|-
| +9
|0'0009
|0'0009
|0'0009
|-
| +8
|0'0008
|0'0008
|0'0008
|-
|...
|...
|...
|...
|-
| +2
|0'0002
|0'0002
|0'0002
|-
| +1
|0'0001
|0'0001
|0'0001
|-
| +0
|0'0000
|0'0000
|0'0000
|-
| -0
|9'0000
|9'9999
|0'0000
|-
| -1
|9'0001
|9'9998
|9'9999
|-
| -2
|9'0002
|9'9997
|9'9998
|-
| -3
|9'0003
|9'9996
|9'9997
|-
| -4
|9'0004
|9'9995
|9'9996
|-
|...
|...
|...
|...
|-
| -9
|9'0009
|9'9990
|9'9991
|-
| -10
|9'0010
|9'9989
|9'9990
|-
| -11
|9'0011
|9'9988
|9'9989
|-
| -12
|9'0012
|9'9987
|9'9988
|-
| -13
|9'0013
|9'9986
|9'9987
|}

=== Арифметика в дополнительном коде ===

==== Сложение и вычитание ====
Оба числа представляются в дополнительном коде. Дополнительный код обоих чисел имеет одинаковое количество разрядов. В данном представлении числа складываются.

Знаки разные: Если в процессе сложения образуется выходящий за пределы первоначальных чисел разряд, то он опускается. Результирующее значение считается '''положительным''', где прямой и дополнительный коды являются идентичными. Иначе — '''отрицательным''' в виде '''дополнительного кода'''.

Например:

* [1234] + [-78] → [0’1234] + [9’9922] = [(1)0’1156] = [1156].
* [-1234] + [78] → [9’8766] + [0’0078] = [9’8844] = [-1156].

Знаки одинаковые:

* Положительные числа. Разряд не опускается, результат положительный.
* Отрицательные числа. Разряд опускается, результат отрицательный в дополнительном коде.

Например:

* [1234] + [78] → [0’1234] + [0’0078] = [0’1312] = [1312].
* [-1234] + [-78] → [9’8766] + [9’9922] = [(1)9’8688] → (первое дополнение) [0’1311] → (второе дополнение или обычное представление) [-1312]. При переводе из дополнительного кода в обычное представление результирующее значение является абсолютным.

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

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

Для примера преобразуем отрицательное число <math>-5</math>, записанное в прямом коде, в дополнительный код.

Прямой код отрицательного числа <math>-5</math>: <code>1000 0101</code>

* Инвертируем все разряды числа, кроме знакового, получая таким образом [[Обратный код (представление числа)|обратный код]] (первое дополнение) отрицательного числа <math>-5</math>: <code>1111 1010</code>
* Добавим к результату <math>1</math>, получая таким образом дополнительный код (второе дополнение) отрицательного числа <math>-5</math>: <code>1111 1011</code>

=== Изменение знака числа ===
Для преобразования отрицательного числа <math>-5</math>, записанного в дополнительном коде, в положительное число <math>5</math>, записанное в прямом коде, используется похожий алгоритм:

* Инвертируем все разряды отрицательного числа <math>-5</math>, получая таким образом положительное число 4 в прямом коде: <code>0000 0100</code>
* Добавив к результату <math>1</math> получим положительное число <math>5</math> в прямом коде: <code>0000 0101</code>

И проверим, сложив получившееся записи <math>5</math> и <math>-5</math>: <code>0000 0101 + 1111 1011 = 0000 0000 ''(пятый и старше разряды выбрасываются)''</code>

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

В системе [[p-адическое число|''p''-адических чисел]] изменение знака числа осуществляется преобразованием числа в его дополнительный код. Например, если используется 5-ричная система счисления, то число, противоположное 00015 (110), равно 44445 (−110).

== Реализация алгоритма нахождения модуля для дополнительного кода ==
=== [[TurboBasic]] ===
<source lang="basic" line="1">
DEF FN TwosComplAbs%(a%)
IF a% < 0 THEN a% = NOT(a% - 1)
FN TwosComplAbs% = a%
END DEF
</source>

=== Pascal ===
<source lang="pascal" line="1">
function TwosComplAbs(a: integer): integer;
begin
if (a < 0) then TwosComplAbs := (not a) + 1
else TwosComplAbs := a;
end;
</source>

=== C/C++ ===
<source lang="cpp" line="1">
int twos_compl_abs(int a)
{
if (a < 0) a = (~a) + 1;
return a;
}
</source>

=== Реализация без ветвления ===
С помощью следующей формулы можно вычислить модуль числа без ветвления<ref>{{Cite web|url=https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs|title=Bit Twiddling Hacks|website=graphics.stanford.edu|access-date=2023-06-29|archive-date=2020-06-01|archive-url=https://web.archive.org/web/20200601123740/https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs|url-status=live}}</ref>:

: <math>|a| = (a\ \text{xor}\ (a\ \text{shr}\ (n-1))) - (a\ \text{shr}\ (n-1))</math>,

где: <math>\text{xor}</math> — Операция [[Исключающее «или»|исключающего "или"]]; 
<math>\text{shr}</math> — [[Битовый сдвиг#Арифметический (знаковый) сдвиг|Арифметический сдвиг]] вправо; 
<math>n</math> — Количество двоичных разрядов

Следующий код на языке [[Си (язык программирования)|Си]] вычисляет модуль по этой формуле:
<syntaxhighlight lang="c">
int32_t fastabs32(int32_t num)
{
int32_t mask = (num >> 31);
return ((num ^ mask) - mask);
}
</syntaxhighlight>

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

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

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

=== Недостатки ===

* Представление отрицательного числа визуально не читается по обычным правилам, для его восприятия нужен особый навык или дополнительные вычисления для приведения в обычный вид.
* В некоторых представлениях (например, [[двоично-десятичный код]]) или их составных частях (например, мантисса числа с [[плавающая запятая|плавающей запятой]]) дополнительное кодирование неудобно.
* Модуль наибольшего числа не равен модулю наименьшего числа. Например, для восьмибитного целого со знаком, максимальное число: 12710 = 011111112, минимальное число: -12810 = 100000002. Таким образом, не для любого числа существует противоположное. Операция изменения знака может потребовать дополнительной проверки.

== Пример программного преобразования ==
Если происходит чтение данных из файла или области памяти, где они хранятся в двоичном дополнительном коде (например, [[WAV|WAV файл]]), может оказаться необходимым преобразовать байты. Если данные хранятся в 8 битах, необходимо, чтобы значения 128-255 были отрицательными.
=== C# .NET / C style ===
<source lang="csharp">
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, потому что знаковый разряд - ноль.
</source>

== Расширение знака ==
'''Расширение знака''' (''[[Английский язык|англ.]] sign extension[[:en:Sign_extension|[en]]]'') — операция над двоичным числом, которая позволяет увеличить разрядность числа с сохранением знака и значения. Выполняется добавлением цифр со стороны старшего значащего разряда. Если число положительное (старший разряд равен 0), то добавляются нули, если отрицательное (старший разряд равен 1) — единицы.

=== Пример ===
'''Примечание''': ''Добавленные цифры подчёркнуты''
{| class="wikitable"
!Десятичное число
!Двоичное число
(8 разрядов)
!Двоичное число
(16 разрядов)
|-
|10
|<code>0000 1010</code>
|<code>0000 0000 0000 1010</code>
|-
|−15
|<code>1111 0001</code>
|<code>1111 1111 1111 0001</code>
|}

== См. также ==
* [[Обратный код (представление числа)|Обратный код]]
* [[Прямой код (представление числа)|Прямой код]]
* [[Целый тип]]
* [[Алгоритм Бута]] — специализированный алгоритм умножения для чисел в дополнительном коде

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

== Примечания ==
{{примечания}}

[[Категория:Компьютерная арифметика]]

wiki12 - Вклад [ru]

Дополнительный код