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

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

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

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

В предыдущем примере первое двоичное сложение дает 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 г.). «Дополнение двоих» . Cornell University . Проверено 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 г.). «Дополнение двоих» . Cornell University . Проверено 15 сентября 2015 г.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]