生成长度为 n 且 1 和 0 数量相同的二进制数

Question

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

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。

这个方法好还是我实施的方法不好？也许存在另一种有趣的方法？ 谢谢克里斯

​

Answer 1

尝试递归方法：

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);

Answer 2

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

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