В вычислительной технике представления чисел со знаком необходимы для кодирования отрицательных чисел в двоичных системах счисления.
В математике отрицательные числа в любом основании обозначаются знаком минус («-»). Однако в регистрах ОЗУ или ЦП числа представлены только в виде последовательностей битов , без дополнительных символов. Четыре наиболее известных метода расширения двоичной системы счисления для представления чисел со знаком : знак-величина, дополнение до единиц, дополнение до двух и двоичное смещение. Некоторые из альтернативных методов используют неявные вместо явных знаков, например, отрицательный двоичный код с основанием -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 и PDP-11 . Машины ВАКС . Архитекторы первых процессоров на базе интегральных схем ( Intel 8080 и т. д.) также предпочитали использовать математику с дополнением до двух. По мере развития технологии IC технология дополнения до двух была принята практически во всех процессорах, включая 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 в двоичном формате (символ ~ — это побитовый оператор NOT C , поэтому ~X означает «инвертировать все биты в X»):
В двоичном представлении смещения, также называемом избыточным -K или смещенным , число со знаком представлено битовой комбинацией, соответствующей беззнаковому числу плюс K , где K является значением смещения или смещением . Таким образом, 0 представлен K , а − K представлен битовой комбинацией, состоящей из всех нулей. Это можно рассматривать как небольшую модификацию и обобщение вышеупомянутого дополнения до двух, которое фактически представляет собой представление избыточного (2 N -1 ) с отрицательным старшим значащим битом .
Смещенные представления теперь в основном используются для экспоненты чисел с плавающей запятой . Стандарт IEEE 754 с плавающей запятой определяет поле экспоненты числа одинарной точности (32 бита) как 8-битное поле с превышением 127 . Поле экспоненты двойной точности (64 бита) представляет собой 11-битное поле с превышением 1023 ; см. смещение показателя . Он также использовал двоично-десятичные числа какexex -3 .
В представлении по основанию -2 число со знаком представляется с использованием системы счисления с основанием -2. В обычных двоичных системах счисления основание или основание системы счисления равно 2; таким образом, самый правый бит представляет 2 0 , следующий бит представляет 2 1 , следующий бит 2 2 и так далее. Однако возможна и двоичная система счисления с основанием -2. Самый правый бит представляет (-2) 0 = +1 , следующий бит представляет (-2) 1 = -2 , следующий бит (-2) 2 = +4 и так далее, с переменным знаком. Числа, которые могут быть представлены четырьмя битами, показаны в сравнительной таблице ниже.
Диапазон чисел, которые могут быть представлены, асимметричен. Если слово имеет четное количество бит, величина наибольшего отрицательного числа, которое может быть представлено, в два раза больше, чем наибольшее положительное число, которое может быть представлено, и наоборот, если слово имеет нечетное количество бит.
В следующей таблице показаны положительные и отрицательные целые числа, которые можно представить с помощью четырех битов.
Та же таблица, если смотреть со стороны «учитывая эти двоичные биты, каково число, интерпретируемое системой представления»:
«Зигзагообразное кодирование» протокольных буферов Google — это система, аналогичная системе «знак-величина», но для представления знака используется младший бит и имеется единственное представление нуля. Это позволяет эффективно использовать кодирование величин переменной длины , предназначенное для неотрицательных (беззнаковых) целых чисел, для целых чисел со знаком. [11]
Подобный метод используется в стандартах сжатия видео Advanced Video Coding/H.264 и High Efficiency Video Coding/H.265 для расширения экспоненциального кодирования Голомба до отрицательных чисел. В этом расширении младший бит является почти знаковым битом; ноль имеет тот же самый младший бит (0), что и все отрицательные числа. Этот выбор приводит к тому, что представимое положительное число наибольшей величины оказывается на единицу больше, чем отрицательное число наибольшей величины, в отличие от кодирования с дополнением до двух или зигзагообразного кодирования протокольных буферов.
Другой подход заключается в присвоении каждой цифре знака, в результате чего получается представление знаковой цифры . Например, в 1726 году Джон Колсон выступал за сокращение выражений до «малых чисел», цифр 1, 2, 3, 4 и 5. В 1840 году Огюстен Коши также выразил предпочтение таким модифицированным десятичным числам, чтобы уменьшить ошибки в вычислениях.
