В вычислительной технике для кодирования отрицательных чисел в двоичных системах счисления требуются знаковые представления чисел .
В математике отрицательные числа в любой базе представляются с помощью префикса со знаком минус («−»). Однако в регистрах ОЗУ или ЦП числа представляются только в виде последовательностей битов без дополнительных символов. Четыре наиболее известных метода расширения двоичной системы счисления для представления знаковых чисел : знак-величина, дополнение до единицы, дополнение до двойки и смещенная двоичная система. Некоторые из альтернативных методов используют неявные знаки вместо явных, например, отрицательная двоичная система счисления с использованием основания -2. Соответствующие методы могут быть разработаны для других баз , будь то положительные, отрицательные, дробные или другие разработки на такие темы.
Не существует определенного критерия, по которому любое из представлений является универсально лучшим. Для целых чисел представление, используемое в большинстве современных вычислительных устройств, является дополнением до двух, хотя мэйнфреймы серии Unisys ClearPath Dorado используют дополнение до единиц.
Ранние дни цифровых вычислений были отмечены конкурирующими идеями как об аппаратных технологиях, так и о математических технологиях (системах счисления). Одним из главных споров был формат отрицательных чисел, при этом некоторые из ведущих экспертов эпохи выражали очень сильные и различные мнения. [ требуется ссылка ] Один лагерь поддерживал дополнение до двух , систему, которая доминирует сегодня. Другой лагерь поддерживал дополнение до единиц, где отрицательное значение формируется путем инвертирования всех битов в его положительном эквиваленте. Третья группа поддерживала знак-величину, где значение изменяется с положительного на отрицательное просто путем переключения старшего бита слова.
Были аргументы за и против каждой из систем. Знак-величина позволяла легче отслеживать дампы памяти (обычный процесс в 1960-х годах), поскольку небольшие числовые значения использовали меньше единичных битов. Эти системы выполняли внутреннюю математику с дополнением по единицам, поэтому числа приходилось преобразовывать в значения с дополнением по единицам, когда они передавались из регистра в математическое устройство, а затем преобразовывать обратно в знак-величину, когда результат передавался обратно в регистр. Электронике требовалось больше вентилей, чем другим системам, что было ключевым вопросом, когда стоимость и упаковка дискретных транзисторов были критичны. 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 , Power ISA , [4] MIPS , SPARC , ARM , Itanium , PA-RISC и DEC Alpha .
В представлении знак-величина , также называемом знак-и-величина или знаковая величина , число со знаком представляется битовой комбинацией, соответствующей знаку числа для бита знака (часто самого старшего бита , установленного в 0 для положительного числа и в 1 для отрицательного числа), и величиной числа (или абсолютным значением ) для остальных битов. Например, в восьмибитном байте только семь бит представляют величину, которая может находиться в диапазоне от 0000000 (0) до 1111111 (127). Таким образом, числа в диапазоне от −127 10 до +127 10 могут быть представлены после добавления бита знака (восьмого бита). Например, −43 10, закодированное в восьмибитном байте, равно 1 0101011, а 43 10 равно 0 0101011. Использование представления знака и величины имеет несколько последствий, что делает его более сложным для реализации: [5]
Этот подход напрямую сопоставим с общепринятым способом отображения знака (размещение "+" или "−" рядом с величиной числа). Некоторые ранние двоичные компьютеры (например, IBM 7090 ) использовали это представление, возможно, из-за его естественной связи с общепринятым использованием. Знак-величина является наиболее распространенным способом представления мантиссы в значениях с плавающей точкой .
В представлении с дополнением по единицам [6] отрицательное число представлено битовой комбинацией, соответствующей побитовому НЕ (т.е. "дополнению") положительного числа. Подобно представлению знак-величина, дополнение по единицам имеет два представления 0: 00000000 (+0) и 11111111 ( −0 ). [7]
Например, форма дополнения до единиц 00101011 (43 10 ) становится 11010100 (−43 10 ). Диапазон знаковых чисел, использующих дополнение до единиц, представлен как −(2 N −1 − 1) до (2 N −1 − 1) и ±0. Обычный восьмибитный байт имеет значение от −127 10 до +127 10 , где ноль равен либо 00000000 (+0), либо 11111111 (−0).
Чтобы сложить два числа, представленных в этой системе, нужно выполнить обычное двоичное сложение, но затем необходимо выполнить круговой перенос : то есть добавить любой полученный перенос обратно в полученную сумму. [8] Чтобы понять, почему это необходимо, рассмотрим следующий пример, демонстрирующий случай сложения −1 (11111110) с +2 (00000010):
двоично-десятичный 11111110 −1+ 00000010 +2─────────── ── 1 00000000 0 ← Неверный ответ 1 +1 ← Добавить перенос─────────── ── 00000001 1 ← Правильный ответ
В предыдущем примере первое двоичное сложение дает 00000000, что неверно. Правильный результат (00000001) появляется только при добавлении переноса обратно.
Замечание по терминологии: система называется «дополнением до единицы», потому что отрицание положительного значения x (представленного как побитовое НЕ x ) также может быть сформировано вычитанием x из представления нуля в виде дополнения до единицы, которое является длинной последовательностью единиц (−0). С другой стороны, арифметика дополнения до двух формирует отрицание x путем вычитания x из одной большой степени двойки, которая конгруэнтна +0. [9] Следовательно, представления одного и того же отрицательного значения в виде дополнения до единицы и дополнения до пары будут отличаться на единицу.
Обратите внимание, что представление отрицательного числа в виде дополнения до единиц может быть получено из представления знака и величины просто путем побитового дополнения величины (инвертирования всех битов после первого). Например, десятичное число −125 с его представлением знака и величины 11111101 может быть представлено в виде дополнения до единиц как 10000010.
В представлении дополнения до двух отрицательное число представлено битовой последовательностью, соответствующей побитовому НЕ (т. е. "дополнению") положительного числа плюс один, т. е. дополнению до единиц плюс один. Это обходит проблемы множественных представлений 0 и необходимость переноса по кругу представления дополнения до единиц. Это также можно рассматривать как старший бит, представляющий инверсию своего значения в беззнаковом целом числе; в 8-битном беззнаковом байте старший бит представляет 128-й разряд, тогда как в дополнении до двух этот бит будет представлять −128.
В дополнительном коде есть только один ноль, представленный как 00000000. Отрицание числа (независимо от того, отрицательное оно или положительное) выполняется путем инвертирования всех битов и последующего добавления единицы к полученному результату. [10] Это фактически отражает кольцевую структуру всех целых чисел по модулю 2 N : . Сложение пары целых чисел в дополнительном коде равно сложению пары беззнаковых чисел (за исключением обнаружения переполнения , если оно выполняется); то же самое верно для вычитания и даже для N младших значащих битов произведения (значения умножения). Например, сложение в дополнительном коде 127 и −128 дает ту же двоичную битовую последовательность, что и беззнаковое сложение 127 и 128, как можно увидеть из 8-битной таблицы дополнительного кода.
Более простой способ получить отрицание числа в дополнительном коде заключается в следующем:
Способ второй:
Пример: для +2, что в двоичном формате равно 00000010 (символ ~ — это побитовый оператор НЕ языка C , поэтому ~X означает «инвертировать все биты в X»):
В смещенном двоичном представлении, также называемом избыточным- K или смещенным , знаковое число представлено битовой комбинацией, соответствующей беззнаковому числу плюс K , где K является смещающим значением или смещением . Таким образом, 0 представлен K , а − K представлен битовой комбинацией из всех нулей. Это можно рассматривать как небольшую модификацию и обобщение вышеупомянутого дополнения до двух, которое фактически является избыточным-(2 N −1 ) представлением с отрицательным старшим битом .
Смещенные представления теперь в основном используются для экспоненты чисел с плавающей точкой . Стандарт IEEE 754 для чисел с плавающей точкой определяет поле экспоненты числа с одинарной точностью (32 бита) как 8-битное поле с избытком-127 . Поле экспоненты с двойной точностью (64 бита) представляет собой 11-битное поле с избытком-1023 ; см. смещение экспоненты . Оно также использовалось для двоично-десятичных чисел как избыток-3 .
В представлении с основанием −2 число со знаком представляется с использованием системы счисления с основанием −2. В обычных двоичных системах счисления основание, или радикс , равно 2; таким образом, самый правый бит представляет 2 0 , следующий бит представляет 2 1 , следующий бит представляет 2 2 и так далее. Однако двоичная система счисления с основанием −2 также возможна. Самый правый бит представляет (−2) 0 = +1 , следующий бит представляет (−2) 1 = −2 , следующий бит (−2) 2 = +4 и так далее, с чередованием знака. Числа, которые могут быть представлены четырьмя битами, показаны в сравнительной таблице ниже.
Диапазон чисел, которые могут быть представлены, асимметричен. Если слово имеет четное число бит, величина наибольшего отрицательного числа, которое может быть представлено, в два раза больше, чем наибольшее положительное число, которое может быть представлено, и наоборот, если слово имеет нечетное число бит.
В следующей таблице показаны положительные и отрицательные целые числа, которые можно представить с помощью четырех бит.
Та же таблица, если смотреть с точки зрения «при наличии этих двоичных битов, каково число, интерпретируемое системой представления»:
"Зигзагообразное кодирование" Google Protocol Buffers — это система, похожая на sign–magnititude, но использующая младший бит для представления знака и имеющая единственное представление нуля. Это позволяет эффективно использовать для знаковых целых чисел кодирование переменной длины, предназначенное для неотрицательных (беззнаковых) целых чисел. [11]
Похожий метод используется в стандартах сжатия видео Advanced Video Coding/H.264 и High Efficiency Video Coding/H.265 для расширения кодирования экспоненциального Голомба на отрицательные числа. В этом расширении младший бит является почти знаковым битом; ноль имеет тот же младший бит (0), что и все отрицательные числа. Этот выбор приводит к тому, что наибольшее представимое положительное число оказывается на единицу больше, чем наибольшее отрицательное число, в отличие от кодирования с дополнением до двух или зигзагом Protocol Buffers.
Другой подход заключается в том, чтобы присвоить каждой цифре знак, что даст представление знаковой цифры . Например, в 1726 году Джон Колсон выступал за сокращение выражений до «маленьких чисел», цифр 1, 2, 3, 4 и 5. В 1840 году Огюстен Коши также выразил предпочтение таким измененным десятичным числам для уменьшения ошибок в вычислениях.
