Jump to content

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

(Перенаправлено со знака и величины )

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

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

  1. Существует два способа представления нуля: 00000000 (0) и 10000000 ( −0 ).
  2. Сложение и вычитание требуют разного поведения в зависимости от знакового бита, тогда как дополнение до единиц может игнорировать знаковый бит и просто выполнять циклический перенос, а дополнение до двух может игнорировать знаковый бит и зависеть от поведения переполнения.
  3. Сравнение также требует проверки знакового бита, тогда как при дополнении до двух можно просто вычесть два числа и проверить, является ли результат положительным или отрицательным.
  4. Минимальное отрицательное число составляет -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

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

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

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

  1. ~00000010 → 11111101
  2. 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 Беззнаковая интерпретация
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 году Огюстен Коши также выразил предпочтение таким модифицированным десятичным числам, чтобы уменьшить ошибки в вычислениях.

См. также

[ редактировать ]
  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 г. ,
  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. ^ Буферы протокола: целые числа со знаком
  • Иван Флорес, Логика компьютерной арифметики , Прентис-Холл (1963)
  • Исраэль Корен, Алгоритмы компьютерной арифметики , AK Peters (2002), ISBN   1-56881-160-8
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: ca0d96cc748fe3675c7b399ecb27110f__1721134380
URL1:https://arc.ask3.ru/arc/aa/ca/0f/ca0d96cc748fe3675c7b399ecb27110f.html
Заголовок, (Title) документа по адресу, URL1:
Signed number representations - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)