& は C のビット AND です。
例：
m= 21(10101)
結果：
0 16 4 1 20 5 17 21
私のコード:
for(int i=0;i<=m;i++)
if ((i&m)==i) printf("%d ",i);
m が大きい場合、これは非常に遅くなります。
結果をすばやく見つける方法 (m=2^30 など、答えが非常に少ない場合)
質問する
118 次
3 に答える
4
受け入れられた答えは正しいですが、詳細が少しまばらなので、それが機能する理由は次のとおりです
セットは、のビットが のビットのサブセットで{ n | n & m == n }あるすべてのセットであることに注意してください。これらすべてのビットが最下位ビットから始まるグループ内にある場合、それらは 0 から までカウントするだけで生成できます。nnmm
ただし、それらは必ずしもグループ化されているわけではないため、ビット間に空のスペースが存在する場合があります。これらのスペースはスキップする必要があります。インクリメントからのキャリーでこれらのビットをスキップするにはどうすればよいですか?
これらのビットを 1 にすることで、キャリーを (正確にスキップするのではなく) 伝播させることができます。
そのため、最初にギャップのビットを設定します( のビットは のビットと重複しないことが保証されているため、またはとi | ~m同等に記述されます)。i ^ ~mi + ~m~mi
次に、インクリメント ( +1) を実行してから、ギャップに残っているゴミを捨てます: & m。
合計: ((i | ~m) + 1) & m。
新しいコードでは、減算からの借用をギャップを介して伝播させる方が簡単であることに注意してください。これは、伝播するためにギャップをゼロで埋める必要があるためです。& m唯一の問題は、隙間にゴミが残る可能性があること(i - 1) & mです。
于 2013-05-12T15:46:02.933 に答える