Представления чисел со знаком
Эта статья нуждается в дополнительных цитатах для проверки . ( апрель 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 , 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 10 до +127 10 могут быть представлены после добавления знакового бита (восьмого бита). Например, −43 10, закодированное в восьмибитном байте, равно 1 0101011, а 43 10 — 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 10 ) становится 11010100 (−43 10 ). Диапазон чисел со знаком, использующих дополнение до единиц, представлен - (2 Н -1 − 1) до (2 Н -1 − 1) и ±0. Обычный восьмибитный байт имеет значение от -127 10 до +127 10 , где ноль равен 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. Н : . Сложение пары целых чисел с дополнением до двух аналогично сложению пары чисел без знака (за исключением обнаружения переполнения , если оно выполнено); то же самое верно для вычитания и даже для 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 в дополнении до двух)
Смещенный двоичный файл
[ редактировать ]Бинарное значение | Интерпретация 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 | Беззнаковая интерпретация |
---|---|---|
00000000 | 0 | 0 |
00000001 | 1 | 1 |
⋮ | ⋮ | ⋮ |
01111111 | 43 | 127 |
10000000 | −128 | 128 |
10000001 | −127 | 129 |
⋮ | ⋮ | ⋮ |
11111111 | −85 | 255 |
В представлении по основанию -2 число со знаком представляется с использованием системы счисления с основанием -2. В обычных двоичных системах счисления основание или основание системы счисления равно 2; таким образом, самый правый бит представляет 2 0 , следующий бит представляет 2 1 , следующий бит 2 2 , и так далее. Однако возможна и двоичная система счисления с основанием -2. Самый правый бит представляет (-2) 0 = +1 , следующий бит представляет (−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 | 1000 | 1111 | ||||
−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