C++:组合算法

Question

我有一个函数(由其他人编写)，它基于一组组件构建组合。不知何故，这样做涉及位移操作，但我很难理解它。代码如下所示:

// Declarations in the header file.
vector<set<Component*, compareComponentIDs>> allScenarios;

// The function.
void System::buildAllScenarios()
{
    int x, y;

    for (x=1; x < (1 << (int)components.size()); x++){
        set<Componenet*, compareComponentIDs> curScenario;

        for(y=0; y < (int)components.size(); y++){
            if ((x >> y) & 1){
                curScenario.insert(components[y]);
            }
        }
        allScenarios.push_back(curScenario);
    }
    return;
}

假设组件的数量是 10。那么，我认为第一个 for 循环将循环 20 次，因为按位左移会将组件的数量乘以 2。第二个组件将循环 10 次，因为没有特殊操作。我不知道 if 语句正在评估什么。

有了这些信息，我的问题是:

1. 第二个 for 循环中的 if 语句如何工作？它有什么作用？
2. 为什么第一个for循环会比组件数多迭代两次。

如有任何帮助，我们将不胜感激。

Answer 1

你有 n 个可能的组件。在场景中，每个组件是否在(2 个值)。意味着您有 2^n 个潜在场景。例如，对于 3 个组件，您有 2*2*2=8 种可能性。

n 的第一个二进制移位等同于乘以 2^n(另见 iso std 第 5.8 节)。所以外层循环遍历每个场景。如果你用二进制写每个数字，你会把它写在 n 位上，每个代表一个组件。例如:

0: 000  no component
1: 001  first component in 
2: 010  second component in 
3: 011  first and second component in, etc... 

内层循环，按照这个逻辑解码出场景的编号。右移 y 位意味着使第 y 位成为最后一位。 x & 1 表示只看最后一位。它会在对应于每个组件的位上查找:如果它是 0(组件不在)或 1(组件在)。在后一种情况下，它将组件插入到一个集合中。

非常聪明和高效的算法，只要组件少于 int 中的位。为了避免与符号位相关的未定义行为，如果您有 sizeof(int)*8 组件，我建议使用 unsigned int rather 而不是 int。