Представления чисел со знаком

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

В математике отрицательные числа в любом основании обозначаются знаком минус («-»). Однако в ОЗУ или ЦП регистрах числа представлены только в виде последовательностей битов , без дополнительных символов. Четыре наиболее известных метода расширения двоичной системы счисления для представления чисел со знаком : знак-величина , дополнение до единиц , дополнение до двух и двоичное смещение . Некоторые альтернативные методы используют неявные вместо явных знаков, например, отрицательный двоичный код с основанием -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 , ARM , Itanium , PA-RISC и DEC Alpha .

Знак-величина

Восьмибитный знак – величина
Бинарное значение	Интерпретация знака и величины	Беззнаковая интерпретация
00000000	0	0
00000001	1	1
⋮	⋮	⋮
01111101	125	125
01111110	126	126
01111111	127	127
10000000	−0	128
10000001	−1	129
10000010	−2	130
⋮	⋮	⋮
11111101	−125	253
11111110	−126	254
11111111	−127	255

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

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

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

Дополнение единиц

Дополнение восьмибитных единиц
Бинарное значение	Интерпретация дополнения единиц	Беззнаковая интерпретация
00000000	0	0
00000001	1	1
⋮	⋮	⋮
01111101	125	125
01111110	126	126
01111111	127	127
10000000	−127	128
10000001	−126	129
10000010	−125	130
⋮	⋮	⋮
11111101	−2	253
11111110	−1	254
11111111	−0	255

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

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

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

    binary    decimal
   11111110     −1
+  00000010     +2
───────────     ──
 1 00000000      0   ← Not the correct answer
          1     +1   ← Add carry
───────────     ──
   00000001      1   ← Correct answer

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

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

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

Дополнение до двух

Восьмибитное дополнение до двух
Бинарное значение	Интерпретация дополнения до двух	Беззнаковая интерпретация
00000000	0	0
00000001	1	1
⋮	⋮	⋮
01111110	126	126
01111111	127	127
10000000	−128	128
10000001	−127	129
10000010	−126	130
⋮	⋮	⋮
11111110	−2	254
11111111	−1	255

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

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

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

	Пример 1	Пример 2
1. Начиная справа, найдите первую «1».	0010100 1	00101 1 00
2. Инвертируйте все биты слева от «1».	1101011 1	11010 100

Способ второй:

Инвертируйте все биты числа. Это вычисляет тот же результат, что и вычитание из отрицательного.
Добавить один

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

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

Смещенный двоичный файл

Восьмибитное превышение-128
Бинарное значение	Интерпретация Excess-128	Беззнаковая интерпретация
00000000	−128	0
00000001	−127	1
⋮	⋮	⋮
01111111	−1	127
10000000	0	128
10000001	1	129
⋮	⋮	⋮
11111111	127	255

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

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

База −2

Восьмибитная база −2
Бинарное значение	Базовая интерпретация −2	Беззнаковая интерпретация
00000000	0	0
00000001	1	1
⋮	⋮	⋮
01111111	43	127
10000000	−128	128
10000001	−127	129
⋮	⋮	⋮
11111111	−85	255

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

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

Сравнительная таблица

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

Четырехбитные целочисленные представления
Десятичный	Без подписи	Знак-величина	Дополнение единиц	Дополнение до двух	Превышение-8 (предвзятое)	База −2
16	—	—	—	—	—	—
15	1111	—	—	—	—	—
14	1110	—	—	—	—	—
13	1101	—	—	—	—	—
12	1100	—	—	—	—	—
11	1011	—	—	—	—	—
10	1010	—	—	—	—	—
9	1001	—	—	—	—	—
8	1000	—	—	—	—	—
7	0111	0111	0111	0111	1111	—
6	0110	0110	0110	0110	1110	—
5	0101	0101	0101	0101	1101	0101
4	0100	0100	0100	0100	1100	0100
3	0011	0011	0011	0011	1011	0111
2	0010	0010	0010	0010	1010	0110
1	0001	0001	0001	0001	1001	0001
0	0000	0000	0000	0000	1000	0000
−0	0000	1000	1111	0000	1000	0000
−1	—	1001	1110	1111	0111	0011
−2	—	1010	1101	1110	0110	0010
−3	—	1011	1100	1101	0101	1101
−4	—	1100	1011	1100	0100	1100
−5	—	1101	1010	1011	0011	1111
−6	—	1110	1001	1010	0010	1110
−7	—	1111	1000	1001	0001	1001
−8	—	—	—	1000	0000	1000
−9	—	—	—	—	—	1011
−10	—	—	—	—	—	1010
−11	—	—	—	—	—	—

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

Двоичный	Без подписи	Знак-величина	Дополнение единиц	Дополнение до двух	Превышение-8	База −2
0000	0	0	0	0	−8	0
0001	1	1	1	1	−7	1
0010	2	2	2	2	−6	−2
0011	3	3	3	3	−5	−1
0100	4	4	4	4	−4	4
0101	5	5	5	5	−3	5
0110	6	6	6	6	−2	2
0111	7	7	7	7	−1	3
1000	8	−0	−7	−8	0	−8
1001	9	−1	−6	−7	1	−7
1010	10	−2	−5	−6	2	−10
1011	11	−3	−4	−5	3	−9
1100	12	−4	−3	−4	4	−4
1101	13	−5	−2	−3	5	−3
1110	14	−6	−1	−2	6	−6
1111	15	−7	−0	−1	7	−5

Другие системы

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

Подобный метод используется в стандартах сжатия видео Advanced Video Coding/H.264 и High Efficiency Video Coding/H.265 для расширения экспоненциального кодирования Голомба до отрицательных чисел. В этом расширении младший бит является почти знаковым битом; ноль имеет тот же самый младший бит (0), что и все отрицательные числа. Этот выбор приводит к тому, что представимое положительное число наибольшей величины на единицу превышает отрицательное число наибольшей величины, в отличие от кодирования с дополнением до двух или зигзагообразного кодирования протокольных буферов.

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

См. также

Ссылки

^ Чу, Хунсу; Мухаммед, К.; Рой, К. (февраль 2003 г.). «Множитель совместного использования вычислений с двойным дополнением и его применение для высокопроизводительного DFE» . Транзакции IEEE по обработке сигналов . 51 (2): 458–469. Бибкод : 2003ITSP...51..458C . дои : 10.1109/TSP.2002.806984 .
^ Справочное руководство по программированию GE-625/635 . Дженерал Электрик . Январь 1966 года . Проверено 15 августа 2013 г.
^ Руководство разработчика программного обеспечения для архитектур Intel 64 и IA-32 (PDF) . Интел . Раздел 4.2.1 . Проверено 6 августа 2013 г.
^ Power ISA версии 2.07 (PDF) . Power.org . Раздел 1.4 . Проверено 2 ноября 2023 г. ,
^ Бэкон, Джейсон В. (2010–2011). «Информатика 315 Конспект лекций» . Архивировано из оригинала 14 февраля 2020 года . Проверено 21 февраля 2020 г.
^ США 4484301 , «Множитель массива, работающий в формате дополнения», выпущен 10 марта 1981 г.
^ US 6760440 , «Криптографический объединитель с дополнением до единицы», выдан 11 декабря 1999 г.
^ Шедлецкий, Джон Дж. (1977). «Комментарий к последовательному и неопределенному поведению сумматора с круговым переносом». Транзакции IEEE на компьютерах . 26 (3): 271–272. дои : 10.1109/TC.1977.1674817 . S2CID 14661474 .
^ Дональд Кнут: Искусство компьютерного программирования , Том 2: Получисловые алгоритмы, глава 4.1
^ Томас Финли (апрель 2000 г.). «Дополнение двоих» . Корнеллский университет . Проверено 15 сентября 2015 г.
^ Буферы протокола: целые числа со знаком

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

[1] Чу, Хунсу; Мухаммед, К.; Рой, К. (февраль 2003 г.). «Множитель совместного использования вычислений с двойным дополнением и его применение для высокопроизводительного DFE» . Транзакции IEEE по обработке сигналов . 51 (2): 458–469. Бибкод : 2003ITSP...51..458C . дои : 10.1109/TSP.2002.806984 .

[2] Справочное руководство по программированию GE-625/635 . Дженерал Электрик . Январь 1966 года . Проверено 15 августа 2013 г.

[3] Руководство разработчика программного обеспечения для архитектур Intel 64 и IA-32 (PDF) . Интел . Раздел 4.2.1 . Проверено 6 августа 2013 г.

[4] Power ISA версии 2.07 (PDF) . Power.org . Раздел 1.4 . Проверено 2 ноября 2023 г. ,

[cs315-5] Бэкон, Джейсон В. (2010–2011). «Информатика 315 Конспект лекций» . Архивировано из оригинала 14 февраля 2020 года . Проверено 21 февраля 2020 г.

[6] США 4484301 , «Множитель массива, работающий в формате дополнения», выпущен 10 марта 1981 г.

[7] US 6760440 , «Криптографический объединитель с дополнением до единицы», выдан 11 декабря 1999 г.

[8] Шедлецкий, Джон Дж. (1977). «Комментарий к последовательному и неопределенному поведению сумматора с круговым переносом». Транзакции IEEE на компьютерах . 26 (3): 271–272. дои : 10.1109/TC.1977.1674817 . S2CID 14661474 .

[9] Дональд Кнут: Искусство компьютерного программирования , Том 2: Получисловые алгоритмы, глава 4.1

[10] Томас Финли (апрель 2000 г.). «Дополнение двоих» . Корнеллский университет . Проверено 15 сентября 2015 г.

[11] Буферы протокола: целые числа со знаком

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]