Cの興味深いビットマスクパズル

Question

興味深いビットマスクパズルの問題があります。私は何かを解決するのに役立つ必要があります。ここに問題があります：

11010 

各ビットはコンテンツの特性を表します。 Redisに格納されます。しかし、それを照会するには、キーを引き上げるためにあらゆる組み合わせが必要です。だから、11010は、これらの組み合わせをもたらすであろう：

11010 
10000 
10010 
11000 
01010 
00010 
01000 

誰もがC++でソリューションを持っていますか？

Answer 1

初期ビットマスクのサブセット数が直線的なアルゴリズムについては、Chess Programming Wikiを参照してください。 nビットが1に設定されている場合、その数は2^nに等しいので、設定されたビット数で指数関数的です。

// enumerate all subsets of set d 
void enumerateAllSubsets(U64 d) { 
    U64 n = 0; 
    do { 
     doSomeThingWithSubset(n); 
     n = (n - d) & d; 
    } while (n); 
} 

Answer 2

2^n（n =ビットセット）があるキーの数より多い場合は、問題を逆転させる方が早い場合があります。つまり、可能なキーを列挙して値をチェックするのではなく、キーリストを取得してビットマスクに対してテストします。