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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 9: Строка 9:
 
Недостатки:
 
Недостатки:
  
*существуют два нуля ("+0" и "-0"), из-за чего усложняется арифметическое сравнение;
+
*выполнение арифметических операций с отрицательными числами требует усложнения архитектуры центрального процессора (например, для вычитания невозможно использовать сумматор, необходима отдельная схема для этого);
*выполнение арифметических операций с отрицательными числами требует усложнения архитектуры центрального процессора (например, для вычитания невозможно использовать сумматор, необходима отдельная схема для этого).
+
*существуют два нуля ("+0" и "-0"), из-за чего усложняется арифметическое сравнение.
  
 
Из-за этого прямой код используется в основном только для записи неотрицательных чисел.
 
Из-за этого прямой код используется в основном только для записи неотрицательных чисел.
  
 
== Код со сдвигом ==
 
== Код со сдвигом ==
При использовании '''кода со сдвигом''' (''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.
+
При использовании '''кода со сдвигом''' (''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.
  
 
По сути, при таком кодировании:
 
По сути, при таком кодировании:
 +
 
*к кодируемому числу прибавляем <tex> 2^{n-1} </tex>;
 
*к кодируемому числу прибавляем <tex> 2^{n-1} </tex>;
 
*переводим получившееся число в двоичную систему исчисления.
 
*переводим получившееся число в двоичную систему исчисления.
Строка 25: Строка 26:
 
Достоинства метода:
 
Достоинства метода:
  
*нет проблемы двух нулей;
+
*не требуется усложнение архитектуры процессора;
*не требуется усложнение архитектуры процессора.
+
*нет проблемы двух нулей.
  
 
Недостатки:
 
Недостатки:
Строка 45: Строка 46:
 
Также дополнительный код отрицательного числа <tex> А </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> А </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>.
 +
 
 +
Можно получить диапазон значений <tex> [-2^{n-1}; 2^{n-1} - 1]</tex>.
 +
 
 +
Достоинства метода:
 +
 
 +
*возможность заменить арифметическую операцию вычитания операцией сложения и сделать операции сложения одинаковыми для знаковых и беззнаковых типов данных, что существенно упрощает архитектуру процессора и увеличивает его быстродействие;
 +
*нет проблемы двух нулей.
 +
 
 +
Недостатки:
 +
 
 +
*ряд положительных и отрицательных чисел несимметричен.
  
 
==Список литературы==
 
==Список литературы==
Строка 51: Строка 63:
  
 
*[http://en.wikipedia.org/wiki/Signed_number_representations Wikipedia: Signed number representations]
 
*[http://en.wikipedia.org/wiki/Signed_number_representations Wikipedia: Signed number representations]
 +
 +
*Эндрю Таненбаум «Архитектура компьютера», 5-е изд., стр. 739—741
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Представление информации]]
 
[[Категория: Представление информации]]

Версия 03:21, 19 октября 2011

Прямой код

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

Таким способом в [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.

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

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

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

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

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

Недостатки:

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

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

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

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

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

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

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

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

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

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

Недостатки:

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

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

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