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

Прямой код

При записи числа в прямом коде (sign-and-magnitude method) старший разряд (most significant bit) является знаковым разрядом (sign bit). Если его значение равно нулю, то число положительное, если единице — отрицательное. В остальных разрядах (которые называются цифровыми) записывается двоичное представление модуля числа. Например, число -5 в восьмибитном типе данных, использующем прямой код, будет выглядеть так: 10000101.

Таким способом в [math] n [/math]-битовом типе данных можно представить диапазон чисел [math] [-2^{n-1} + 1; 2^{n-1} - 1] [/math].

Достоинства метода:

• получить прямой код числа достаточно просто.

Недостатки:

• выполнение арифметических операций с отрицательными числами требует усложнения архитектуры центрального процессора (например, для вычитания невозможно использовать сумматор, необходима отдельная схема для этого);
• существуют два нуля ("+0" и "-0"), из-за чего усложняется арифметическое сравнение.

Из-за этого прямой код используется в основном только для записи неотрицательных чисел.

Код со сдвигом

При использовании кода со сдвигом (excess-[math] K [/math], где [math] K = 2^{n-1} [/math]; также говорят biased representation) мы сдвигаем целочисленный отрезок от нуля до [math] 2^n [/math] ([math] n [/math] — количество бит) влево на [math] 2^{n-1} [/math], а затем последовательно кодируем получившееся на этом отрезке числа в порядке возрастания кодами от 000...0 до 111...1. Например, число -5 в восьмибитном типе данных, использующем код со сдвигом, превратится в -5 + 128 = 123, то есть будет выглядеть так: 01111011.

По сути, при таком кодировании:

• к кодируемому числу прибавляем [math] 2^{n-1} [/math];
• переводим получившееся число в двоичную систему исчисления.

Можно получить диапазон значений [math] [-2^{n-1}; 2^{n-1} - 1][/math].

Достоинства метода:

• не требуется усложнение архитектуры процессора;
• нет проблемы двух нулей.

Недостатки:

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

Из-за необходимости усложнять арифметические операции код со сдвигом используется не часто.

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

Чаще всего для представления отрицательных чисел используется дополнительный код (дополнение до двух, англ. two's complement).

Алгоритм получения дополнительного кода числа:

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

В качестве примера переведём число -5 в дополнительный восьмибитный код (так оно будет храниться в типе данных unsigned char). Прямой код модуля -5 — 0000101, обратный — 1111010, прибавляем 1, получаем 1111011, приписываем 1 в качестве знакового разряда, в результате получаем 11111011.

Также дополнительный код отрицательного числа [math] А [/math], хранящегося в [math] n [/math] битах, равен [math] 2^n - |A|[/math]. По сути, дополнительный код представляет собой дополнение [math] |A| [/math] до [math] 0 [/math]: так как в [math] n [/math]-разрядной арифметике [math] 2^{n} = 0 [/math] (двоичная запись этого числа состоит из единицы и [math] n [/math] нулей, а в [math] n [/math]-разрядную ячейку помещаются только [math] n [/math] младших разрядов, то есть [math] n [/math] нулей), то верно равенство [math] 2^n - |A| + |A| = 0 [/math].

Для получения из дополнительного кода самого числа нужно инвертировать все разряды кода и прибавить к нему единицу. Можно проверить правильность, сложив дополнительный код с самим числом: результат должен быть равен [math] 2^n [/math]. Переведём 11111011 обратно. Инвертируем — 00000100, прибавляем 1, получаем 00000101 — модуль исходного числа -5. Проверим: 11111011 + 00000101 = 100000000.

Можно получить диапазон значений [math] [-2^{n-1}; 2^{n-1} - 1] [/math].

Достоинства метода:

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

Недостатки:

• ряд положительных и отрицательных чисел несимметричен.

Беззнаковые типы данных

В современных компьютерах беззнаковые типы данных хранятся в прямом коде, а знаковые — в дополнительном. Это позволяет одинаково реализовывать арифметические операции для них. Однако из-за того, что в беззнаковом [math] n [/math]-битном типе данных можно представить диапазон [math] [0; 2^n - 1] [/math], а в [math] n [/math]-битном знаковом — [math] [-2^{n-1}; 2^{n-1} - 1] [/math], то может произойти переполнение.

Список литературы

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

• Wikipedia: Signed number representations

• Эндрю Таненбаум «Архитектура компьютера», 5-е изд., стр. 739—741

• Wikipedia: Signedness