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 回答