CODEWITHSUNDEEP
c#bit-manipulation
dtb
dtb

Reputation: 217361

Set a range of bits in a circular bit field

I have a bit field consisting of 64 bits:

long bitfield = 0;

I can set the bit for a given index as follows:

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

i.e. if the index is 0, 64, 128, ... then bit 0 is set, if the index is 1, 65, 129, ... then bit 1 is set, and so on.

Question: given an index and a count (or a lower and upper index), how can I set the bits for all indexes in this range without using a loop?

Upvotes: 3

Views: 348

Answers (3)

Henk Holterman
Henk Holterman

Reputation: 273571

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
}

Upvotes: 3

Ethan Brown
Ethan Brown

Reputation: 27282

You can use 2x-1 to create a mask x bits long, then shift it and OR it in, like so:

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

Update: I like to think that Math.Pow optimizes powers of two to a left shift, but it may not. If that's the case, you can get a little more performance by replacing the call to Math.Pow with the corresponding left shift:

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

Upvotes: 1

sehe
sehe

Reputation: 393593

You could use a lookup table for combined bit masks

A real simple approach with no thought to special cases or optimizations like these questions raised, would look like:

 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];
 }

Thoughts:

  • you might consider an optimization that given [lobit...hibit], if hibit-lobit>=64 you can set all bits at once.

  • There is a bit of thought to be put in the connected-ness of regions given the fact that both boundaries can wrap around (do you wrap-around both boundaries first, or do you wraparound lobit, and use the delta to find the hibit from the wrapped boundary, like with the optimization mentioned before?)

Upvotes: 1

Related Questions