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

Выбор способа хранения целых чисел в памяти компьютера — не такая тривиальная задача, как могло бы показаться на первый взгляд. Желательно, чтобы этот способ:

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

Рассмотрим разные методы представления.

Прямой код

Нумерация двоичных чисел в прямом представлении

При записи числа в прямом коде (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"), из-за чего усложняется арифметическое сравнение.

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

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

Код со сдвигом. Как видно, нумерация зацикливается по модулю [math]2^n[/math]

При использовании кода со сдвигом (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].

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

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

Недостатки:

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

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

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

Нумерация двоичных чисел в представлении дополнения до двух. В отличии от кода со сдвигом, нулю соответствует код 00...000

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

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

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

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

Также дополнительный код отрицательного числа [math] A [/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].

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

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

Недостатки:

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

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

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

• Wikipedia: Signed number representations

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

• Wikipedia: Signedness