Почему 32-разрядные целые числа не срабатывают влево, сдвиг «<<», как ожидается, если их использовать более 32 раз? - PullRequest
Новая
       28

Почему 32-разрядные целые числа не срабатывают влево, сдвиг «<<», как ожидается, если их использовать более 32 раз?

58 голосов
/ 13 сентября 2011

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

#include <iostream>

int main()
{
    int a = 1;
    std::cout << (a << 32) << std::endl;

    return 0;
}

Но по логике, поскольку сказано, что биты теряются, если они переполняют битовую ширину, вывод должен быть 0. Что происходит?

Код на Ideone, http://ideone.com/VPTwj.

Ответы [ 9 ]

43 голосов
/ 13 сентября 2011

В C ++ смещение четко определено, только если вы сдвигаете значение на несколько шагов меньше, чем размер типа.Если int составляет 32 бита, то только от 0 до 31 шага и более четко определены.

Итак, почему это так?

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

Ответ на вопрос в комментарии

C и C ++ предназначены для максимально быстрой работы на любом доступном оборудовании.Сегодня сгенерированный код - это просто команда 'shift', независимо от того, как базовое оборудование обрабатывает значения за пределами указанного диапазона.Если бы языки указали, как должен вести себя сдвиг, сгенерированный мог бы проверить, находится ли счетчик сдвигов в диапазоне, прежде чем выполнять сдвиг.Как правило, это даст три инструкции (сравнение, ветвь, сдвиг).(По общему признанию, в этом случае это не было бы необходимо, поскольку счетчик сдвигов известен.)

40 голосов
/ 19 сентября 2011

Это вызвано комбинацией неопределенного поведения в C и того факта, что код, сгенерированный для процессоров IA-32, имеет 5-битовую маску, примененную к счетчику сдвигов. Это означает, что на процессорах IA-32 диапазон числа смен составляет только 0-31 . 1

С Язык программирования C 2

Результат не определен, если правый операнд отрицательный или больше или равен числу битов в типе левого выражения.

Из IA-32 Руководство разработчика программного обеспечения для архитектуры Intel 3

8086 не маскирует счет смены. Однако все остальные процессоры IA-32 (начиная с процессора Intel 286) маскируют число сдвигов до 5 битов, что приводит к максимальному счету 31. Эта маскировка выполняется во всех режимах работы (включая режим virtual-8086) для уменьшить максимальное время выполнения инструкций.


1 http://codeyarns.com/2004/12/20/c-shift-operator-mayhem/

2 A7.8 Операторы сдвига, Приложение A. Справочное руководство, Язык программирования C

3 SAL / SAR / SHL / SHR - Shift, глава 4. Справочник по наборам инструкций, IA-32 Руководство разработчика программного обеспечения для архитектуры Intel

21 голосов
/ 13 сентября 2011

Это неопределенное поведение в соответствии со стандартом C ++:

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

12 голосов
/ 13 сентября 2011

Ответы Lindydancer и 6502 объясняют, почему (на некоторых машинах) печатается 1 (хотя поведение операции не определено). Я добавляю детали на случай, если они не очевидны.

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

movl $32, %ecx
sall %cl, %eax

По теме sall и других операций смены на стр. 624 Справочного руководства Set Instructions сказано:

8086 не маскирует счет смены. Тем не менее, все остальные процессоры архитектуры Intel (начиная с процессора Intel 286) маскируют число сдвигов до пяти бит, что приводит к максимальное количество 31. Эта маскировка выполняется во всех режимах работы (включая виртуальную-8086 режим), чтобы уменьшить максимальное время выполнения инструкций.

Поскольку младшие 5 битов 32 равны нулю, то 1 << 32 эквивалентно 1 << 0, что 1.

Экспериментируя с большими числами, мы предсказали бы, что 

cout << (a << 32) << " " << (a << 33) << " " << (a << 34) << "\n";

напечатает 1 2 4, и это действительно то, что происходит на моей машине.

9 голосов
/ 13 сентября 2011

Это не работает, как ожидалось, потому что вы ожидаете слишком многого.

В случае x86 аппаратное обеспечение не заботится об операциях сдвига, где счетчик больше, чем размер регистра (см., Например, описание инструкции SHL в справочной документации по x86 для объяснения).

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

С этой свободой разработчики компиляторов могут генерировать только одну инструкцию по сборке без какого-либо теста или ветвления.

Более «полезный» и «логический» подход мог бы, например, иметь (x << y), эквивалентный (x >> -y), а также обрабатывать большие счетчики с логическим и последовательным поведением.

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

Учитывая, что в этих случаях разные аппаратные средства делают разные вещи, стандарт говорит: «Что бы ни случилось, если вы делаете странные вещи, просто не обвиняйте C ++, это ваша вина», переведенное на юридический язык.

8 голосов
/ 13 сентября 2011

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

Серьезно, большую часть времени вывод будет равен 0 (если int - это 32 бита или меньше), поскольку вы сдвигаете 1, пока он снова не упадет и не останется ничего, кроме 0.Но компилятор может оптимизировать его так, чтобы он делал все, что ему нравится.

См. Отличную запись в блоге LLVM Что должен знать каждый программист C о неопределенном поведении , обязательное чтение для каждого разработчика C.1008 *

5 голосов
/ 13 сентября 2011

Так как вы сдвигаете бит на 32 бит;вы получите: warning C4293: '<<' : shift count negative or too big, undefined behavior в VS.Это означает, что вы выходите за пределы целого числа, и ответ может быть НИЧЕГО, потому что это неопределенное поведение.

0 голосов
/ 23 марта 2017

У меня была такая же проблема, и это сработало для меня:

f = ((long long) 1 << (i-1)); </p>

Где я могу быть на целое большечем 32 бита.1 должно быть 64-битным целым числом, чтобы сдвиг работал.

0 голосов
/ 19 сентября 2011

Вы можете попробовать следующее. Это фактически дает вывод как 0 после 32 левых сдвигов. 

#include<iostream>
#include<cstdio>

using namespace std;

int main()
{
  int a = 1;
  a <<= 31;
  cout << (a <<= 1);
  return 0;
}
...