问题与标题相同。我做了两种方法。一是直截了当。生成所有位掩码
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。
这种方法是好的还是我正在实施一些不好的事情?也许存在另一种有趣的方法?谢谢
克里斯