algorithm - An algorithm using bit flips to iterate over all numbers with k bits

Question

I am looking for an efficient way to iterate over all n bit non-negative integers which have at most k bits set by flipping one bit at a time.

What is the minimum number of bit flips I need to do to iterate over all n bit non-negative integers with at most k bits set?

I know that if k = n, that is we want to iterate over all n bit non-negative integers then we can use a Gray code. This has the great property that you only ever change one bit to get a new number. However this will typically go via integers with more than k bits if k < n.

Answer 1

要遍历位 0 的所有值：从任何起始值开始，然后翻转位 0。

要遍历位 0、1 的所有值：从任何起始值开始。迭代位 0 的所有值。翻转位 1。迭代位 0 的所有值。

遍历位 0-2 的所有值： 从任何起始值开始。迭代位 0、1 的所有值。翻转位 2。迭代位 0、1 的所有值。

遍历位 0-3 的所有值： 从任何起始值开始。遍历位 0-2 的所有值。翻转位 3。迭代位 0-2 的所有值。我希望系统现在很清楚。

从 i = 任意值开始，j = 0。将 j 加 1，确定 j 中设置的最低位，翻转 i 中的那个位。冲洗并重复。

Answer 2

一种已知的位摆弄技术可以如下实现（使用unsigned的是底层的 n 位整数类型）

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

它在具有相同 1 位数的整数序列中生成“下一个”数字。(1u << k) - 1u是起点。当第一次溢出发生时迭代结束。后者意味着该算法可以立即用于n小于unsigned.

（有关更详细的说明，请参阅https://en.wikipedia.org/wiki/Combinatorial_number_system 。）