C++ побитовый сдвиг влево на 32

Question

В настоящее время я работаю над алгоритмом грубой силы для проблемы с рюкзаком. Все работает отлично для небольших проблемных экземпляров, например 15 элементов. Но когда я запускаю свою программу для больших экземпляров, например 31 или 32, алгоритм терпит неудачу. У меня возникла проблема с бит-мутным сдвигом, который я использую, чтобы вычислить количество возможных решений. Например, с 10 пунктов программа должна сделать 2^10 итераций, поэтому я использую это заявление:

unsigned long long int setCnt = (1 << 10); 

Вычисленное значение 1024 является правильным. Но для (1 << 31) вычисленное значение равно 18446744071562067968 (макс. unsigned long long int), но должно быть 2147483648. (1 << 32) возвращает 0. Это похоже на то, что все работает нормально, если сдвинуть с 0 до 30 бит.

Я использую сообщество Visual Studio 2015 и компилирую свое решение в режиме x64. В чем причина такого поведения? Как я могу обойти это?

Answer 1

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

Попробуйте использовать 1ULL << 32 (или любую другую сумму сдвига, которую вы хотите) - суффикс ULL делает константу unsigned long long, соответствуя типу желаемого результата. Это может все еще переполняться, если сумма сдвига становится слишком большой для unsigned long long, но до этого она будет работать.