c++ - C++ 中有趣的位掩码谜题

Question

我有一个有趣的位掩码难题，我需要帮助解决一些问题。这是问题所在：

11010

每个位代表一段内容的一个特征。它存储在 Redis 中。但是要查询它，我们需要每个组合，以便我们可以拉出密钥。所以11010会产生这些组合：

11010
10000
10010
11000
01010
00010
01000

有人有 C++ 的解决方案吗？

Answer 1

有关初始位掩码的子集数量呈线性的算法，请参阅国际象棋编程 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=bits set) 多于您拥有的键数，则反转问题可能会更快。也就是说，获取您的键列表并针对位掩码测试它们，而不是枚举可能的键并检查值。