最大kビットをオンにして整数をループする最良の方法は何ですか？

Question

最大でkビットのON（ビット1）（0 < n < = 32および0 < = k < = n）を持つすべてのnビット整数をループする必要があります。たとえば、n = 4およびk = 2の場合、これらの数字は（0000、0001、0010、0100、1000、0011、0101、0110,1001,1010,1100）です。これらの数字の順序はループスルーは重要ではありませんが、それぞれが一度だけ訪問されます。

は現在、私はこの単純なアルゴリズムを使用しています：

for x = 0 to (2^n - 1) 
    count number of bits 1 in x 
    if count <= k 
     do something with x 
    end if 
end for 

私はそれがあまりにも多くの数字をループに持っているので、このアルゴリズムは非効率的だと思います。例えば、n = 32、k = 2の場合、2^32個の数字をループして、529個の数字（< = 2ビット1）のみを見つける必要があります。

私の質問です：これを行うための効率的なアルゴリズムはありますか？

Answer 1

ループカウンタをインクリメントするために、ビット単位のカウントアルゴリズムを作成する必要があります。基本的には、シーケンス内の次の数を計算するために、k '1ビットよりも少ないビットがあれば、通常はインクリメントし、k' 1ビットがあれば、最下位ビット '1'存在し、正常に増加する。

標準カウンタでは、最下位ビットに1を加えてキャリーするという別の方法があります。あなたのケースでは、k個の '1'があるときは、1を最下位の '1'ビットに追加します。例えば

kが2であり、あなたがそうあなたが110を取得し、1100ため0に追加1010最後0を無視して101をインクリメントしている。場合ここ

番号をインクリメントするための擬似コードである：

Count 1 bits in current number 
If number of 1's is < k 
    number = number + 1 
Else 
    shift_number = number of 0 bits after least significant 1 bit 
    number = number >> shift_number 
    number = number + 1 
    number = number << shift_number 

Answer 2

あなたが4で2ビットを設定する必要がある場合、最下位ビットセットは第三の（0 ... 3から数えて）最大でなければならず、最高で少なくとも2番目。

ですから、あなたが16ビットのための16個のループを書くために2つのループ

for lowest in 0 to (n-k) 
    for highest in lowest + 1 to 3 
    (0000).setBit (lowest).setBit (highest) 

でループしたくない可能性があるため、あなたは再帰的なものにこのアイデアを変換することがあります。

Answer 3

以下のようにwhileループを使用できます。このループは、ビットをオンにしたときだけループします。包み、あなたのビットの何が固定されているあなたは

countbits = 0 
while num > 0 
    num = num & (num-1) 
    countbits = countbits + 1 
end while 

ブレークを使用することはできません。例：
（1000000）64であれば、それ意志一度だけループ、
（1001000）72であれば、その後2回

Answer 4

組み合わせ論。

ビット長がn、ビット数がrの整数の場合は、nCrとなります。組み合わせジェネレータを使用し、必要に応じて組み合わせを繰り返します。

Answer 5

Bit hack to generate all integers with a given number of 1sに答えて、[1,k]をループしてください。これは、最大でkビットの各整数を生成します。