C++ 中有趣的位掩码拼图 [英] Interesting bitmask puzzle in C++

问题描述

我有一个有趣的位掩码难题，我需要帮助解决一些问题.问题来了:

I have an interesting bitmask puzzle problem I need help solving in something. Here is the problem:

11010

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

Each bit represents a characteristic of a piece of content. It is stored in Redis. But to query it, we need every combination so that we can pull up the key. So 11010 would yield these combinations:

11010
10000
10010
11000
01010
00010
01000

有人在 C++ 中有解决方案吗?

Anyone have a solution in C++?

推荐答案

参见 Chess Programming Wiki 用于在初始位掩码的子集数量上呈线性的算法.当 n 位设置为 1 时，该数字等于 2^n，因此它是设置位数量的指数.

See the Chess Programming Wiki for an algorithm that is linear in the number of subsets of the initial bitmask. With n bits set to 1, that number is equal to 2^n, so it's exponential in the number of set bits.

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

这篇关于C++ 中有趣的位掩码拼图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！