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

Question

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

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

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

Но в 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 и почему оператор правого сдвига вызывает только поведение, определенное реализацией?

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

Answer 1

Скопированный вами абзац говорит о неподписанных типах. Поведение не определено в C++. Из последней версии C++0x:

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

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

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

Answer 2

В C операция побитового сдвига влево вызывает неопределенное поведение, когда левый боковой операнд имеет отрицательное значение. [...] Но в 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 не особенно полезен. Таким образом, текущее состояние определенно лучше, чем требование, чтобы освобожденные биты были заполнены нулями, потому что это оставляет место для машин, которые делают расширения знака - даже если это не гарантируется.

Answer 3

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

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

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

Мой вывод:

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

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

  я * (1u << k)

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

Answer 4

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

Answer 5

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

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

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

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

Я думаю, что вторая причина - потенциальное изменение знака на машине комплимента 2. Но я никогда не читал это нигде (без обид @sellibitze (и я с ним согласен)).

Answer 6

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

Обязательное поведение 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 будет вполне законным.

Answer 7

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

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

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

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

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

Answer 8

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