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

Question

私は何かで解決するのに助けが必要な興味深いビットマスクパズルの問題を抱えています。ここに問題があります：

11010

各ビットは、コンテンツの特性を表します。Redisに保存されます。ただし、クエリを実行するには、キーをプルアップできるようにすべての組み合わせが必要です。したがって11010、これらの組み合わせが得られます。

11010
10000
10010
11000
01010
00010
01000

誰かがC++の解決策を持っていますか？

Answer 1

初期ビットマスクのサブセット数が線形であるアルゴリズムについては、ChessProgrammingWikiを参照してください。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 =ビットセット）がキーの数よりも多い場合は、問題を元に戻す方が速い場合があります。つまり、可能なキーを列挙して値をチェックする代わりに、キーのリストを取得してビットマスクに対してテストします。