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

2014-01-07T19:38:13Z

Luxy: Добавлен метод представления "дополнение до единицы". Убрана лишняя точка в конце конспекта.

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

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

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

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

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

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

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

Недостатки:

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

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

== Код со сдвигом ==
[[Файл:Представление двоичных чисел в коде со сдвигом.jpg|230px|thumb|right|Код со сдвигом. Как видно, двоичное представление зациклено по модулю <tex dpi="100">1000..000_{(2)}</tex> (<tex>n</tex> нулей)]]
При использовании '''кода со сдвигом''' (''excess-''<tex> K </tex>, где <tex> K = 2^{n-1} </tex>; также говорят ''biased representation'') целочисленный отрезок от нуля до <tex> 2^n </tex> (<tex> n </tex> — количество бит) сдвигается влево на <tex> 2^{n-1} </tex>, а затем получившиеся на этом отрезке числа последовательно кодируются в порядке возрастания кодами от 000...0 до 111...1. Например, число −5 в восьмибитном типе данных, использующем код со сдвигом, превратится в −5 + 128 = 123, то есть будет выглядеть так: 01111011.

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

*к кодируемому числу прибавляют <tex> 2^{n-1} </tex>;
*переводят получившееся число в двоичную систему исчисления.

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

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

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

Недостатки:

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

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

== Дополнительный код (дополнение до единицы) ==
[[Файл:Представление_чисел_дополнением_до_единицы.jpg|230px|thumb|right|Нумерация двоичных чисел в представлении c дополнением до единицы. В отличии от кода со сдвигом, нулю соответствуют коды 00...000 и 11...111]]
В качестве альтернативы представления целых чисел может использоваться код с дополнением до единицы (англ. ''Ones' complement'').

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

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

Пример: переведём число −13 в восьмибитный код (так оно будет храниться в типе данных unsigned char). Прямой код модуля −13 --- 00001101, инвертируем и получаем 11110010.
Для получения из дополнительного кода самого числа достаточно инвертировать все разряды кода.

Таким способом можно получить диапазон значений <tex> [-2^{n-1}+1; 2^{n-1} - 1] </tex>.

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

*Простое получение кода отрицательных чисел

Недостатки метода:

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

*существуют два нуля ("+0" и "−0")

== Дополнительный код (дополнение до двух) ==
[[Файл:Представление двоичных чисел в дополнительном коде.jpg|230px|thumb|right|Нумерация двоичных чисел в представлении c дополнением до двух.]]
Чаще всего для представления отрицательных чисел используется код с дополнением до двух (англ. ''two's complement'').

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

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

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

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

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

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

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

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

Недостатки:

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

==Список литературы==
*[http://ru.wikipedia.org/wiki/%D0%94%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%B4_%28%D0%BF%D1%80%D0%B5%D0%B4%D1%81%D1%82%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0%29 Википедия: Дополнительный код (представление числа)]

*[http://en.wikipedia.org/wiki/Signed_number_representations Wikipedia: Signed number representations]

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

*[http://en.wikipedia.org/wiki/Signedness Wikipedia: Signedness]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Представление информации]]

Файл:Представление чисел дополнением до единицы.jpg

2014-01-07T19:30:22Z

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

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

Викиконспекты - Вклад участника [ru]

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

Файл:Представление чисел дополнением до единицы.jpg