Set a range of bits in a circular bit field

Go To StackoverFlow.com

2

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?

2012-04-05 22:23
by dtb
I don't think you need the %64 - Henk Holterman 2012-04-05 22:56
@HenkHolterman: If the index is 12345, then bit 57 should be set. Without the % 64 the 1L would be shifted left by 12345 bits, resulting in bitfield |= 0; - dtb 2012-04-05 23:00
The << has a modulo (or a carousel) built-in - Henk Holterman 2012-04-05 23:04
@HenkHolterman: Interesting! I didn't know that - dtb 2012-04-05 23:09


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-05 22:55
by Henk Holterman
This fails for (56,80): It returns 1⁸0⁵⁶ but should return 1⁸0³⁷1¹⁷. Do you assume that the << in mask = mask << lower; is a rotating shift - dtb 2012-04-06 00:16
@dtb: Note that this code uses lower and upper bounds rather than index and count. It will work as long as lower and upper are in the range 0..63. Your best bet is to set lower = index % 64, make sure that (lower + range) < 64, and then set upper = index + range - Jim Mischel 2012-04-06 02:46
@JimMischel - lower and upper can be any positive integers, as long as upper >= lower. There's no need to do %64 explicitly - Henk Holterman 2012-04-06 07:20


1

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?)

2012-04-05 22:28
by sehe
Do you mean ~maskLUT[hibit,lobit] - dtb 2012-04-05 22:44
@dtb That depends solely on the polarity of the masks in maskLUT - which I don't show. In other words: that's up to yo - sehe 2012-04-05 22:46


0

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);
}
2012-04-05 22:30
by Ethan Brown
Ads