一种使用位翻转迭代所有 k 位数字的算法

Question

我正在寻找一种有效的方法来迭代所有 n 位非负整数，这些整数通过一次翻转一位来设置最多 k 位。

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?

我知道如果k = n，也就是我们想要遍历所有n位非负整数，那么我们可以使用Gray code。这有很棒的属性，您只需更改一位即可获得新号码。然而，如果 k < n，这通常会通过超过 k 位的整数。

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 位数目的整数序列生成 "next" 数。 (1u << k) - 1u 是起点。当第一次溢出发生时，迭代结束。后者意味着该算法可以立即用于 n 小于 unsigned.

中的位数

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