Представление целых чисел: прямой код, код со сдвигом, дополнительный код — различия между версиями
Martoon (обсуждение | вклад) м (Увеличение размеров рисунков) |
Luxy (обсуждение | вклад) (Добавлен метод представления "дополнение до единицы". Убрана лишняя точка в конце конспекта.) |
||
Строка 47: | Строка 47: | ||
Из-за необходимости усложнять арифметические операции код со сдвигом для представления целых чисел используется не часто, но зато применяется для хранения порядка [[Представление вещественных чисел|вещественного числа]]. | Из-за необходимости усложнять арифметические операции код со сдвигом для представления целых чисел используется не часто, но зато применяется для хранения порядка [[Представление вещественных чисел|вещественного числа]]. | ||
− | == Дополнительный код == | + | == Дополнительный код (дополнение до единицы) == |
− | [[Файл: | + | [[Файл:Представление_чисел_дополнением_до_единицы.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 в дополнительный восьмибитный код. Прямой код модуля −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> 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>. | ||
Строка 71: | Строка 95: | ||
Недостатки: | Недостатки: | ||
− | *ряд положительных и отрицательных чисел несимметричен, но это не так важно: с помощью дополнительного кода выполнены гораздо более важные вещи, желаемые от способа представления целых чисел | + | *ряд положительных и отрицательных чисел несимметричен, но это не так важно: с помощью дополнительного кода выполнены гораздо более важные вещи, желаемые от способа представления целых чисел. |
==Список литературы== | ==Список литературы== |
Версия 22:38, 7 января 2014
Выбор способа хранения целых чисел в памяти компьютера — не такая тривиальная задача, как могло бы показаться на первый взгляд. Желательно, чтобы этот способ:
- не требовал усложнения архитектуры процессора для выполнения арифметических операций с отрицательными числами;
- не усложнял арифметические действия;
- хранил бы одинаковое количество положительных и отрицательных чисел.
Рассмотрим разные методы представления.
Содержание
Прямой код
При записи числа в прямом коде (sign-and-magnitude method) старший разряд (most significant bit) является знаковым разрядом (sign bit). Если его значение равно нулю, то число положительное, если единице — отрицательное. В остальных разрядах (которые называются цифровыми) записывается двоичное представление модуля числа. Например, число −5 в восьмибитном типе данных, использующем прямой код, будет выглядеть так: 10000101.
Таким способом в
-битовом типе данных можно представить диапазон чисел .Достоинства метода:
- получить прямой код числа достаточно просто.
Недостатки:
- выполнение арифметических операций с отрицательными числами требует усложнения архитектуры центрального процессора (например, для вычитания невозможно использовать сумматор, необходима отдельная схема для этого);
- существуют два нуля ("+0" и "−0"), из-за чего усложняется арифметическое сравнение.
Из-за этого прямой код используется очень редко.
Код со сдвигом
При использовании кода со сдвигом (excess-
, где ; также говорят biased representation) целочисленный отрезок от нуля до ( — количество бит) сдвигается влево на , а затем получившиеся на этом отрезке числа последовательно кодируются в порядке возрастания кодами от 000...0 до 111...1. Например, число −5 в восьмибитном типе данных, использующем код со сдвигом, превратится в −5 + 128 = 123, то есть будет выглядеть так: 01111011.По сути, при таком кодировании:
- к кодируемому числу прибавляют ;
- переводят получившееся число в двоичную систему исчисления.
Можно получить диапазон значений
.Достоинства метода:
- не требуется усложнение архитектуры процессора;
- нет проблемы двух нулей.
Недостатки:
- при арифметических операциях нужно учитывать смещение, то есть проделывать на одно действие больше (например, после «обычного» сложения двух чисел у результата будет двойное смещение, одно из которых необходимо вычесть);
- ряд положительных и отрицательных чисел несимметричен.
Из-за необходимости усложнять арифметические операции код со сдвигом для представления целых чисел используется не часто, но зато применяется для хранения порядка вещественного числа.
Дополнительный код (дополнение до единицы)
В качестве альтернативы представления целых чисел может использоваться код с дополнением до единицы (англ. Ones' complement).
Алгоритм получения кода числа:
- если число положительное, то в старший разряд (который является знаковым) записывается ноль, а далее записывается само число;
- если число отрицательное, то код получается инвертированием представления модуля числа (получается обратный код)
Пример: переведём число −13 в восьмибитный код (так оно будет храниться в типе данных unsigned char). Прямой код модуля −13 --- 00001101, инвертируем и получаем 11110010. Для получения из дополнительного кода самого числа достаточно инвертировать все разряды кода.
Таким способом можно получить диапазон значений
.Достоинства метода:
- Простое получение кода отрицательных чисел
Недостатки метода:
- выполнение арифметических операций с отрицательными числами требует усложнения архитектуры центрального процессора
- существуют два нуля ("+0" и "−0")
Дополнительный код (дополнение до двух)
Чаще всего для представления отрицательных чисел используется код с дополнением до двух (англ. two's complement).
Алгоритм получения дополнительного кода числа:
- если число положительное, то в старший разряд записывается ноль, далее записывается само число;
- если число отрицательное, то все биты модуля числа инвертируются, то есть все единицы меняются на нули, а нули — на единицы, к инвертированному числу прибавляется единица, далее к результату дописывается знаковый разряд, равный единице.
В качестве примера переведём число −5 в дополнительный восьмибитный код. Прямой код модуля −5 — 0000101, обратный — 1111010, прибавляем 1, получаем 1111011, приписываем 1 в качестве знакового разряда, в результате получаем 11111011.
Также дополнительный код отрицательного числа
, хранящегося в битах, равен . По сути, дополнительный код представляет собой дополнение до : так как в -разрядной арифметике (двоичная запись этого числа состоит из единицы и нулей, а в -разрядную ячейку помещаются только младших разрядов, то есть нулей), то верно равенство .Для получения из дополнительного кода самого числа нужно инвертировать все разряды кода и прибавить к нему единицу. Можно проверить правильность, сложив дополнительный код с самим числом: результат должен быть равен
. Переведём 11111011 обратно. Инвертируем — 00000100, прибавляем 1, получаем 00000101 — модуль исходного числа −5. Проверим: 11111011 + 00000101 = 100000000.Можно получить диапазон значений
.Достоинства метода:
- возможность заменить арифметическую операцию вычитания операцией сложения и сделать операции сложения одинаковыми для знаковых и беззнаковых типов данных, что существенно упрощает архитектуру процессора и увеличивает его быстродействие;
- нет проблемы двух нулей.
Недостатки:
- ряд положительных и отрицательных чисел несимметричен, но это не так важно: с помощью дополнительного кода выполнены гораздо более важные вещи, желаемые от способа представления целых чисел.
Список литературы
- Эндрю Таненбаум «Архитектура компьютера», 5-е изд., стр. 739—741