algorithm - 一种使用位翻转迭代所有 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 中的该位。冲洗并重复。