Почему операция сдвига влево вызывает неопределенное поведение, когда левый операнд имеет отрицательное значение?

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

Соответствующая цитата из ISO C99 (6.5.7 / 4)

Результатом E1 << E2 является E1 сдвинутая влево битовая позиция E2; освобожденные биты заполняются нулями. Если E1 имеет тип без знака, значение результата будет E1 × 2E2, уменьшено по модулю на единицу больше максимального значения, представляемого в типе результата. Если E1 имеет тип со знаком и неотрицательное значение, а E1 × 2E2 представимо в типе результата, то есть полученное значение; иначе,поведение не определено.

Но в C ++ поведение четко определено.

ISO C ++ - 03 (5.8 / 2)

Значение E1 << E2 - это E1 (интерпретируется как битовая комбинация) смещенных влево битовых позиций E2; освобожденные биты заполнены нулями. Если E1 имеет тип без знака, значение результата равно E1, умноженному на величину 2, возведенную в степень E2, по модулю ULONG_MAX + 1, если E1 имеет тип unsigned long, в противном случае UINT_MAX + 1. [Примечание: константы ULONG_MAX и UINT_MAX определены в заголовке). ]

Это означает

int a = -1, b=2, c;
c= a << b ;

вызывает неопределенное поведение в C, но поведение хорошо определено в C ++.

Что заставило комитет ISO C ++ считать, что поведение четко определено, а не поведение в C?

С другой стороны, поведениеimplementation defined для операции побитового сдвига вправо, когда левый операнд отрицательный, верно?

Мой вопрос: почему операция левого сдвига вызывает неопределенное поведение в C и почему оператор правого сдвига вызывает только поведение, определенное реализацией?

П.С .: Пожалуйста, не давайте ответов типа «Это неопределенное поведение, потому что стандарт так говорит». :П

 Ben Voigt19 июл. 2014 г., 22:08
Это неопределенное поведение, потому что Стандарт говорит так в 5p5.
 fredoverflow24 сент. 2010 г., 10:31
C и C ++ - это разные языки, стандартизированные разными комитетами. Я не вижу ничего удивительного в этом.
 David Thornley24 сент. 2010 г., 20:07
Кроме того, C ++ был основан на C89 / C90. Затем комитет C двигался в разных направлениях для C99. C99 и C ++ основаны на оригинальном стандарте C, но расхождения не были согласованы вообще.
 legends2k12 июн. 2014 г., 10:12
Я вижу, что в более ранних стандартах было такое различие, но стандарты C99 и C ++ 11 являются встроенными со сдвигами как влево, так и вправо для целых типов со знаком и без знака, требующих одинакового поведения.
 R..25 сент. 2010 г., 03:20
Ваша цитата C ++ только определяет поведение, когда тип без знака. Вы забыли скопировать абзац о подписанных значениях?
 Johannes Schaub - litb25 сент. 2010 г., 22:47
@R .. текст определяет поведение подписанного его первым предложением. Затем он более подробно описывает поведение неподписанных другими предложениями.

Ответы на вопрос(8)

как умножение только тогда, когда числа представлены как дополнение к двум. Но проблема не только в отрицательных числах. Рассмотрим 4-битное число со знаком, представленное в избытке-8 (он же двоичное смещение). Число 1 представляется как 1 + 8 или 1001. Если мы сместим это значение в битах, мы получим 0010, что является представлением для -6. Точно так же -1 представляется как -1 + 8 0111, который становится 1110 при смещении влево, что соответствует +6. Побитовое поведение четко определено, но числовое поведение сильно зависит от системы представления.

 supercat20 авг. 2018 г., 17:46
Под C89 ваше утверждение было бы правильным. C99, однако, одновременно добавил явное утверждение о том, что сдвиг влево отрицательного значения приводит к неопределенному поведению, в то же время фактически запрещая что-либо, кроме двух реализаций дополнения на машинах с размером слова 64 бита или меньше (насколько я могу сказать, количество ненастроенных реализаций C99, не дополняющих два, равно нулю).
 Reality Pixels01 апр. 2016 г., 20:48
Я вижу, что я получил пару отрицательных оценок за этот пост. Я ожидаю, что это происходит из-за конфликта с утверждением в спецификации "Значение E1 << E2 - это смещенные влево позиции E1 в битах E2; освобожденные биты заполнены нулями. Если E1 имеет тип без знака, значение результат E1 × 2E ^ 2 .... ". Представление избытка N не имеет этого свойства. Это означает, что C / C ++ не может быть реализован для спецификации на такой машине.

как в C ++ 11 и C99, вам просто нужно выйти за рамки правила для сдвига влево.

Раздел 5p5 стандарта гласит, что:

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

Выражения смещения влево, которые специально вызываются в C99 и C ++ 11 как неопределенное поведение, являются теми же самыми, которые оценивают результат за пределами диапазона представимых значений.

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

 supercat02 апр. 2016 г., 20:55
В любом случае, результат любой операции, безусловно, должен находиться в диапазоне указанных типов. Только для системы знаковых величин должны быть какие-то реальные проблемы.
 supercat02 апр. 2016 г., 20:54
В понятии с двумя дополнениями побитовое представление -1 равно ... 111 [111] .000 ... с компьютерами, которые часто просто хранят среднюю часть, дублируя MSB влево и дополняя нулями правое; сдвиг влево на один бит должен дать ... 111 [110] .000 ... т.е. -2. В нотации дополнения -1 - это ... 111 [110] .111 ... с компьютерами, хранящими среднюю часть и дублирующими самый левый бит с обеих сторон. Сдвиг влево должен дать ... [101] .111 ..., то есть -2, хотя некоторые реализации могут сдвигаться в ноль, а не дублировать знаковый бит.

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

Для операции сдвига влево, если значение положительное или 0, определение оператора как умножения со степенью 2 имеет смысл, так что все в порядке, если результат не переполняется, ничего удивительного.

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

Мой вывод:

если вы хотите выполнять операции с реальными битовыми шаблонами, используйте типы без знака

если вы хотите умножить значение (подписанное или нет) на степень два, просто сделайте это, что-то вроде

я * (1u << k)

Ваш компилятор превратит это в достойный ассемблер в любом случае.

Решение Вопроса

является неопределенный в C ++. Из последней версии C ++ 0x:

Значение E1 << E2 - это биты E2, сдвинутые влево E1; освобожденные биты заполнены нулями. Если E1 имеет тип без знака, значение результата равно E1 × 2E ^ 2, уменьшенное по модулю на единицу больше максимального значения, представляемого в типе результата. В противном случае, если E1 имеет тип со знаком и неотрицательное значение, а E1 × 2E ^ 2 представимо в типе результата, то это результирующее значение;в противном случае поведение не определено.

РЕДАКТИРОВАТЬ: взглянул на C ++ 98 бумаги. Это просто не упоминает подписанные типы вообще. Так что это все еще неопределенное поведение.

Отрицательный сдвиг вправо определяется реализацией, верно. Зачем? На мой взгляд: это легко реализовать-определить, потому что нет никаких усечений из левых вопросов. Когда вы сдвигаетесь влево, вы должны сказать не только то, что сдвинуто вправо, но и то, что происходит с остальными битами, например, с представлением двух дополнений, что является другой историей.

 Ben Voigt19 июл. 2014 г., 22:03
@ JohannesSchaub-litb: Это явно не определено из-за 5p5: «Если во время вычисления выражения результат не определен математическиили нет в диапазоне представимых значений для его типа, поведение не определено ". Вы правы в том, что первая часть применяется ко всем типам, вторая часть заставляет операции над типами без знака генерировать представимое значение, потому что в противном случае сдвиг влево без знака также будет вызывать неопределенное поведение, если какие-либо биты переполнены.
 Prasoon Saurav24 сент. 2010 г., 09:51
Этот пункт не присутствует ни вC++03 ни вC++98.
 Johannes Schaub - litb25 сент. 2010 г., 22:41
@ Давид "РЕДАКТИРОВАТЬ: взглянул на документ C ++ 98. Он просто не упоминает подписанные типы вообще. Так что это все еще неопределенное поведение." Я не согласен с такой интерпретацией. «Значение E1 << E2 - это смещенные влево позиции E1 в битах E2; освобожденные биты заполнены нулями». является четким утверждением и не исключает подписанные типы. Я думаю, что они просто пропустили случай подписанных отрицательных операндов.
 David Rodríguez - dribeas24 сент. 2010 г., 09:56
@Prasoon Saurav: Этот параграф является частью текущего окончательного варианта C ++ 0x, и он показывает, что Комитет по стандартам C ++ посчитал это недостатком в текущем стандарте и исправил его, фактически заявив, что он не определен - вместо неявно не определяя результат.

что обычные процессоры могут фактически поддерживать в одной инструкции, и тем, что достаточно полезно, чтобы гарантировать, что разработчики компиляторов гарантируют, даже если для этого требуются дополнительные инструкции. Как правило, программист, использующий операторы сдвига битов, ожидает, что они будут сопоставляться с отдельными инструкциями на процессорах с такими инструкциями, поэтому существует неопределенное поведение или поведение реализации, где процессоры по-разному обрабатывают «граничные» условия, а не предписывают поведение и выполняют операцию. быть неожиданно медленным Имейте в виду, что дополнительные инструкции до / после или обработки могут быть сделаны даже для более простых случаев использования. неопределенное поведение, возможно, было необходимо, когда некоторые процессоры генерировали прерывания / исключения / прерывания (в отличие от исключений типа try / catch типа C ++) или, как правило, бесполезные / необъяснимые результаты, в то время как набор процессоров, рассматриваемый Комитетом по стандартизации в то время, предоставлен на хотя бы какое-то определенное поведение, тогда они могли бы определить реализацию поведения.

 supercat18 апр. 2015 г., 01:28
Лично я нахожу такую ​​сверхсовременную мысль тревожной; сценарий таблицы переходов, который обрабатывает только до 63 и выпадает из-за чего-то большего, был бы правдоподобным оправданием, но маскирование в худшем случае добавило бы одну инструкцию к тому, что даже в лучшем случае было бы последовательностью команд 4-5.
 David Stone09 мар. 2012 г., 03:26
Что ж, благодаря правилу «как будто», компилятору нужно только добавить столько инструкций сдвига в такой архитектуре, сколько в числе битов. Таким образом, для 64-битного числа он может реализовать его максимум за 64 смены (или либо установить на 0, либо на 63, в зависимости от того, как компилятор решит его реализовать).
 supercat21 нояб. 2011 г., 01:07
Из того, что мне сказали, на некоторых процессорах инструкция shift-left-N будет выполнять N сдвигов. Если N - это long, который содержит -1, для этого потребуется примерно четыре миллиарда циклов. Наличие инструкции, которая обычно занимает несколько микросекунд вместо того, чтобы заблокировать процессор на много минут, является достаточно странным побочным эффектом, поэтому было бы справедливо считать это «неопределенным поведением», а не просто говорить, что значение равно «реализация- «определено», тем более что выполнение одной инструкции в течение этого времени может привести к сбросу ЦП чем-то вроде сторожевого таймера.
 supercat18 апр. 2015 г., 01:25
К сожалению, с тех пор, как вы написали выше, все изменилось. Даже при работе на процессоре с инструкцией левого сдвига, которая будет вести себя точно так, как можно было бы ожидать в арифметике с двумя дополнениями, гиперсовременная философия компилятора показала бы, что нет причин заставлять поведение такого левого сдвига подчиняться законам время и причинность. Современная философия диктует, что, учитываяif (x >= 0) launch_missiles(); x<<=1; компилятор должен признать, что ему разрешено делать все, что ему нравится, если x отрицателен, и поэтому он может запускать ракеты безоговорочно.

почему операция левого сдвига вызывает неопределенное поведение в C и почему оператор правого сдвига вызывает только поведение, определенное реализацией?

Люди из LLVM предполагают, что оператор сдвига имеет ограничения из-за способа реализации инструкции на различных платформах. ОтЧто каждый программист C должен знать о неопределенном поведении # 1/3:

... Я предполагаю, что это произошло из-за того, что лежащие в основе операции сдвига на разных процессорах делают с этим разные вещи: например, X86 усекает 32-битное значение сдвига до 5 бит (таким образом, сдвиг на 32 бита аналогичен сдвигу на 0 бит), но PowerPC усекает 32-битное смещение до 6 бит (поэтому смещение на 32 приводит к нулю). Из-за этих аппаратных различий поведение полностью не определяется C ...

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

I считать Вторая причина - потенциальное изменение знака на машине комплимента 2. Но я никогда нигде не читал (не обижайся на @sellibitze (и я с ним согласен)).

 Ben Voigt19 июл. 2014 г., 22:15
Вы, кажется, обсуждаете подписьправо операнд; вопрос только смотрит на левый.

когда левый боковой операнд имеет отрицательное значение. [...] Но в C ++ поведение четко определено. [...] Зачем [...]

Простой ответ: потому что стандарты говорят так.

Более длинный ответ: вероятно, это как-то связано с тем фактом, что C и C ++ допускают и другие представления для отрицательных чисел, кроме дополнения 2. Предоставление меньшего количества гарантий относительно того, что произойдет, позволяет использовать языки на другом оборудовании, включая неясные и / или старые машины.

По какой-то причине комитет по стандартизации C ++ захотел добавить небольшую гарантию об изменении представления битов. Но так как отрицательные числа все еще могут быть представлены через дополнение 1 или знак + величина, результирующие значения значения по-прежнему варьируются.

Предполагая 16-битные целые, мы будем иметь

 -1 = 1111111111111111  // 2's complement
 -1 = 1111111111111110  // 1's complement
 -1 = 1000000000000001  // sign+magnitude

Сдвинемся влево на 3, получим

 -8 = 1111111111111000  // 2's complement
-15 = 1111111111110000  // 1's complement
  8 = 0000000000001000  // sign+magnitude

Что заставило комитет ISO C ++ считать, что поведение четко определено, а не поведение в C?

Я предполагаю, что они дали эту гарантию, чтобы вы могли использовать << надлежащим образом, когда вы знаете, что делаете (т.е. когда вы уверены, что ваша машина использует дополнение 2).

С другой стороны, поведение определяется реализацией для операции побитового сдвига вправо, когда левый операнд отрицательный, верно?

Я должен был проверить стандарт. Но вы можете быть правы. Сдвиг вправо без расширения знака на машине с комплементом 2 не особенно полезен. Таким образом, текущее состояние определенно лучше, чем требовать, чтобы освобожденные биты были заполнены нулями, потому что это оставляет место для машин, которые делают расширения знака - даже если это не гарантируется.

 supercat24 авг. 2016 г., 00:24
Одна из целей при написании Стандарта состояла в том, чтобы, насколько это возможно, заверить, что если какая-либо реализация принесет что-то полезное в определенной ситуации, соответствующая реализация должна иметь возможность вести себя аналогичным образом. Случаи, когда реализация может оказаться полезной за пределами юрисдикции Стандарта, помечены как вызывающие неопределенное поведение. Авторы Стандарта Си могли представить, что некоторые реализации могут перехватывать при сдвиге влево по крайней мере некоторые отрицательные значения, и кто-то может найти это полезным, поэтому поведение остается неопределенным.
 supercat24 авг. 2016 г., 00:26
Некоторые существующие реализации заполнены нулями при сдвигах вправо, в то время как другие расширены знаками, и потому что некоторый код, написанный для предыдущих реализаций, мог полагаться на поведение, которое было оставлено как Определено реализацией. Я думаю, что комитет C ++ исправил поведение левого сдвига, когда они осознали, что, хотя вполне возможно, что некоторые платформы могут перехватывать при отрицательных значениях, сдвигаемых влево, на самом деле ни одна из них не сделала этого, и было нечего получить, позволив запускать будущие реализации делать это.

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

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

К сожалению, даже при том, что никогда не было никаких реализаций C99, которые не используют математику с двумя дополнениями, авторы C11 отказались определять поведение общего случая (не переполнение); IIRC утверждал, что это помешает "оптимизации". Наличие оператора левого сдвига вызывает неопределенное поведение, когда левый операнд является отрицательным, позволяет компиляторам предполагать, что смещение будет достижимо только тогда, когда левый операнд неотрицателен. Это позволяет компиляторам получать код вроде:

int do_something(int x)
{
  if (x >= 0)
  {
    launch_missiles();
    exit(1);
  }
  return x<<4;
}

признать, что такой метод никогда не будет вызываться с отрицательным значением дляxи, таким образом,if тест может быть удален иlaunch_missiles() звонок сделан безоговорочно. посколькуexit известно, что не возвращает, компилятор также может пропустить вычислениеx<<4, Если бы не такое правило, программист должен был бы вставить какую-то неуклюжую__assume(x >= 0); Директива запрашивает такое поведение, но делает сдвиги влево отрицательных значений Undefined Behavior избавляет от необходимости иметь программиста, который явно хочет, чтобы такая семантика (в силу выполнения сдвига влево) загромождала код с ними.

Обратите внимание, кстати, в гипотетическом событии, которое код вызывалdo_something(-1), это будет связано с неопределенным поведением, поэтому вызов launch_missiles будет совершенно законным.

 Björn Lindqvist23 июн. 2015 г., 15:18
Но этоreturn x<<4; строка, которая запускает UB и компилятор, едва ли может изменить четко определенную семантику кода, предшествующего этой строке. Я проверил с обоими-O2 а также-O3 и, по крайней мере, gcc не выполняет ту оптимизацию, которую вы предлагаете.
 supercat24 июн. 2015 г., 15:37
@ BjörnLindqvist: Из того, что я прочитал, видно, что сдвиг влево отрицательного числа изначально оставлялся неопределенным поведением, чтобы учесть возможность того, что где-то может существовать машина, в которой она будет вызывать ловушку; учитывая отсутствие доказательств того, что такие машины когда-либо существовали, Комитет рассмотрел вопрос об изменении спецификации, чтобы она просто приводила к неопределенному значению, но авторы компилятора возразили против изменения, заявив, что оно «затруднит оптимизацию». Мой ответ был, возможно, чрезмерно запутанным, но, учитывая, что исследователи компиляторов работают над поиском способов удаления кода, который бы ...
 supercat23 июн. 2015 г., 17:34
«(1) Когда дан правильный входной сигнал, выведите действительный выходной сигнал; (2) Соблюдайте законы времени и причинности даже при наличии недопустимого входного сигнала», чтобы удовлетворить такие требования, даже если происходят такие вещи, как арифметическое переполнение, но Стандарт не предъявляет таких требований.
 supercat24 июн. 2015 г., 15:40
... уместно только в тех случаях, когда код вызывает неопределенное поведение (концепция, которая может быть полезна для некоторых форм UB, но, безусловно, бесполезна для других), моя интерпретация их желания сохранить левое смещение отрицательного значения Undefined - это что они хотят, чтобы компилятор предположил, что никакое значение, которое будет смещено влево, никогда не будет отрицательным, и пропустит любой код, который будет релевантным только тогда, когда значение, которое будет смещено влево, будет отрицательным.
 supercat23 июн. 2015 г., 17:32
@ BjörnLindqvist: Текущая версия gcc для основной строки не выполняет удаление мертвого кода настолько агрессивно, насколько позволяет стандарт, но в стандарт был добавлен язык, в котором прямо говорится, что если выполнение кода с заданным вводом приведет к неопределенному поведению затем Стандарт не предъявляет никаких требований к какому-либо поведению программы, даже до того, как UB состоялся бы. Лично я думаю, что Стандарт был бы намного лучше, если бы большинство вещей, которые в настоящее время являются UB, были достаточно ограничены, чтобы это было возможно для программы, требования которой ...
 supercat24 июн. 2015 г., 15:34
@ BjörnLindqvist: компилятору разрешено начинать делать все, что он хочет, как только он может определить, что UB неизбежен с вводом, который он будет получать. Позволяя UB определенную степень освобождения от законоввремя Разумно, с точки зрения того, что это позволило бы компилятору делать такие вещи, как выражения, инвариантные к циклу подъема, без предварительной проверки, что они не вызовут переполнения. Однако язык Стандарта не ограничивает степень, в которой компиляторы могут «использовать» неопределенное поведение, и некоторые авторы стремятся максимально использовать такие возможности.

Ваш ответ на вопрос