6

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

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

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の場合、529個の数値（<= 2ビット1）のみを見つけるために、2^32個の数値をループする必要があります。

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

4

5 に答える 5

4

ループカウンターをインクリメントするために、独自のビット単位のカウントアルゴリズムを作成する必要があります。基本的に、シーケンス内の次の数値を計算するために、k '1'ビット未満の場合は通常どおりにインクリメントし、k '1'ビットがある場合は、最下位の'1'の後に'0'ビットを装います。存在し、正常に増分します。

別の言い方をすれば、標準のカウンターでは、最下位ビットに1を加算してキャリーします。あなたの場合、「1」がk個ある場合、最下位の「1」ビットに1を追加します。

たとえば、kが2で1010、最後を無視して0増分する場合は、 for101を取得110してから追加します。01100

数を増やすための擬似コードは次のとおりです。

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
于 2012-05-05T02:42:47.227 に答える
1

ビットハックへの答えを取得して、指定された数の1を持つすべての整数を生成し、ループオーバーし[1,k]ます。kこれにより、最大ビットの各整数が1回生成されます。

于 2012-05-05T03:38:22.133 に答える
0

4に2ビットを設定する必要がある場合、最小のビットセットは最大で3番目（0 ... 3から数えて）で、最大は少なくとも2番目である必要があります。

したがって、2つのループでループできます

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

16ビットに対して16ループを記述したくないので、このアイデアを再帰的なアイデアに変換することができます。

于 2012-05-05T02:43:29.280 に答える
0

組み合わせ論。

nビット長とrビットが設定された整数がある場合は、nCrそのような数値があります。組み合わせジェネレーターを使用し、必要に応じて組み合わせを繰り返し処理するだけです。

于 2012-05-05T03:14:39.407 に答える
-1

以下に示すように、whileループを使用できます。このループは、オンのビットがない場合にのみループします。ビット数が固定されている場合は、ブレークを使用できます

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

例：
64（1000000）の場合は1回だけループし、
72（1001000）の場合は2回ループします

于 2012-05-05T02:57:14.893 に答える