c++ - 枚举二进制序列

Question

假设我想枚举所有 4 位模式，即从 0 (0000) 到 15 (1111)。一种方法是“真值表”方法:

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, ... 1111

这种方法相当于从十进制数 0 到 15。

另一种方法是使用格雷码，一次只翻转一位:

0000, 0001, 0011, 0010, 0110, ... 1000

我将如何以最小化位和的顺序系统地枚举所有数字？例如，类似以下内容:

0000, 0001, 0010, 0100, 1000, 0011, 0101, 1001, 0110, 1010, 1001, 0111, 1011, 1101, 1110, 1111

以 4 位为例。

最终，最好将其扩展到任何基础，但二进制情况似乎最容易实现。

编辑: 我可能应该明确表示该方法必须是生成式的，即我无法计算所有可能的序列然后对它们进行排序；解决方案必须以与指定顺序相似的顺序迭代生成序列。

Answer 1

这个有点乱七八糟的技巧

unsigned next_combination(unsigned x)
{
  unsigned u = x & -x;
  unsigned v = u + x;
  x = v  + (((v ^ x) / u) >> 2);
  return x;
}

将允许您轻松枚举所有包含相同数量 1 位的 unsigned 位组合(按升序排列)。 (参见 https://en.wikipedia.org/wiki/Combinatorial_number_system)

可以用这个算法依次枚举出一个1位、两个1位、三个1位等的所有组合。例如，对于长达 4 位的组合(如您的示例)

#define N 4u

int main()
{
  for (unsigned k = 1; k <= N; ++k)
  {
    for (unsigned subset = (1 << k) - 1; 
         subset < (1 << N); 
         subset = next_combination(subset))
      printf("%X ", subset);

    printf("\n");  
  }
}

http://coliru.stacked-crooked.com/a/0c8327c5e0611eaa

上面的维基百科链接还包含对更通用算法的描述，不依赖于任何位运算。