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

Дополнительный код (англ. two’s complement) — это способ представления целых чисел со знаком в двоичной системе счисления, наиболее распространённый в современных компьютерах и цифровых устройствах. Он позволяет выполнять арифметические операции сложения и вычитания с использованием единого алгоритма, не требуя отдельной обработки знака числа. В дополнительном коде старший бит числа выполняет роль знакового разряда: 0 соответствует положительному числу, 1 — отрицательному.

История

Дополнительный код был разработан в середине XX века для упрощения конструкции арифметико-логических устройств (АЛУ) компьютеров. Ранние вычислительные машины, такие как ENIAC (1945 год), использовали прямой код для представления чисел, что требовало отдельных схем для сложения и вычитания. В 1940-х годах Джон фон Нейман предложил использовать дополнительный код в архитектуре EDVAC, чтобы унифицировать арифметические операции.

Первым коммерческим компьютером, реализовавшим дополнительный код, стал IBM 704 (1954 год). С тех пор этот метод стал стандартом для большинства процессоров, включая архитектуры x86, ARM, RISC-V и другие. В 1960-х годах дополнительный код был включён в систему команд PDP-8, а затем и в микропроцессоры Intel 4004 (1971 год).

Принцип работы

Представление чисел

В дополнительном коде числа записываются в двоичной системе с фиксированной разрядностью (например, 8, 16, 32 или 64 бита). Для положительных чисел дополнительный код совпадает с прямым кодом: старший бит равен 0, остальные биты содержат модуль числа. Для отрицательных чисел алгоритм преобразования состоит из двух шагов:

1. Взять модуль числа в двоичном виде (прямой код).
2. Инвертировать все биты (получить обратный код).
3. Прибавить 1 к полученному значению.

Например, для 8-битного представления числа −5:

• Прямой код числа 5: 00000101.
• Инвертирование: 11111010.
• Прибавление 1: 11111011 (дополнительный код числа −5).

Диапазон значений

Для n-битного представления в дополнительном коде диапазон возможных значений составляет от −2^(n−1) до 2^(n−1) − 1. Например:

• Для 8 бит: от −128 до 127.
• Для 16 бит: от −32768 до 32767.
• Для 32 бит: от −2147483648 до 2147483647.

Особенностью является асимметрия: количество отрицательных чисел на единицу больше, чем положительных, из-за того, что ноль имеет единственное представление (все биты равны 0). Минимальное отрицательное число (например, −128 для 8 бит) не имеет положительного аналога в том же диапазоне.

Арифметические операции

Сложение и вычитание в дополнительном коде выполняются по единому алгоритму: числа складываются как беззнаковые двоичные числа, а знак результата определяется автоматически. Если результат выходит за пределы диапазона, возникает переполнение (overflow), которое обнаруживается по несовпадению знакового бита результата со знаковыми битами операндов.

Вычитание реализуется как сложение с дополнительным кодом вычитаемого. Например, 5 − 3 = 5 + (−3):

• 5: 00000101.
• −3: 11111101.
• Сложение: 00000101 + 11111101 = 1 00000010 (старший бит отбрасывается, результат 2).

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

Сравнение с другими кодами

Прямой код

В прямом коде знак числа указывается отдельным битом (0 для плюса, 1 для минуса), а модуль записывается в двоичной форме. Недостатки:

• Ноль имеет два представления (00000000 и 10000000), что усложняет арифметику.
• Вычитание требует отдельных схем для заема.

Обратный код

Обратный код (англ. one’s complement) получается инвертированием всех бит прямого кода. Недостатки:

• Ноль также имеет два представления (00000000 и 11111111).
• При сложении требуется циклический перенос (end-around carry), что замедляет вычисления.

Дополнительный код лишён этих недостатков: ноль единственен, а сложение и вычитание выполняются одинаково.

Применение

Процессоры и микроконтроллеры

Дополнительный код используется во всех современных процессорах для представления целых чисел со знаком. Например, в архитектуре x86 команды ADD и SUB работают с числами в дополнительном коде. В микроконтроллерах, таких как AVR или ARM Cortex-M, арифметические операции также основаны на этом методе.

Языки программирования

В языках программирования, таких как C, C++, Java и Python, целые числа со знаком (типы int, short, long) хранятся в дополнительном коде. Стандарт C99 (ISO/IEC 9899:1999) явно разрешает дополнительный код как один из вариантов, а начиная с C23 (ISO/IEC 9899:2023) он стал единственным обязательным представлением для знаковых целых.

Цифровая обработка сигналов

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

Интересные факты

• В дополнительном коде минимальное отрицательное число (например, −128 для 8 бит) при инвертировании и прибавлении 1 даёт само себя, что является математическим курьёзом.
• Некоторые ранние компьютеры, такие как IBM 7090, использовали обратный код, но позже перешли на дополнительный из-за его эффективности.
• В языке программирования Java все целые типы (byte, short, int, long) используют дополнительный код, что гарантирует переносимость между платформами.

Критика

Несмотря на широкое распространение, дополнительный код имеет ограничения:

• Асимметрия диапазона (например, −128 представимо, а +128 — нет) может приводить к ошибкам при переполнении.
• Умножение и деление в дополнительном коде требуют более сложных алгоритмов, чем в прямом коде.
• Для чисел с плавающей запятой используется отдельный стандарт IEEE 754, не связанный с дополнительным кодом.

Источники

• Таненбаум Э. Архитектура компьютера. — 6-е изд. — СПб.: Питер, 2013. — 816 с.
• Паттерсон Д., Хеннесси Дж. Архитектура компьютера и проектирование компьютерных систем. — 5-е изд. — М.: Вильямс, 2018. — 1056 с.
• ISO/IEC 9899:2023. Information technology — Programming languages — C. — 2023.
• Intel 64 and IA-32 Architectures Software Developer’s Manual. — Vol. 1. — Intel Corporation, 2023.