Почему используются числа без знака?

12

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

Отчасти мой вопрос: почему они должны быть в наборе команд, а не поддерживаться компилятором?

JTW
источник
27
В основном числа без знака являются стандартом, знаки со знаком реализованы для предоставления отрицательных чисел.
Питер Б
37
Многие мировые данные не числовые. Нечисловые данные легко обрабатываются с использованием неподписанных типов. То, что в Java нет числовых типов без знака, является ошибкой, которая вызывает много ошибок в вещах, которые должны манипулировать нечисловыми данными (например, сжатие и т. Д.).
Эрик Эйдт
6
@jtw Эрик говорит, что нет такой вещи, как отрицательный цвет пикселя или отрицательный символ. Поэтому для этого было бы расточительно использовать целые числа со знаком, вы бы оставили половину адресного пространства.
Мартин Маат
26
Я не уверен, что я один здесь, но я нахожу удивительно редким, когда мне нужны целые числа со знаком при разработке приложений. Почти все время мне нужно либо натуральное число (без знака) (обычно положительного размера), либо число с плавающей запятой со знаком. Исключениями являются такие вещи, как валюта, но они очень редки; для меня целые числа без знака являются нормой, а целые числа со знаком являются исключением!
Томас
11
С точки зрения процессора, практически все числа без знака. Несколько команд могут интерпретировать биты как подписанные (.eg arithmetic-right-shift), но на самом деле дополнение к двум позволяет ЦПУ обрабатывать целые числа со знаком как целые числа без знака, то есть ЦПУ не требует (или очень мало) специальных схем для поддержки обоих ,
Кукурузные початки

Ответы:

39

Числа без знака являются одной интерпретацией последовательности битов. Это также самая простая и наиболее используемая интерпретация внутри процессора, потому что адреса и коды операций - это просто биты. Адресация памяти / стека и арифметика - основа микропроцессора, ну и обработки. Двигаясь вверх по пирамиде абстракции, другая частая интерпретация битов - это символ (ASCII, Unicode, EBCDIC). Затем существуют другие интерпретации, такие как IEEE с плавающей точкой, RGBA для графики и так далее. Ни одно из них не является простым числом со знаком (IEEE FP не является простым, и арифметическое использование их очень сложно).

Кроме того, с арифметикой без знака довольно просто (если не наиболее эффективно) реализовать другие. Обратное неверно.

Кристиан Х
источник
3
У EBCDIC есть только одно «я».
Руслан
4
@Ruslan - но произносится как два. <g>
Пит Беккер,
5
@PeteBecker нет, это не так. EBCDIC произносится как eb -see-dick.
Майк Накис
19

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

  • все ли биты равны нулю (то есть равные условия),
  • знаковый бит результата
  • бит переноса вычитания (т.е. 33-й бит старшего разряда на 32-битном компьютере)

При правильной комбинации тестирования этих трех битов после операции вычитания мы можем определить все подписанные реляционные операции, а также все беззнаковые реляционные операции (эти биты также определяют, как обнаруживается переполнение, подписано и не подписано). Одно и то же базовое аппаратное обеспечение ALU может использоваться совместно для реализации всех этих сравнений (не говоря уже о команде вычитания), вплоть до окончательной проверки этих трех битов состояния, которые отличаются в соответствии с желаемым сравнительным сравнением. Таким образом, это не так много дополнительного оборудования.

Единственная реальная стоимость - это необходимость кодирования дополнительных режимов сравнения в архитектуре набора команд, что может незначительно снизить плотность команд. Тем не менее, вполне нормально, что на оборудовании есть много инструкций, которые не используются ни одним из языков.

Эрик Эйдт
источник
1
Сравнение чисел без знака не требует вычитания. это может быть достигнуто путем побитового сравнения слева направо.
Джонатан Розен
10
@JonathanRosenne Но процессоры это реализуют не так. Напротив, для процессора с двумя дополнительными компонентами почти немыслимо не реализовывать вычитание (с переносом / заимствованием или без него) в своем ALU. Сразу после этого дизайнер задумался о том, чтобы использовать это необходимое АЛУ, чтобы убить другую птицу с тем же камнем, для сравнения. Сравнение тогда просто становится вычитанием, где результат не записывается обратно в регистровый файл.
Iwillnotexist Idonotexist
4
+1: это правильный ответ на заданный вопрос. Подводя итог: потому что реализация неподписанных операций практически бесплатна, когда вы уже выполнили подписанные .
Периата Breatta
10
@PeriataBreatta Это также работает наоборот. Цифры со знаком и без знака в современных процессорах практически идентичны, что является основным моментом, который ОП не распознал. Даже инструкции сравнения одинаковы для подписанных и неподписанных - это одна из причин, почему два дополнения выиграли целые войны со
знаком
3
@svidgen> Как сказали другие ответы, все работает наоборот. Основное внимание уделяется числам без знака, которые используются практически для всего (адрес памяти, порты ввода / вывода, представления символов и т. Д.). Цифры с подписью просто дешевеют после того, как вы подписались, и пригодятся в тех редких случаях, когда они желательны.
спектры
14

Потому что, если вам нужно считать что-то, что всегда >= 0 , вы бы без необходимости сократили свое счетное пространство пополам, используя целые числа со знаком.

Подумайте об автоинкрементном INT PK, который вы можете поместить в таблицы базы данных. Если вы используете там целое число со знаком, ваша таблица хранит в HALF столько записей, сколько она могла бы для того же размера поля без НИКАКОЙ выгоды.

Или октеты цвета RGBa. Мы не хотим неловко начинать считать эту концепцию натурального числа с отрицательным числом. Число с подписью либо сломает ментальную модель, либо уменьшит вдвое пространство. Целое число без знака не только соответствует концепции, но и обеспечивает двойное разрешение.

С аппаратной точки зрения целые числа без знака просты. Они, вероятно, самая простая структура битов для выполнения математики. И, без сомнения, мы могли бы упростить аппаратное обеспечение, моделируя целочисленные типы (или даже числа с плавающей запятой!) В компиляторе. Итак, почему целые числа без знака и со знаком реализованы в аппаратном обеспечении?

Ну что ж ... производительность!

Реализовать целые числа со знаком в аппаратном обеспечении более эффективно, чем в программном обеспечении. Аппаратные средства могут быть проинструктированы выполнять математику для любого типа целого числа в одной инструкции. И это очень хорошо , потому что аппаратные средства соединяют куски более или менее параллельно. Если вы попытаетесь симулировать это в программном обеспечении, целочисленный тип, который вы выберете для «симуляции», несомненно, потребует много инструкций и будет заметно медленнее.

svidgen
источник
2
Кроме того, вы можете сохранить себе операцию при проверке границ массива. Если вы используете целое число без знака, вам нужно только проверить, что указанный индекс меньше размера массива (потому что он не может быть отрицательным).
riwalk
2
@ dan04 Это, конечно, может ... Но, если вы используете автоинкрементное int, начинающееся с 0 или 1, что является довольно распространенной практикой, вы исключаете использование половины доступных чисел. И хотя вы можете начать считать с -2 ^ 31 (или что-то еще), у вас будет потенциальный «крайний» случай в середине вашего пространства идентификаторов.
svidgen
1
Сокращение вашего поля пополам является слабым аргументом. Скорее всего, если вашему приложению требуется более 2 миллиардов, оно также требует более 4 миллиардов.
CorsiKa
1
@corsiKa: по этой причине, если требуется более 4, вероятно, потребуется 8, затем 16 и т. д. Где это заканчивается?
whatsisname
1
Как правило, @whatsisname, вы используете целочисленные типы 8, 16, 32 или 64 бита. Сказать, что unsigned лучше, потому что вы получаете все 32 бита вместо ограниченного диапазона 31 бита положительного целого пространства в байте со знаком, в большинстве случаев не имеет большого значения.
CorsiKa
9

Ваш вопрос состоит из двух частей:

  1. Какова цель целых чисел без знака?

  2. Стоят ли целые числа без знака?

1. Какова цель целых чисел без знака?

Простые числа без знака представляют класс величин, для которых отрицательные значения не имеют смысла. Конечно, вы можете сказать, что ответ на вопрос "сколько у меня яблок?" может быть отрицательным числом, если вы кому-то должны несколько яблок, но как насчет вопроса "сколько у меня памяти?" - у вас не может быть отрицательного количества памяти. Таким образом, целые числа без знака очень подходят для представления таких величин, и они имеют преимущество в том, что могут представлять в два раза больший диапазон положительных значений, чем целые числа со знаком. Например, максимальное значение, которое вы можете представить с помощью 16-разрядного целого числа со знаком, равно 32767, а с 16-разрядным целым числом без знака - 65535.

2. Стоят ли целые числа без знака?

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

CPU не имеет одного множителя для целых чисел со знаком и другого множителя для целых чисел без знака; у него есть только один множитель, который работает немного по-разному в зависимости от характера операции. Для поддержки знакового умножения требуется чуть больше схем, чем без знака, но, поскольку его нужно поддерживать в любом случае, умножение без знака предоставляется практически бесплатно, оно включено в пакет.

Что касается сложения и вычитания, то в схемотехнике вообще нет никакой разницы. Если вы прочитаете о так называемом представлении целых чисел в виде дополнения к двум, то обнаружите, что оно разработано настолько умно, что эти операции могут выполняться точно так же, независимо от природы целых чисел.

Сравнение также работает таким же образом, поскольку это не что иное, как вычитание и отбрасывание результата, единственное различие заключается в инструкциях условного перехода (перехода), которые работают, просматривая различные флаги ЦП, которые устанавливаются предшествующая (сравнительная) инструкция. В этом ответе: /programming//a/9617990/773113 вы можете найти объяснение того, как они работают на архитектуре Intel x86. Что происходит, так это то, что обозначение инструкции условного перехода как подписанной или неподписанной зависит от того, какие флаги она проверяет.

Майк Накис
источник
1
Мой вопрос предполагал все это, под алгоритмом я подразумевал, что правило для менее чем больше, чем и т. д., было другим Стоимость, которую я вижу, имеет множество дополнительных инструкций. Если высокоуровневым программам нравится видеть данные в виде битовых комбинаций, это может быть легко реализовано, скажем, компилятором
jtw
3
@jtw - но дело в том, что эти дополнительные инструкции на самом деле очень похожи на инструкции, необходимые для чисел со знаком , и почти все схемы, необходимые для них, могут быть разделены . Дополнительные затраты на реализацию обоих типов практически равны нулю.
Периата Breatta
1
да, это отвечает на мой вопрос, добавление дополнительных инструкций ветвления идет с небольшой стоимостью, и они часто полезны на практике
JTW
1
«Операции без знака требуют некоторой дополнительной обработки, когда дело доходит до деления и умножения». Я думаю, что вы имеете это в обратном направлении. Умножение и деление легче с беззнаковыми значениями. Для обработки подписанных операндов требуется дополнительная обработка.
Коди Грэй,
@CodyGray Я знал, что кто-то придет, чтобы сказать это. Вы правы, конечно. Это обоснование моего утверждения, которое я изначально опущен для краткости: ЦП не может предложить умножение и деление только без знака, потому что подписанные версии очень полезны. На самом деле, подписанные умножение и деление являются обязательными; без знака являются необязательными. Следовательно, если также предлагается unsigned , это можно рассматривать как требующее чуть больше схемы.
Майк Накис
7

Микропроцессоры изначально без знака. Числа со знаком - это то, что реализовано, а не наоборот.

Компьютеры могут работать и работают без подписанных чисел, но нам, людям, нужны отрицательные числа, поэтому была изобретена подпись.

Питер Б
источник
4
Многие микропроцессоры имеют как подписанные, так и неподписанные инструкции для различных операций.
whatsisname
1
@whatsisname: все наоборот: многие микропроцессоры имеют только неподписанные инструкции. Несколько подписали инструкции. Это связано с тем, что в арифметике с дополнением 2s значение бита одинаково, независимо от того, является ли число подписанным или не подписанным, и то, как считать число, является лишь вопросом интерпретации - следовательно, его легче реализовать как функцию компилятора. Обычно только старые микросхемы, предполагающие, что программисты не используют компиляторы, имеют причудливые подписанные инструкции, чтобы сделать читаемый код ассемблера.
Slebetman
3

Потому что у них есть еще один бит, который легко доступен для хранения, и вам не нужно беспокоиться об отрицательных числах. Там не намного больше, чем это.

Теперь, если вам нужен пример того, где вам понадобится этот дополнительный бит, есть много чего найти, если вы посмотрите.

Мой любимый пример - битборды в шахматных движках. На шахматной доске 64 квадрата, что unsigned longобеспечивает идеальное хранилище для различных алгоритмов, вращающихся вокруг генерации ходов. Учитывая тот факт, что вам нужны бинарные операции (а также операции сдвига !!), легко понять, почему легче не беспокоиться о том, что происходит, если установлен MSB. Это можно сделать с подписанным длинным, но намного проще использовать без подписанного.

riwalk
источник
3

Имея чистый математический фон, это немного более математический подход для всех, кто интересуется.

Если мы начнем с 8-битного целого числа со знаком и без знака, то мы получим в основном целые числа по модулю 256, что касается сложения и умножения, при условии, что дополнение 2 используется для представления отрицательных целых чисел (и именно так это делает каждый современный процессор) ,

Где вещи различаются в двух местах: одно это операции сравнения. В некотором смысле целые числа по модулю 256 лучше всего рассматривать как круг чисел (как целые по модулю 12 на старомодном аналоговом циферблате). Чтобы сделать числовые сравнения (это x <y) значимыми, нам нужно было решить, какие числа меньше других. С точки зрения математика, мы хотим как-то встроить целые числа по модулю 256 в набор всех целых чисел. Преобразование 8-битного целого числа, двоичное представление которого представляет собой все нули, в целое число 0 - очевидная вещь, которую нужно сделать. Затем мы можем перейти к отображению других так, чтобы «0 + 1» (результат обнуления регистра, скажем, ax и увеличения его на единицу с помощью «inc ax») переходил к целому числу 1 и так далее. Мы можем сделать то же самое с -1, например, сопоставив «0-1» с целым числом -1 и «0-1-1» в целое число -2. Мы должны убедиться, что это вложение является функцией, поэтому не может отобразить одно 8-битное целое число на два целых числа. Таким образом, это означает, что если мы отобразим все числа в набор целых чисел, то будет 0, наряду с некоторыми целыми числами меньше 0 и некоторыми больше 0. Существуют по существу 255 способов сделать это с 8-битным целым числом (согласно до какого минимума вы хотите, от 0 до -255). Затем вы можете определить «x <y» в терминах «0 <y - x».

Существует два распространенных варианта использования, для которых целесообразна аппаратная поддержка: один со всеми ненулевыми целыми числами, превышающими 0, и один с примерно 50/50, разделенными на 0. Все остальные возможности легко эмулируются путем перевода чисел с помощью дополнительного «add». и sub 'before операции, и необходимость в этом настолько редка, что я не могу вспомнить явный пример в современном программном обеспечении (поскольку вы можете просто работать с более крупной мантиссой, скажем, 16 битами).

Другая проблема заключается в отображении 8-битного целого числа в пространство 16-битных целых. -1 идет к -1? Это то, что вы хотите, если 0xFF означает -1. В этом случае разумным является расширение знака, поэтому 0xFF переходит к 0xFFFF. С другой стороны, если 0xFF должен был представлять 255, то вы хотите, чтобы он был сопоставлен с 255, следовательно, с 0x00FF, а не с 0xFFFF.

В этом и разница между операциями «сдвиг» и «арифметический сдвиг».

В конечном счете, однако, все сводится к тому, что целые числа в программном обеспечении - это не целые числа, а представления в двоичном виде, и только некоторые из них могут быть представлены. При проектировании аппаратного обеспечения необходимо сделать выбор в отношении того, что делать в аппаратном обеспечении. Поскольку с дополнением 2 операции сложения и умножения идентичны, имеет смысл представлять отрицательные целые числа таким образом. Тогда это только вопрос операций, которые зависят от того, какие целые числа должны представлять ваши двоичные представления.

Джон Аллсуп
источник
Мне нравится математический подход, но вместо того, чтобы думать просто о переходе к конкретному большему размеру, я думаю, что лучше обобщать в терминах операций над двоичными числами бесконечной длины. Вычтите 1 из любого числа, у которого самые правые k цифр равны 0, а самые правые k цифр результата будут равны 1, и можно по индукции доказать, что если выполнить математику с бесконечным числом битов, каждый бит будет равен 1. Для беззнакового математика, каждый игнорирует все, кроме нижних битов числа.
суперкат
2

Давайте рассмотрим стоимость реализации для добавления целых чисел без знака в структуру ЦП с существующими целыми числами со знаком.

Типичный процессор нуждается в следующих арифметических инструкциях:

  • ADD (который добавляет два значения и устанавливает флаг, если операция переполняется)
  • SUB (который вычитает одно значение из другого и устанавливает различные флаги - мы обсудим это ниже)
  • CMP (который по сути является «SUB и отбрасывает результат, оставляя только флаги»)
  • LSH (сдвиг влево, установите флажок при переполнении)
  • RSH (сдвиг вправо, установите флаг, если 1 сдвинут)
  • Варианты всех вышеперечисленных инструкций, которые обрабатывают перенос / заимствование из флагов, что позволяет вам удобно объединять команды в команды для работы с большими типами, чем регистры процессора
  • MUL (умножение, установка флагов и т. Д. - не всегда доступно)
  • DIV (деление, установка флагов и т. Д. - во многих архитектурах ЦП этого нет)
  • Переход от меньшего целочисленного типа (например, 16-битный) к большему (например, 32-битный). Для целых чисел со знаком это обычно называется MOVSX (перемещение со знаком расширения).

Также нужны логические инструкции:

  • Ветвь на нуле
  • Ветвь на большем
  • Филиал на меньше
  • Ветка на переполнении
  • Отрицательные версии всего вышеперечисленного

Чтобы выполнить вышеуказанные ветви для целочисленных сравнений со знаком, проще всего заставить команду SUB установить следующие флаги:

  • Нуль. Установите, если вычитание привело к значению ноль.
  • Переполнение. Установите, если вычитание заимствовало значение из старшего значащего бита.
  • Подписать. Установите бит знака результата.

Затем арифметические ветви реализуются следующим образом:

  • Ветка на нуле: если установлен нулевой флаг
  • Переход на меньшее: если флаг знака отличается от флага переполнения
  • Ветвь на большем: если флаг знака равен флагу переполнения, а флаг нуля сброшен.

Отрицания этого должны очевидно следовать из того, как они реализованы.

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

  • ADD - реализация ADD идентична.
  • SUB - нам нужно добавить дополнительный флаг: флаг переноса устанавливается, когда значение заимствовано из самого старшего бита регистра.
  • CMP - не меняется
  • LSH - не меняется
  • RSH - правое смещение для знаковых значений сохраняет значение старшего значащего бита. Для значений без знака мы должны вместо этого установить его в ноль.
  • MUL - если ваш выходной размер такой же , как вход, никакой специальной обработки не требуется (x86 делает имеют специальную обработку, но только потому , что она имеет выход в пару регистров, но обратите внимание , что этот объект на самом деле довольно редко, так что было бы более очевидный кандидат на исключение из процессора, чем неподписанные типы)
  • DIV - никаких изменений не требуется
  • Переход от меньшего к большему типу - нужно добавить MOVZX, двигаться с нулевым расширением. Обратите внимание, что MOVZX чрезвычайно прост в реализации.
  • Ветвь на нуле - без изменений
  • Ветвь на меньшее - прыгает, когда установлен флаг переноса.
  • Ветвь на большем - прыжки, если флаг переноса и ноль очищены.

Обратите внимание, что в каждом случае модификации очень просты и могут быть реализованы просто путем включения или выключения небольшого участка схемы или путем добавления нового регистра флага, который может управляться значением, которое должно быть вычислено как часть реализация инструкции в любом случае.

Поэтому стоимость добавления неподписанных инструкций очень мала . Что касается того, почему это должно быть сделано , обратите внимание, что адреса памяти (и смещения в массивах) по своей природе являются значениями без знака. Поскольку программы тратят много времени на обработку адресов памяти, наличие типа, который обрабатывает их правильно, облегчает написание программ.

Периата Breatta
источник
спасибо, это отвечает на мой вопрос, стоимость небольшая, и инструкции часто полезны
JTW
1
Двойное беззнаковое умножение является существенным при выполнении арифметики с множественной точностью и, вероятно, хорошо для улучшения общей скорости более чем в 2 раза при выполнении шифрования RSA. Кроме того, деление отличается в случаях со знаком и без знака, но так как дело без знака проще, а деление достаточно редко и достаточно медленно, так что добавление нескольких инструкций не повредит, простейшее, что можно сделать, это реализовать только деление без знака и затем оберните это с некоторой логикой обработки знака.
суперкат
2

Числа без знака существуют в основном для обработки ситуаций, когда нужно обернуть алгебраическое кольцо (для 16-разрядного типа без знака это будет кольцо конгруэнтов целых чисел 65536). Возьмите значение, добавьте любую величину меньше модуля, и разница между двумя значениями будет суммой, которая была добавлена. В качестве примера из реальной жизни, если счетчик коммунальных услуг в начале месяца читает 9995, а один использует 23 единицы, счетчик в конце месяца будет читать 0018. При использовании типа алгебраического кольца нет необходимости делать что-то особенное, чтобы справиться с переполнением. Вычитание 9995 из 0018 даст 0023, точно количество единиц, которые были использованы.

На PDP-11, машине, для которой C был впервые реализован, не было целочисленных типов без знака, но знаковые типы можно было бы использовать для модульной арифметики, которая заключена между 32767 и -32768, а не между 65535 и 0. Целочисленные инструкции в некоторых других платформы, однако, не оборачивали вещи чисто; вместо того, чтобы требовать, чтобы реализации должны были эмулировать целые числа с двумя дополнительными компонентами, используемые в PDP-11, язык вместо этого добавил типы без знака, которые в основном должны были вести себя как алгебраические кольца, и позволял типам со знаком целыми числами вести себя другими способами в случае переполнения.

В первые дни C было много количеств, которые могли превышать 32767 (общий INT_MAX), но не 65535 (общий UINT_MAX). Таким образом, стало распространенным использование беззнаковых типов для хранения таких количеств (например, size_t). К сожалению, в языке нет ничего, чтобы различать типы, которые должны вести себя как числа с дополнительным битом положительного диапазона, и типы, которые должны вести себя как алгебраические кольца. Вместо этого язык заставляет типы меньше «int» вести себя как числа, тогда как полноразмерные типы ведут себя как алгебраические кольца. Следовательно, вызывая функцию как:

uint32_t mul(uint16_t a, uint16_t b) { return a*b; }

с (65535, 65535) будет иметь одно определенное поведение в системах с int16 битами (т. е. с возвратом 1), другое поведение с int33 битами или более (с возвратом 0xFFFE0001) и неопределенное поведение в системах, где «int» находится где угодно в между [обратите внимание, что gcc обычно будет давать арифметически правильные результаты с результатами между INT_MAX + 1u и UINT_MAX, но иногда генерирует код для вышеуказанной функции, который завершается с такими значениями!]. Не очень полезно.

Тем не менее, отсутствие типов, которые ведут себя последовательно как числа или последовательно как алгебраическое кольцо, не меняет того факта, что типы алгебраических колец практически необходимы для некоторых видов программирования.

Supercat
источник