Дополнительный код
Дополнительный код — способ, которым процессоры записывают отрицательные целые числа. Благодаря ему сложение и вычитание чисел со знаком и без знака выполняются одними и теми же командами, а 0xFF9C в 16-битной переменной означает −100.
Обновлено Редакция GAW
Дополнительный код (two's complement) — способ записи целых чисел со знаком, при котором отрицательное число −x в N битах хранится как 2N − x. Практически его получают так: инвертируют все биты модуля и прибавляют единицу. Старший бит показывает знак — 1 у отрицательных чисел, — но в отличие от прямого кода он входит в значение с весом −2N−1.
Примеры в 8 и 16 битах
| Число | 8 бит | 16 бит |
|---|---|---|
| 1 | 0x01 | 0x0001 |
| −1 | 0xFF | 0xFFFF |
| −100 | 0x9C | 0xFF9C |
| 127 | 0x7F | 0x007F |
| −128 | 0x80 | 0xFF80 |
Главное удобство дополнительного кода: сложение и вычитание выполняются той же схемой, что и для беззнаковых чисел, а результат правильный и для чисел со знаком, если он помещается в разрядность. Поэтому у процессора одна команда сложения, а знаковость учитывается только во флагах — например, во флаге переполнения V у AVR. Перевести число между десятичной, шестнадцатеричной и двоичной записью со знаком и без поможет конвертер чисел.
В языке C
Стандарт C11 допускает три представления знаковых целых — прямой, обратный и дополнительный код, — но типы точной ширины int8_t, int16_t, int32_t из stdint.h всегда хранятся в дополнительном коде (раздел 7.20.1.1). Переполнение знакового типа — неопределённое поведение, поэтому арифметику с возможным переполнением ведут в беззнаковых типах. Размеры типов на AVR и ARM — в статье «Язык C для микроконтроллеров», сдвиги знаковых чисел — в статье о битовых операциях. Дробные числа со знаком в целых переменных — это формат Q, тоже основанный на дополнительном коде.
Частые вопросы
Как получить дополнительный код отрицательного числа?
Инвертировать все биты модуля числа и прибавить единицу. Например, 100 в 16 битах — 0x0064, инверсия — 0xFF9B, плюс 1 — 0xFF9C, это и есть −100. То же самое даёт формула 2^N − x: 65 536 − 100 = 65 436 = 0xFF9C. Число −1 в любой разрядности — все единицы.
Какой диапазон у int8_t и int16_t?
N-битное число в дополнительном коде принимает значения от −2^(N−1) до 2^(N−1) − 1: int8_t — от −128 до 127, int16_t — от −32 768 до 32 767, int32_t — от −2 147 483 648 до 2 147 483 647. Отрицательных значений на одно больше, поэтому модуль самого маленького числа в том же типе не помещается.
Что такое переполнение в дополнительном коде?
Ситуация, когда результат сложения или вычитания выходит за диапазон типа: 127 + 1 в 8 битах даёт 0x80, то есть −128. Процессор отмечает это флагом: у AVR — флаг V (Two's Complement Overflow Flag). В языке C переполнение знакового типа — неопределённое поведение, поэтому полагаться на «заворачивание» нельзя.
Источники
- ISO/IEC 9899:201x (C11), Committee Draft N1570, April 2011 — 6.2.6.2 — представления знаковых целых (прямой, обратный и дополнительный код); 6.5p5 — переполнение знакового типа — неопределённое поведение; 7.20.1.1 — intN_t всегда в дополнительном коде
- Microchip. AVR Instruction Set Manual, DS40002198 — команда NEG — дополнительный код; флаг V — переполнение в дополнительном коде
Нашли ошибку?