Прямой способ кодирования целых чисел

Прямой, дополнительный и обратный коды

Прямой, дополнительный и обратный код числа (создан по запросу).

Далее идет калькулятор, который переводит введенное положительное или отрицательное целое число в двоичный код, а также выводит обратный код этого числа и его дополнительный код. Под калькулятором, как водится, немного теории.

Обновление: Из комментариев становится ясно, что люди не вполне понимают, что делает этот калькулятор. Точнее, что делал — применял алгоритм вычисления дополнительного кода к любому числу. Люди хотят, чтобы он им просто показывал дополнительный код числа. Ну хорошо — теперь при вводе положительного числа калькулятор показывает представление числа в двоичной форме, ибо для него нет обратного и дополнительного кода, а при вводе отрицательного показывает дополнительный и обратный код.

Прямой, дополнительный и обратный код

Прямой код числа это представление беззнакового двоичного числа. Если речь идет о машинной арифметике, то как правило на представление числа отводится определенное ограниченное число разрядов. Диапазон чисел, который можно представить числом разрядов n равен

Обратный код числа, или дополнение до единицы (one’s complement) это инвертирование прямого кода (поэтому его еще называют инверсный код). То есть все нули заменяются на единицы, а единицы на нули.

Дополнительный код числа, или дополнение до двойки (two’s complement) это обратный код, к младшему значащему разряду которого прибавлена единица

А теперь «зачем, зачем это все?» ©

А это все для удобной работы со знаками. Поскольку я все люблю понимать на примерах, рассказывать я тоже буду на примерах. Итак, предположим, что у нас 4 разряда для работы с двоичными числами. Представить таким образом можно 16 чисел — 0, 1, . 15
00 — 0000
.
15 — 1111

Но если нет знака, убогая получается арифметика. Нужно вводить знак. Чтобы никого не обидеть, половину диапазона отдадим положительным числам (8 чисел), половину — отрицательным (тоже 8 чисел). Ноль, что отличает машинную арифметику от обычной, мы отнесем в положительные числа (в обычной арифметике у нуля нет знака, если не ошибаюсь). Итого, в положительные числа попадают 0. 7, а в отрицательные -1, . -8.

Для различия положительных и отрицательных чисел выделяют старший разряд числа, который называется знаковым (sign bit)
0 в этом разряде говорит нам о том, что это положительное число, а 1 — отрицательное.

С положительными числами все вроде бы понятно, для их представления можно использовать прямой код
0 — 0000
1 — 0001
7 — 0111

А как представить отрицательные числа?

Вот для их представления как раз и используется дополнительный код.
То есть, -7 в дополнительном коде получается так
прямой код 7 = 0111
обратный код 7 = 1000
дополнительный код 7 = 1001

Обратим внимание на то, что прямой код 1001 представляет число 9, которое отстоит от числа -7 ровно на 16, или .
Или, что тоже самое, дополнительный код числа «дополняет» прямой код до , т.е. 7+9=16

И это оказалось очень удобно для машинных вычислений — при таком представлении отрицательного числа операции сложения и вычитания можно реализовать одной схемой сложения, при этом очень легко определять переполнение результата (когда для представления получившегося числа не хватает разрядности)

Пара примеров
7-3=4
0111 прямой код 7
1101 дополнительный код 3
0100 результат сложения 4

-1+7=6
1111 дополнительный код 1
0111 прямой код 7
0110 результат сложения 6

Что касается переполнения — оно определяется по двум последним переносам, включая перенос за старший разряд. При этом если переносы 11 или 00, то переполнения не было, а если 01 или 10, то было. При этом, если переполнения не было, то выход за разряды можно игнорировать.

Примеры где показаны переносы и пятый разряд

00111 прямой код 7
00001 прямой код 1
01110 переносы
01000 результат 8 — переполнение

Два последних переноса 01 — переполнение

-7+7=0
00111 прямой код 7
01001 дополнительный код 7
11110 переносы
10000 результат 16 — но пятый разряд можно игнорировать, реальный результат 0

Два последних переноса 11 з перенос в пятый разряд можно отбросить, оставшийся результат, ноль, арифметически корректен.
Опять же проверять на переполнение можно простейшей операцией XOR двух бит переносов.

Вот благодаря таким удобным свойствам дополнительный код это самый распространенный способ представления отрицательных чисел в машинной арифметике.

Источник

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

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

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

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

Содержание

Прямой код [ править ]

При записи числа в прямом коде (англ. Signed magnitude representation) старший разряд является знаковым разрядом. Если его значение равно нулю, то представлено положительное число или положительный ноль, если единице, то представлено отрицательное число или отрицательный ноль. В остальных разрядах (которые называются цифровыми) записывается двоичное представление модуля числа. Например, число [math] -5 [/math] в восьмибитном типе данных, использующем прямой код, будет выглядеть так: [math] 10000101 [/math] .

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

Достоинства представления чисел с помощью прямого кода [ править ]

1. Получить прямой код числа достаточно просто.
2. Из-за того, что [math]0[/math] обозначает [math]+[/math] , коды положительных чисел относительно беззнакового кодирования остаются неизменными.
3. Количество положительных чисел равно количеству отрицательных.

Недостатки представления чисел с помощью прямого кода [ править ]

1. Выполнение арифметических операций с отрицательными числами требует усложнения архитектуры центрального процессора (например, для вычитания невозможно использовать сумматор, необходима отдельная схема для этого).
2. Существуют два нуля: [math] -0 [/math] [math](100 \ldots 000) [/math] и [math] +0 [/math] [math] (000 \ldots 000) [/math] , из-за чего усложняется арифметическое сравнение.

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

Код со сдвигом [ править ]

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

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

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

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

Достоинства представления чисел с помощью кода со сдвигом [ править ]

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

Недостатки представления чисел с помощью кода со сдвигом [ править ]

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

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

Дополнительный код (дополнение до единицы) [ править ]

В качестве альтернативы представления целых чисел может использоваться код с дополнением до единицы (англ. Ones’ complement).

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

• если число положительное, то в старший разряд (который является знаковым) записывается ноль, а далее записывается само число;
• если число отрицательное, то код получается инвертированием представления модуля числа (получается обратный код);
• если число является нулем, то его можно представить двумя способами: [math] +0 [/math] [math](000 \ldots 000) [/math] или [math] -0 [/math] [math] (111 \ldots 111) [/math] .

Пример: переведём число [math] -13 [/math] в двоичный восьмибитный код. Прямой код модуля [math] -13 [/math] : [math] 00001101 [/math] , инвертируем и получаем [math] 11110010 [/math] . Для получения из дополнительного кода самого числа достаточно инвертировать все разряды кода.

Таким способом можно получить диапазон значений [math] [-2^+1; 2^ — 1] [/math] .

Достоинства представления чисел с помощью кода с дополнением до единицы [ править ]

1. Простое получение кода отрицательных чисел.
2. Из-за того, что [math]0[/math] обозначает [math]+[/math] , коды положительных чисел относительно беззнакового кодирования остаются неизменными.
3. Количество положительных чисел равно количеству отрицательных.

Недостатки представления чисел с помощью кода с дополнением до единицы [ править ]

1. Выполнение арифметических операций с отрицательными числами требует усложнения архитектуры центрального процессора.
2. Существуют два нуля: [math] +0 [/math] и [math] -0 [/math] .

Дополнительный код (дополнение до двух) [ править ]

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

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

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

В качестве примера переведём число [math] -5 [/math] в дополнительный восьмибитный код. Прямой код модуля [math] -5 [/math] : [math] 0000101 [/math] , обратный — [math] 1111010 [/math] , прибавляем [math] 1 [/math] , получаем [math] 1111011 [/math] , приписываем [math] 1 [/math] в качестве знакового разряда, в результате получаем [math] 11111011 [/math] .

Также дополнительный код отрицательного числа [math] A [/math] , хранящегося в [math] n [/math] битах, равен [math] 2^n — |A| [/math] . По сути, дополнительный код представляет собой дополнение [math] |A| [/math] до [math] 0 [/math] : так как в [math] n [/math] -разрядной арифметике [math] 2^ = 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] . Переведём [math] 11111011 [/math] обратно. Инвертируем — [math] 00000100 [/math] , прибавляем [math] 1 [/math] , получаем [math] 00000101 [/math] — модуль исходного числа [math] -5 [/math] . Проверим: [math] 11111011 + 00000101 = 100000000 [/math] .

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

Длинная арифметика для чисел, представленных с помощью кода с дополнением до двух [ править ]

Дополнительный код также удобно использовать для вычислений в длинной арифметике, особенно для операций сложения и вычитания. Это операции удобно выполнять с числами одинаковой длины, поэтому в старшие разряды меньшего числа нужно поместить нули (если число положительно) или единицы (если число отрицательно). Тогда числа будут выглядеть следующим образом: в старших разрядах бесконечное число нулей (единиц), а в младших разрядах уже встречаются и нули, и единицы, которые кодируют само число, а не знак. Удобство заключается в том, что нам не обязательно проделывать операции сложения с каждой парой бит, если мы знаем, что на этом отрезке в числах стоят либо единицы, либо нули. Таким образом, на этом отрезке в получившемся числе тоже будут либо только единицы, либо только нули. Операцию сложения можно выполнить только один раз для старших битов, таким образом мы узнаем знак получившегося числа. Вычитание тоже выполняется просто: инвертируем число, прибавляем один и получаем это число с минусом, затем просто делаем сложение. Однако умножение с числами, представленными дополнительным кодом, выполнять не всегда оптимально: алгоритм либо слишком медленный (наивный алгоритм работает за [math]O(n^2)[/math] ), либо слишком сложный. Лучше для умножение использовать прямой код (бит под знак). Тогда можно числа перевести в десятичную систему счисления, выполнить быстрое преобразование Фурье за [math]O(n \log n)[/math] , затем перевести их обратно в двоичную. Обычно такой алгоритм работает быстрее, чем выполнение операции напрямую с двоичными числами. Для деления обычно тоже лучше использовать прямой код.

Достоинства представления чисел с помощью кода с дополнением до двух [ править ]

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

Недостатки представления чисел с помощью кода с дополнением до двух [ править ]

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

Несмотря на недостатки, дополнение до двух в современных вычислительных системах используется чаще всего.

Источник