algorithm - 在 (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

有一个很好的方法可以做到这一点

for(int i = x ;; i = x & (i - 1)){
     print i;
     if(i == 0)
        break;
}

注意条件i = x & (i - 1)确保i总是减少并且只包含 x 中的位

请参阅 here 中的运行 Java 代码

万一x > n , 所以 i应该以 i = min(x, n - 1) & x 开头