algorithm - 在C中有效地生成所有整数n，其中n&m==n（m是给定的整数）

Question

& 在 C 中是位与。

例子：

m= 21(10101)

结果：

0 16 4 1 20 5 17 21

我的代码：

for(int i=0;i<=m;i++) 
    if ((i&m)==i) printf("%d ",i);

当 m 很大时，这将非常慢。

如何快速找到结果（当答案很少时，例如 m=2^30）？

Answer 1

接受的答案是正确的，但在细节上有点稀疏，所以这就是它起作用的原因

观察到该集合{ n | n & m == n }是所有的集合，n其中的位是 中的位n的子集m。如果所有这些位都在一个从最低有效位开始的组中，则可以通过简单地从 0 计数到 来生成它们m。

但它们不一定因此分组，位之间可能有空格。这些空格应该被跳过，你如何让递增的进位跳过这些位？

好吧，您可以通过将它们设为 1 来使进位传播（不完全跳过）这些位。但这会在这些位中留下一些垃圾，必须将其清除。

因此，首先设置间隙中的位：（i | ~m等效地写为i ^ ~m或i + ~m因为~m保证中的位不会与 中的任何位重叠i）。

然后做增量（+1），然后扔掉留在间隙中的任何垃圾：& m。

总计：((i | ~m) + 1) & m.

---

对于新代码，请注意从减法中借用通过间隙传播更容易，因为为了传播间隙应该用零填充，它已经是。那么，唯一的问题是可能会在间隙中留下一些垃圾，应该用& m、总共 、清除这些垃圾(i - 1) & m。

Answer 2

i = 0
repeat
  print(i)
  i = (i + (NOT m) + 1) AND m
until i == 0

---

UPD：
更简单的代码：

i = 0
repeat
  print(i)
  i = (i - 1) AND m
until i == 0

Answer 3

一行代码：

for(i=m;i;i=(i-1)&m) printf("%d ",i);printf("0");