Существуют ли компиляторы C99, где с настройками по умолчанию -1››1 != -1?

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

Если код хочет выполнить целочисленное деление со знаком на пол, кратное степени двойки, и он будет выполняться только для текущей или будущей архитектуры, существует ли реальная опасность, которую какой-либо будущий компилятор будет интерпретировать оператор сдвига вправо как делает что-нибудь еще? Если существует реальная возможность, есть ли хороший способ обеспечить ее без негативного влияния на читаемость, производительность или и то, и другое? Существуют ли какие-либо другие зависимости, которые оправдали бы прямое предположение о поведении оператора (например, код будет бесполезен в реализациях, которые не поддерживают функцию X, а реализации вряд ли будут поддерживать X, если они не используют расширенные знаками сдвиги вправо )?

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


person supercat    schedule 20.11.2013    source источник
comment
И мой любимый тест на идиотизм: если даже Microsoft сделает это так, как ожидалось, то, скорее всего, с другими компиляторами все будет в порядке. Однако я не знаю, реализует ли MSVC это, как вы ожидаете.   -  person    schedule 20.11.2013
comment
Я работаю почти исключительно с MCU, у которого даже нет права на сдвиг, поэтому его реализация ломается, если он не может разбить его на доступные инструкции. Это меньше о компиляторе и больше об аппаратной платформе. Есть несколько микроконтроллеров со странным сдвигом вправо.   -  person Sam Cristall    schedule 20.11.2013
comment
@SamCristall: В каком MCU нет правого сдвига? Я работал над некоторыми, где арифметический сдвиг вправо иногда требует на одну или две инструкции больше, чем логический сдвиг вправо [в зависимости от размера операнда и величины сдвига], но компилятор все еще генерирует код для арифметического сдвига вправо. На этом конкретном MCU сравнения без знака выполняются быстрее, чем сравнения со знаком, поэтому критичный ко времени код избегает ненужного использования чисел со знаком; если кто-то сдвигает число со знаком вправо, часто на это есть причина.   -  person supercat    schedule 20.11.2013
comment
В частности, @supercat DSP, см. Мой ответ, чтобы узнать больше об этом. MCU, о котором я говорю, может создать эквивалент, но в некоторых случаях это настолько ужасно, что лучше просто ошибиться и сообщить об этом программисту. Это в небольшой встроенной системе (‹32 КБ ОЗУ)   -  person Sam Cristall    schedule 20.11.2013
comment
Было бы ошибкой думать: «Ну, сейчас все процессоры меняются таким образом, поэтому будущие реализации C будут меняться так же», потому что компиляторы все чаще рассматривают язык абстрактно. Операторы записи, такие как >> и +, не определяют используемые процессором инструкции; они определяют операции в абстрактной машине. Когда компилятор переводит язык абстрактной машины в реальный код, он может реализовывать только функции, указанные для абстрактной машины. В частности, когда применяется оптимизация, неопределенное поведение абстрактной машины может быть преобразовано во что угодно.   -  person Eric Postpischil    schedule 20.11.2013
comment
На практике разработчики компиляторов учитывают, какой код на самом деле пишут люди, и могут разработать компилятор так, чтобы он выходил за рамки спецификации языка. Таким образом, если они считают сдвиг вправо отрицательных чисел важным поведением, они могут спроектировать компилятор так, чтобы он обрабатывал его как определенную операцию. Но разработчики компиляторов также заинтересованы в эффективности генерируемого кода, что заставляет их хотеть иметь возможность преобразовывать входной исходный код в любой допустимый выходной код, удовлетворяющий спецификации. Таким образом, при отсутствии спецификации вы не можете полагаться на авторов компиляторов, сохраняющих поведение >>.   -  person Eric Postpischil    schedule 20.11.2013
comment
@EricPostpischil: Как бы вы предложили, чтобы код выполнял деление на степень двойки, если код будет полагаться на (n+d)/d == (n/d)+1, который справедлив как для натуральных, так и для действительных чисел, а также для используемых значений? Я не знаю ни одной хорошей формулировки для деления степени двойки, кроме использования знакового сдвига, и ни одной некрасивой формулировки для деления не степени двойки [лучший подход, который я могу придумать для последнего, это добавить (UINT_MAX/d) *d, выполнить деление без знака, а затем вычесть (UINT_MAX/d); Я бы предпочел избегать таких конструкций, когда это возможно, и для степеней двойки это может быть.   -  person supercat    schedule 20.11.2013
comment
Команда транспьютера сдвига вправо была микрокодирована как цикл, эквивалентный do { value >>= 1; } while (--count);. Предварительное декремент означало, что если вы попытаетесь сдвинуться на 0, это закончится повторением 2 ^ 32 раз... с отключенными прерываниями. Это займет несколько дней.   -  person David Given    schedule 21.11.2013
comment
@DavidGiven: я помню, как читал об этом; Я почти уверен, что 32-битная машина, я почти уверен, что сдвиг вправо между 0 и 31 включительно должен работать, хотя цикл -1 2^32-1 раз был бы законным . В любом случае вопрос касался случаев, когда отрицательное значение сдвигается вправо на положительное значение.   -  person supercat    schedule 21.11.2013
comment
@supercat Да, я действительно просто поднял этот вопрос из интереса (в любом случае Transputer на самом деле не был разработан для C; я предполагаю, что компилятор должен был бы сгенерировать явную проверку для ››0). Обычно для всего странного неопределенного поведения в C есть причина, даже если она довольно архаична.   -  person David Given    schedule 21.11.2013
comment
Если ваша цель - выполнить переносимое целочисленное деление со знаком, то см. здесь.   -  person M.M    schedule 06.02.2015


Ответы (2)


Это лишь одна из многих причин, почему это так, но рассмотрим случай обработки сигнала:

1111 0001 >> 1
0000 1111 >> 1

В форме арифметики сдвига вправо (SRA), на которую вы ссылаетесь, вы получите следующее:

1111 0001 >> 1 = 1111 1000
OR
-15 >> 1 = -8

0000 1111 >> 1 = 0000 0111
OR
15 >> 1 = 7

Так в чем проблема? Рассмотрим цифровой сигнал с амплитудой 15 "единиц". Разделение этого сигнала на 2 должно дать эквивалентное поведение независимо от знака. Однако с SRA, как указано выше, положительный сигнал 15 приведет к сигналу с амплитудой 7, а отрицательный сигнал 15 приведет к сигналу с амплитудой 8. Эта неравномерность приводит к смещению постоянного тока на выходе. По этой причине некоторые процессоры DSP предпочитают реализовывать арифметический сдвиг вправо «округление до 0» или вообще другие методы. Поскольку стандарт C99 сформулирован как есть, эти процессоры по-прежнему могут соответствовать требованиям.

На этих процессорах -1 >> 1 == 0

Связанная вики

person Sam Cristall    schedule 20.11.2013
comment
И натуральные числа, и действительные числа определяют только одну форму деления, и она поддерживает аксиому, согласно которой для любых значений n и d (n+d)/d == (n/d)+1. Деление вещественных чисел также поддерживает аксиому, согласно которой (-n)/d == -(n/d). Целочисленное деление может быть определено так, чтобы поддерживать одну или другую аксиому, но не обе. Если у вас есть сигнал, который колеблется от -7 до +7 (колебание 14), деление на два заставит его колебаться от -4 до +3 (т.е. уменьшит его ровно наполовину), в то время как усеченное деление уменьшит его качели до шести. - person supercat; 20.11.2013
comment
Если кто-то хочет избежать смещения постоянного тока, смещение входа того, что в противном случае было бы делением пола, на d / 2 или d / 4, устранит большую его часть; правильное применение такого смещения при использовании усеченного деления обычно не намного проще, чем приведение операнда к положительному значению. Я не могу вспомнить ни одной поддержки DSP, которую я когда-либо видел для сдвига, который ведет себя как усеченное деление. - person supercat; 20.11.2013
comment
Что касается Wiki, идея о том, что x>>1 не делит отрицательные числа на два, зависит от того, что такое деление должно означать. Если рассматривать расширение натуральных чисел до целых как присоединение зеркальной копии целых чисел слева от нуля, то смысл деления на вещи, находящиеся по разные стороны от нуля, довольно расплывчат. Если рассматривать расширение как для каждого целого числа X (включая ноль), X-1 является целым числом, то аксиома натуральных чисел должна быть явно применима. - person supercat; 20.11.2013

Теоретически, в настоящее время в реализациях компилятора есть тонкости, которые могут злоупотреблять так называемым «неопределенным поведением», помимо того, что серверный процессор будет делать с фактическими целыми числами в регистрах (или «файлах», или местах памяти или что-то еще):

  1. Кросс-компиляторы - это обычное дело: компилятор может злоупотреблять спецификациями, зависящими от реализации, при выполнении простых вычислений. Рассмотрим случай, когда целевая архитектура реализует это одним способом, а хостинг — другим. В вашем конкретном примере константы времени компиляции могут оказаться равными 1, даже если любой вывод сборки в целевой архитектуре в противном случае даст 0 (я не могу придумать такой архитектуры). А потом опять наоборот. Не было бы никаких требований (кроме жалоб пользователей) для разработчика компилятора, чтобы в противном случае заботиться.

  2. Рассмотрим CLANG и другие компиляторы, генерирующие промежуточный абстрактный код. Ничто не мешает механике типов оптимизировать некоторые операции вплоть до последнего бита в промежуточное время на некоторых путях кода (т. е. когда код может быть сведен к константам, на ум приходит свертывание циклов), в то время как серверная часть сборки решает эту проблему во время выполнения в другие пути. Другими словами, вы могли наблюдать смешанное поведение. В такой абстракции разработчик не обязан подчиняться каким-либо стандартам, кроме того, что ожидает язык C. Подумайте о случае, когда вся целочисленная математика выполняется библиотеками арифметики произвольной точности вместо прямого сопоставления с целыми числами хост-процессора. Реализация может по какой-то причине решить, что это не определено, и вернет 0. Она может сделать это для любого знакового арифметического неопределенного поведения, и в стандарте ISO C их много, особенно упаковка и тому подобное.

  3. Рассмотрим (теоретический) случай, когда вместо полной инструкции для выполнения низкоуровневой операции компилятор перехватывает подоперацию. Примером этого является ARM с бочкообразным переключателем: явная инструкция (например, добавить или что-то еще) может иметь диапазон и семантику, но подоперация может работать с немного другими ограничениями. Компилятор может использовать это до тех пределов, где поведение может различаться, например, в одном случае можно установить флаги результата, а в другом нет. Я не могу придумать конкретный случай, когда это имеет значение, но вполне возможно, что какая-то странная инструкция может иметь дело только с подмножествами «нормального поведения в остальном», и компилятор может предположить, что это хорошая оптимизация, поскольку предполагается, что неопределенное поведение на самом деле означает неопределенное. :-)

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

Однако, сказав все это, мы также должны учитывать:

  1. Вы просили компилятор C99. Большинство странных архитектур (например, встроенные цели) не имеют компилятора C99.
  2. Большинство «крупномасштабных» разработчиков компиляторов имеют дело с очень большими базами пользовательского кода и, вообще говоря, сталкиваются с кошмарами поддержки, чрезмерно оптимизируя мелкие тонкости. Так они не делают. Или они делают это так, как это делают другие игроки.
  3. В частном случае «неопределенного поведения» целого числа со знаком обычно дополнительная беззнаковая операция является определенной операцией, т.е. я видел приведение кода со знаком к беззнаковому только для выполнения операции, а затем отбрасывание результата обратно.

Я думаю, что лучший прямой ответ, который я мог бы дать, это «вы можете предположить, что все это не имеет значения, но, возможно, вам не следует».

person Alexandre Pereira Nunes    schedule 05.02.2015
comment
Я ожидаю, что приличный кросс-компилятор должен оценивать константы времени компиляции, используя те же правила арифметики, что и код, который он генерирует для целевой системы, независимо от того, что в противном случае использовала бы хост-система. Я думаю, что моя главная мысль заключается в том, что причина того, что C оставляет неясность в отношении таких вещей, как сдвиг вправо, заключается в том, чтобы не заставлять людей платить за то, что им не нужно, но если реализации C99 в основном работают на оборудовании, где арифметический сдвиг вправо стоит столько же, сколько логический сдвиг вправо, и в тех немногих реализациях, где поставщики компилятора не генерируют код... - person supercat; 06.02.2015
comment
... для расширения знака int значений, которые сдвинуты вправо, дает ли неопределенность какую-либо пользу кому-либо, которая компенсировала бы затраты на принуждение программистов к написанию конструкций, подобных (int)((n ^ 0x80000000u) >> 4)-0x8000000? - person supercat; 06.02.2015
comment
Честно говоря, я не знаю, какое обоснование использует комитет C для понижения в должности целого числа со знаком. А потом пришла Sun и создала java с только целыми числами со знаком. Они пытаются нас разозлить. - person Alexandre Pereira Nunes; 06.02.2015
comment
Целочисленная семантика C без знака поистине ужасна, потому что язык не может решить, являются ли они числами или элементами обертывающего абстрактного алгебраического кольца чисел, конгруэнтных по модулю 2^n. Поведение uint32+int32->uint32 имеет смысл, если они являются членами абстрактного алгебраического кольца, но повышение типа имеет смысл только в том случае, если они являются числами. Я не возражаю против решения Java не поддерживать ужасный беззнаковый беспорядок C, хотя он должен был включать беззнаковые 16-битные и 8-битные величины, поскольку нет никакой двусмысленности в отношении того, как они должны себя вести. - person supercat; 06.02.2015
comment
@supercat объясните, что вы подразумеваете под продвижением типа, имеет смысл, только если это числа. Ничто не продвигает к unsigned int (кроме DSP) - person M.M; 06.02.2015
comment
@MattMcNabb: Предположим, что два 16-битных аппаратных регистра сообщают о количестве сдвинутых влево и сдвинутых вправо импульсов, полученных на каком-то входе, мод 65536, и можно гарантировать, что между событиями опроса будет получено не более 65535 импульсов. Сообщаемые значения счетчика следует рассматривать как элементы обертывающего алгебраического кольца. Если в предыдущем цикле опроса один регистр читал 65534, а в текущем - 3, значит, он получил 5 отсчетов, а не -65531. С другой стороны, если вычислить в uint16_t переменных количество кликов, что-то перемещалось вправо и влево... - person supercat; 06.02.2015
comment
... и затем хочет обновить 32-битную текущую позицию, тогда, если было 3 хода вправо и 5 ходов влево, позиция должна быть скорректирована на -2, а не на 65534; количество левых/правых импульсов, полученных в самом последнем цикле, следует рассматривать как кардинальное число. Оператор someLong += someUInt16 - anotherUInt16 будет вести себя так, как будто вычитаемые являются членами алгебраического кольца на машинах, где int составляет 16 бит, и как если бы они были количественными числами на машинах, где int длиннее. Этот пример проясняет ситуацию? - person supercat; 06.02.2015
comment
@MattMcNabb: Если бы я разрабатывал язык, операции между членом кольца и числом давали бы член того же кольца, а неявное преобразование числа в кольцо добавляло бы это число к нулю кольца. Операции между членами разных колец или неявные преобразования членов кольца в числа будут запрещены. Таким образом, вышеупомянутый some32bitThing += someRing16 - anotherRing16 отказался бы компилироваться, если бы правая часть не была переписана однозначно: либо (int16)(someRing16-anotherRing16), либо (cardinal16)someRing16-(cardinal16)anotherRing16. - person supercat; 06.02.2015
comment
@supercat это хорошо, но не совсем относится к C . В итоге вы получите какой-то беспорядок, такой как Java, где нормальный код должен иметь приведения повсюду, потому что нет неявного преобразования. - person M.M; 07.02.2015
comment
@MattMcNabb: Если бы типы были реализованы так, как я хотел бы их видеть, в основном потребовалось бы приведение типов в местах, где разные компиляторы C в настоящее время делают разные вещи. Если бы совместимость с существующим кодом не требовалась, я бы предпочел someUInt32 += firstUInt16-secondUInt16; отказаться от компиляции, чем выполнять разные вычисления на разных машинах. Кроме того, во многих случаях проверка переполнения была бы желательной и стоила бы затрат во время выполнения, если бы был способ отличить переполнения, которые должны быть помечены, от вычислений, которые должны быть просто перенесены. - person supercat; 07.02.2015
comment
@supercat, возможно, вы сможете перейти на C++, где вы действительно сможете писать код, который делает то, что вы хотите - person M.M; 07.02.2015
comment
@MattMcNabb: Если язык не позволяет использовать константы времени компиляции определяемых пользователем типов (я не думаю, что это делает С++), я не вижу хорошей замены встроенной в компилятор надежной числовой системе типов. В настоящее время существует как минимум три основных диалекта C: C с 16-битным int (по-прежнему популярен в мире встраиваемых систем), C с 32-битным int (в настоящее время наиболее популярным) и C с 64-битным int. Я хотел бы видеть язык, который позволял бы легко писать код, который корректно работал бы на всех трех платформах, используя при этом оптимальный размер переменных на каждой из них. - person supercat; 07.02.2015