Почему операция сдвига влево вызывает неопределенное поведение, когда левый операнд имеет отрицательное значение? - PullRequest
40 голосов
/ 24 сентября 2010

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

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

Результатом E1 << E2 является E1-сдвинутая влево позиция E2; освобожденные биты заполняются нулями. Если E1 имеет тип без знака, значение результата будет E1 × 2 <sup>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 определены в заголовке). ] </p>

Это значит

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

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

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

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

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

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

Ответы [ 8 ]

32 голосов
/ 24 сентября 2010

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

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

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

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

16 голосов
/ 24 сентября 2010

В 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). </p>

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

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

7 голосов
/ 24 сентября 2010

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

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

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

Мой вывод:

  • , если вы хотите выполнять операции с битовым шаблоном, используйте типы без знака
  • , еслиВы хотите умножить значение (подписанное или нет) на степень два, просто сделайте это, например,

    i * (1u << k) </p>

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

3 голосов
/ 24 сентября 2010

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

1 голос
/ 05 апреля 2014

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

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

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

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

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

0 голосов
/ 30 марта 2016

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

0 голосов
/ 18 апреля 2015

В 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 будет совершенно законным действием.

0 голосов
/ 20 июля 2014

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

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

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

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

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

...