0

问题与标题相同。我做了两种方法。一是直截了当。生成所有位掩码

2^{n-1}

至

2^n

对于每个位掩码，检查是否存在相同数量的 1 和 0，如果是，则对其进行处理。这就是问题所在，因为我必须处理这些位掩码，而不仅仅是计算它们。

我采用了第二种方法，它在 O(2^{n/2}) 时间运行，但似乎它没有生成所有位掩码，我不知道为什么。

第二种方法是这样的：生成从 0 到 2^{n/2} 的所有位掩码并具有有效的位掩码（称为 B）我必须做这样的事情：B#~B

其中〜是负数。

例如，我有 n=6，所以我将生成长度为 3 的位掩码。

例如我有 B=101，所以 ~B 将是 010，最终位掩码将是 101010，正如我们所见，我们有相同数量的 1 和 0。

这种方法是好的还是我正在实施一些不好的事情？也许存在另一种有趣的方法？谢谢

克里斯

4

2 回答 2

2

尝试递归方法：

void printMasks(int n0, int n1, int mask) {
    if (!n0 && !n1) {
        cerr << mask << endl;
        return;
    }
    mask <<= 1;
    if (n0) {
        printMasks(n0-1, n1, mask);
    }
    if (n1) {
        printMasks(n0, n1-1, mask | 1);
    }
}

调用printMasks传递给它所需数量的 0 和 1。例如，如果您需要 3 个 1 和 3 个 0，请像这样调用它：

printMasks(3, 3, 0);
于 2011-12-16T15:14:09.330 回答
0

给定一个二进制数，有可能产生下一个更高的二进制数，它具有相同数量的“1”，对足够大以容纳所有位的字使用恒定数量的操作（假设除以两个计数的幂作为一项操作）。

确定最不重要的“1”的位置（提示：如果你减少数字会发生什么）和最不重要的“0”高于它（提示：如果你将“最不重要的1”添加到原始数字会发生什么？）您应该将最低有效位“0”更改为“1”，并将适当数量的最低有效位设置为“1”，并将中间位设置为“0”。

于 2011-12-16T21:50:12.843 回答