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 Communityを使用しており、ソリューションをx64モードでコンパイルしています。 この現象は何の原因ですか？どうすればこれを回避できますか？

Answer 1

問題は1リテラルsigned int一定であるということである - ので、シフトは（明らかにあなたのコンパイラの符号を含めちょうど32ビットである）signed intシフトとして行われ、それは未定義の動作につながる、オーバーフローしています。

1ULL << 32（または他のシフト量を使用してください） - ULL接尾辞は、希望する結果のタイプに一致する定数をunsigned long longにします。シフト量がunsigned long longのために大きすぎると、これはまだオーバーフローするかもしれませんが、それまではうまくいくでしょう。