Знаковые представления чисел

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Представления подписанных чисел»  -  новости  · газеты  · книги  · ученый  · JSTOR ( апрель 2013 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

В математике отрицательные числа в любом основании обозначаются префиксом со знаком минус ("-"). Однако в компьютерном оборудовании числа представлены только как последовательности битов без дополнительных символов. Четыре наиболее известные способами расширения двоичной системы счисления для представления чисел со знаком, являются: знак-и магнитуды , обратный кода , дополнение до двух , и смещение двоичных . Некоторые из альтернативных методов используют неявные знаки вместо явных, такие как отрицательный двоичный код, с использованием основания -2 . Соответствующие методы могут быть разработаны для других баз., будь то положительные, отрицательные, частичные или другие разработки по таким темам.

Не существует окончательного критерия, по которому любое из представлений является универсально превосходящим. Для целых чисел представление, используемое в большинстве современных вычислительных устройств, является дополнением до двух, хотя в мэйнфреймах серии Unisys ClearPath Dorado используется дополнение до единиц.

История [ править ]

Первые дни цифровых вычислений были отмечены множеством конкурирующих идей, касающихся как аппаратных технологий, так и математических технологий (систем счисления). Одним из самых больших споров был формат отрицательных чисел, некоторые из ведущих экспертов эпохи имели очень сильные и разные мнения. ^{[ необходима цитата ]} Один лагерь поддерживал два дополнения , систему, которая сегодня доминирует. Другой лагерь поддерживал дополнение, где любое положительное значение превращается в его отрицательный эквивалент путем инвертирования всех битов в слове. Третья группа поддерживает «знак и величину» (знак-величина), где значение изменяется с положительного на отрицательное просто путем переключения бита знака (старшего разряда) слова.

Были аргументы за и против каждой из систем. Знак и величина позволили упростить отслеживание дампов памяти (распространенный процесс в 1960-х годах), поскольку для небольших числовых значений используется меньше 1 бит. Внутри этих систем выполнялась математика с дополнением до единиц, поэтому числа нужно было преобразовать в значения с дополнением до единиц, когда они были переданы из регистра в математическую единицу, а затем преобразовать обратно в знаковую величину, когда результат был передан обратно в регистр. Электронике требовалось больше вентилей, чем другим системам, что было ключевой проблемой, когда стоимость и упаковка дискретных транзисторов были критическими. IBM была одним из первых сторонников знаковой величины, и их компьютеры серий 704 , 709 и 709x были, пожалуй, самыми известными системами, в которых она использовалась.

Их дополнение позволяло создавать несколько более простые конструкции оборудования, поскольку не было необходимости преобразовывать значения при передаче в математический модуль и из него. Но у него также есть нежелательная характеристика со знаком-величиной - способность представлять отрицательный ноль (-0). Отрицательный ноль ведет себя точно так же, как положительный ноль; при использовании в качестве операнда в любом вычислении результат будет одинаковым независимо от того, является ли операнд положительным или отрицательным нулем. Однако недостатком является то, что наличие двух форм одного и того же значения требует двух, а не одного сравнения при проверке равенства нулю. Вычитание дополнительных элементов также может привести к заимствованию на конец периода.(описано ниже). Можно утверждать, что это усложняет логику сложения / вычитания или упрощает ее, поскольку вычитание требует простого инвертирования битов второго операнда при его передаче в сумматор. PDP-1 , CDC 160 серии , CDC 3000 серии, CDC серии 6000 , UNIVAC 1100 серии, а также ЛИНК дополнение представление компьютера использовать поразрядное.

Дополнение до двух проще всего реализовать на оборудовании, что может быть основной причиной его широкой популярности. ^[1] Процессоры на ранних мэйнфреймах часто состояли из тысяч транзисторов - устранение значительного количества транзисторов было значительной экономией. Мэйнфреймы , такие как IBM System / 360 , в серии GE-600 , ^[2] и PDP-6 и PDP-10 использовать два с дополнением, как и миникомпьютеры , такие , как PDP-5 и PDP-8 и PDP-11 и VAX . Архитекторы первых процессоров на базе интегральных схем ( Intel 8080и т. д.) решили использовать математику с дополнением до двух. По мере развития технологии ИС практически все использовали технологию дополнения до двух. Процессоры x86 , ^[3] m68k , Power ISA , ^[4] MIPS , SPARC , ARM , Itanium , PA-RISC и DEC Alpha дополняют друг друга.

Знаковое представление величины [ править ]

Это представление также называется представлением «знак-величина» или «знак и величина». В этом подходе знак числа представлен битом знака : установка этого бита (часто самого старшего бита ) на 0 для положительного числа или положительного нуля и установка на 1 для отрицательного числа или отрицательного нуля. Остальные биты числа указывают величину (или абсолютное значение ). Например, в восьмибитном байте только семь битов представляют величину, которая может находиться в диапазоне от 0000000 (0) до 1111111 (127). Таким образом, числа в диапазоне от -127 ₁₀ до +127 ₁₀ могут быть представлены после добавления знакового бита (восьмого бита). Например, −43 ₁₀в восьмибитном байте кодируется как 1 0101011, а 43 ₁₀ - это 0 0101011. Использование представления величины со знаком имеет несколько последствий, что усложняет их реализацию: ^[5]

1. Есть два способа представить ноль: 00000000 (0) и 10000000 ( -0 ).
2. Сложение и вычитание требуют разного поведения в зависимости от знакового бита, в то время как одно дополнение может игнорировать знаковый бит и просто выполнять сквозной перенос, а два дополнения могут игнорировать знаковый бит и зависеть от поведения переполнения.
3. Сравнение также требует проверки знакового бита, тогда как в дополнении до двух можно просто вычесть два числа и проверить, является ли результат положительным или отрицательным.
4. Минимальное отрицательное число -127 вместо -128 в случае дополнения до двух.

Этот подход напрямую сопоставим с обычным способом показа знака (размещение «+» или «-» рядом с величиной числа). Некоторые ранние бинарные компьютеры (например, IBM 7090 ) использовали это представление, возможно, из-за его естественного отношения к обычному использованию. Величина со знаком - это наиболее распространенный способ представления мантиссы в значениях с плавающей запятой .

Дополнение [ править ]

В качестве альтернативы для представления отрицательных чисел можно использовать систему, известную как дополнение до единиц ^[6] . Форма дополнения до единиц отрицательного двоичного числа - это побитовое НЕ, применяемое к нему, то есть «дополнение» его положительного аналога. Подобно представлению знака и величины, дополнение до единиц имеет два представления 0: 00000000 (+0) и 11111111 ( -0 ). ^[7]

Например, форма дополнения единиц 00101011 (43 ₁₀ ) становится 11010100 (-43 ₁₀ ). Диапазон подписанных чисел , используя обратный код представлен - (2 ^{Н -1} - 1) к (2 ^{N -1} - 1) и ± 0. Обычный восьмиразрядный байт - это от −127 ₁₀ до +127 _10, где ноль равен либо 00000000 (+0), либо 11111111 (−0).

Чтобы сложить два числа, представленных в этой системе, выполняется обычное двоичное сложение, но затем необходимо выполнить сквозной перенос : то есть добавить любой результирующий перенос обратно в результирующую сумму. ^[8] Чтобы понять, почему это необходимо, рассмотрим следующий пример, показывающий случай добавления −1 (11111110) к +2 (00000010):

 двоичный десятичный 11111110 -1 + 00000010 +2 ──────────── ── 1 00000000 0 ← Не правильный ответ 1 +1 ← Добавить перенос ──────────── ── 00000001 1 ← Правильный ответ

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

Замечание по терминологии: Система называется «дополнением , поскольку того , » отрицание положительного значения х (представлено в виде побитового НЕ из й ) также может быть образованно путем вычитания х из один комплемента представления нуля , что является длинная последовательность единиц (−0). С другой стороны, арифметика с дополнением до двух формирует отрицание x путем вычитания x из одной большой степени двойки, которая конгруэнтна +0. ^[9] Следовательно, представление одного и того же отрицательного значения в виде дополнения до единицы и дополнения до двух будет отличаться на единицу.

Обратите внимание, что представление отрицательного числа с дополнением до единиц может быть получено из представления знаковой величины просто путем побитового дополнения величины (инвертирования всех битов после первого). Например, десятичное число -125 с его знаком величины 11111101 может быть представлено в форме дополнения до единиц как 10000010.

Дополнение до двух [ править ]

Проблемы множественного представления 0 и необходимость непрерывного переноса обходятся с помощью системы, называемой дополнением до двух . В дополнении до двух отрицательные числа представлены битовой комбинацией, которая на единицу больше (в беззнаковом смысле), чем дополнение единиц положительного значения.

В дополнении до двух существует только один ноль, представленный как 00000000. Отрицание числа (отрицательного или положительного) осуществляется путем инвертирования всех битов и последующего добавления единицы к этому результату. ^[10] Это фактически отражает кольцевую структуру на все целые числа по модулю 2 N : . Добавление пары целых чисел с дополнением до двух совпадает с добавлением пары беззнаковых чисел (за исключением обнаружения переполнения , если это сделано); то же самое верно для вычитания и даже для N${\ Displaystyle \ mathbb {Z} / 2 ^ {N} \ mathbb {Z}}$младшие значащие биты продукта (значение умножения). Например, сложение с дополнительным двоичным кодом 127 и -128 дает тот же двоичный битовый шаблон, что и беззнаковое сложение 127 и 128, как можно увидеть из 8-битной таблицы дополнения до двух.

Более простой способ получить отрицание числа в дополнении до двух выглядит следующим образом:

Метод второй:

1. Инвертируйте все биты через число
2. Добавить одну

Пример: для +2, что равно 00000010 в двоичном формате (символ ~ является побитовым оператором НЕ C , поэтому ~ X означает "инвертировать все биты в X"):

1. ~ 00000010 → 11111101
2. 11111101 + 1 → 11111110 (−2 в дополнении до двух)

Смещение двоичного [ править ]

Двоичное смещение , также называемое избыточным K или смещенным представлением, использует заранее заданное число K в качестве значения смещения. Значение представлено беззнаковым числом, которое на K больше заданного значения. Таким образом, 0 представлен как K , а -K представлен битовой комбинацией из нулей. Это можно рассматривать как небольшую модификацию и обобщение вышеупомянутого дополнения до двух, которое фактически является представлением с избытком (2 ^{N -1} ) с инвертированным старшим значащим битом .

Смещенные представления теперь в основном используются для экспоненты чисел с плавающей запятой . Стандарт IEEE 754 с плавающей запятой определяет поле экспоненты числа с одинарной точностью (32-битное) как 8-битное поле с избыточностью 127 . Поле экспоненты с двойной точностью (64-битное) представляет собой 11-битное поле с превышением 1023 ; см. смещение экспоненты . Он также использовался для двоичных десятичных чисел в качестве лишнего-3 .

База -2 [ править ]

В обычных двоичных системах счисления основание или основание системы счисления равно 2; таким образом, крайний правый бит представляет 2 ⁰ , следующий бит представляет 2 ¹ , следующий бит 2 ² и так далее. Однако возможна и двоичная система счисления с основанием −2. Самый правый бит представляет (-2) ⁰ = +1 , следующий бит представляет (-2) ¹ = -2 , следующий бит (-2) ² = +4 и так далее, с переменным знаком. Числа, которые могут быть представлены четырьмя битами, показаны в сравнительной таблице ниже.

Диапазон чисел, которые могут быть представлены, асимметричен. Если слово имеет четное число битов, величина наибольшего отрицательного числа, которое может быть представлено, вдвое больше, чем наибольшее положительное число, которое может быть представлено, и наоборот, если слово имеет нечетное число битов.

Таблица сравнения [ править ]

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

Та же таблица, если смотреть на это "учитывая эти двоичные биты, какое число интерпретируется системой представления":

Другие системы [ править ]

«Зигзагообразное кодирование» буферов протокола Google - это система, аналогичная системе «знак и величина», но в которой используется младший бит для представления знака, и она имеет единственное представление нуля. Это позволяет эффективно использовать количественное кодирование переменной длины, предназначенное для неотрицательных (беззнаковых) целых чисел, для целых чисел со знаком. ^[11]

Другой подход - присвоить каждой цифре знак, в результате чего будет получено представление цифры со знаком . Например, в 1726 году Джон Колсон выступал за сокращение выражений до «малых чисел», цифр 1, 2, 3, 4 и 5. В 1840 году Огюстен Коши также выразил предпочтение таким модифицированным десятичным числам для уменьшения ошибок в вычислениях.

См. Также [ править ]

• Сбалансированный тройной
• Десятичное число с двоичным кодом
• Формат номера компьютера
• Метод дополнений
• Подпись

Ссылки [ править ]

• Иван Флорес, Логика компьютерной арифметики , Прентис-Холл (1963)
• Исраэль Корен, Компьютерные арифметические алгоритмы , AK Peters (2002), ISBN 1-56881-160-8