algorithm - ビット フリップを使用してすべての数値を k ビットで反復処理するアルゴリズム

Question

一度に1ビットずつ反転することにより、最大kビットが設定されているすべてのnビットの非負の整数を反復処理する効率的な方法を探しています。

最大で k ビットが設定された n ビットの非負の整数すべてを反復処理するために必要なビット フリップの最小数は?

k = n の場合、つまり、すべての n ビットの非負の整数を反復処理したい場合は、グレイ コードを使用できます。これには、新しい数値を取得するために 1 ビットだけを変更するという優れた特性があります。ただし、これは通常、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 でそのビットを反転します。すすいで繰り返します。