3

64 ビットで構成されるビット フィールドがあります。

long bitfield = 0;

次のように、特定のインデックスのビットを設定できます。

void Set(long index)
{
   bitfield |= 1L << (int)(index % 64);
}

つまり、インデックスが 0、64、128、... の場合はビット 0 が設定され、インデックスが 1、65、129、... の場合はビット 1 が設定されます。

質問:インデックスとカウント (または下位インデックスと上位インデックス) が与えられた場合、ループを使用せずにこの範囲内のすべてのインデックスのビットを設定するにはどうすればよいですか?

4

3 に答える 3

3 
long SetRangeMask(int lower, int upper)     // 3..7
{
   if (! (lower <= upper)) throw new ArgumentException("...");

   int size = upper - lower + 1;            // 7 - 3 + 1 = 5
   if (size >= 64) return -1;
   long mask = (1 << size) - 1;             // #00100000 - 1  = #000011111
   return mask << lower | mask >> -lower;   // #00011111 << 3 = #011111000
}
于 2012-04-05T22:55:59.537 に答える
1

次のように、 2 x -1 を使用して x ビット長のマスクを作成し、それをシフトして OR に入れることができます。

void Set( int index, int count ) {
  bitfield |= (long)(Math.Pow( 2, count ) - 1) << ((index-count) % 64);
}

更新:Math.Pow 2 の累乗を左シフトに最適化 すると思いたいのですが、そうではないかもしれません。Math.Powその場合は、 への呼び出しを対応する左シフトに置き換えることで、パフォーマンスをもう少し向上させることができます。

public void Set( int index, int count ) {
  bitfield |= ((2 << count - 1) - 1) << ((index-count) % 64);
}
于 2012-04-05T22:30:47.197 に答える
1

組み合わせたビットマスクにルックアップテーブルを使用できます

これらの質問のような特別なケースや最適化を考慮しない、本当に単純なアプローチは次のようになります。

 static readonly private long[] maskLUT = new long[64,64] { /* generated */ };

 void SetRange(long lobit, long hibit)
 {
     lobit %= 64;
     hibit %= 64;

     bitfield |= lobit<hibit? maskLUT[lobit,hibit] : maskLUT[hibit,lobit];
 }

考え:

  • [lobit...hibit]>=64の場合、hibit-lobitすべてのビットを一度に設定できる最適化を検討できます。

  • 両方の境界がラップアラウンドできるという事実を考えると、領域の接続性について少し考えなければなりません (最初に両方の境界をラップアラウンドしますか、それともラップアラウンドlobitし、デルタを使用してラップされたものhibitからを見つけますか)境界、前述の最適化と同様に?)

于 2012-04-05T22:28:38.340 に答える