产生范围为(0,n)的k&x = k的解

Question

如何有效地生成内部的所有数字0,1,2...n.
(大n).
这样对于固定x和变化k (0 <= k < n),k & x = k.
这是很容易发现,与值的所有位1中k也是1在x.
但我无法计算所有这些.
我曾经DP找到设置位的所有子集和x,以得出所有可能的解决方案.

但是这种方法证明在多个这样的情况下要求不同的效率低效x.

我是否必须考虑需要改变的每一点以获得所有可能性？还有其他有效的方法吗？另外,我当然不想与所有人一起检查n.

Answer 1

首先注意x中的 0 位表示k中必须为 0 的位，而x中的 1 位可以是k中的 0 或 1 。因此，该算法应该迭代k中所有可能的位组合，其中x具有 1 位，并且结果数字 ( k ) 不大于n。

这些组合最好通过使用格雷码序列之类的东西来生成，因为人们可以在恒定时间内从一个位模式步进到下一个位模式。

例子：

x = 0b011010 (26)
n = 0b010000 (16)

为k生成的值是（按格雷码序列的顺序）：

    0b000000 ( =  0)
    0b000010 ( =  2)
    0b001010 ( = 10)
    0b001000 ( =  8)
    0b011000 ( = 24) too large: exclude
    0b011010 ( = 26) too large: exclude
    0b010010 ( = 18) too large: exclude
    0b010000 ( = 16)

由于使用格雷码方案，从一种组合到下一种组合只有一位发生变化。这意味着数字不是按顺序生成的，有些数字可能太大（> n）。这个缺点仍然是值得的，因为按顺序生成它们将涉及每步更多的位变化。

下面是在 JavaScript 中实现这个想法的代码片段：

x = 0b011010 (26)
n = 0b010000 (16)

请注意，输出未排序（因为使用了格雷码序列）。如果您需要对它们进行排序，请应用一些基数排序（或散列）。

在 JavaScript 中，考虑到值是唯一的，实现这种基数排序非常容易。但在其他语言中，您可以实现更明确、简化的基数排序。这是它的 JavaScript 函数：

    0b000000 ( =  0)
    0b000010 ( =  2)
    0b001010 ( = 10)
    0b001000 ( =  8)
    0b011000 ( = 24) too large: exclude
    0b011010 ( = 26) too large: exclude
    0b010010 ( = 18) too large: exclude
    0b010000 ( = 16)

复杂：

外部循环在n中的每个位位置迭代一次，即log(n)次，而内部循环每次迭代次数大约加倍。因此，在最坏的情况下（当x为 0 并且内部循环始终执行时），我们得到的最内部操作总数约为2 ^log(n)次，时间复杂度为O(n)。

由于x是固定的，复杂度也应该用x来表示。假设x有b个 1 位，那么时间复杂度为O(b+2 ^b )。