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

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

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

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

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

История

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

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

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

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

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

Это представление также называется представлением «знак-величина» или «знак и величина». В этом подходе знак числа представлен в виде знаковый бит: установка этого кусочек (часто старший бит ) на 0 для положительного числа или положительного нуля и установка на 1 для отрицательного числа или отрицательного нуля. Остальные биты в номере указывают величину (или абсолютная величина ). Например, в восьмибитном байт, только семь битов представляют величину, которая может варьироваться от 0000000 (0) до 1111111 (127). Таким образом, числа в диапазоне от -127₁₀ до +127₁₀ может быть представлен после добавления знакового бита (восьмого бита). Например, −43₁₀ закодировано в восьмибитном байте 10101011 а 43₁₀ является 00101011. Использование представления величины со знаком имеет несколько последствий, что делает их более сложными для реализации:^[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^N−1 − 1) к (2^N−1 − 1) и ± 0. Обычный восьмиразрядный байт равен −127.₁₀ до +127₁₀ где ноль равен либо 00000000 (+0), либо 11111111 (-0).

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

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

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

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

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

Два дополнения

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

В дополнении до двух существует только один ноль, представленный как 00000000. Отрицание числа (отрицательного или положительного) осуществляется путем инвертирования всех битов и последующего добавления единицы к этому результату.^[10] Это фактически отражает звенеть структура на всех целых числах по модулю 2^N: ${ Displaystyle mathbb {Z} / 2 ^ {N} mathbb {Z}}$. Добавление пары целых чисел с дополнением до двух совпадает с добавлением пары целых чисел. беззнаковые числа (кроме обнаружения переполнение, если это будет сделано); то же самое верно и для вычитания, и даже для N младшие значащие биты продукта (значение умножения). Например, сложение с дополнительным двоичным кодом 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)
• Исраэль Корен, Компьютерные арифметические алгоритмы, А.К. Питерс (2002), ISBN  1-56881-160-8