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?
% 64
the 1L
would be shifted left by 12345 bits, resulting in bitfield |= 0;
- dtb 2012-04-05 23:00
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
}
<<
in mask = mask << lower;
is a rotating shift - dtb 2012-04-06 00:16
lower = index % 64
, make sure that (lower + range) < 64
, and then set upper = index + range
- Jim Mischel 2012-04-06 02:46
%64
explicitly - Henk Holterman 2012-04-06 07:20
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?)
maskLUT
- which I don't show. In other words: that's up to yo - sehe 2012-04-05 22:46
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);
}
%64
- Henk Holterman 2012-04-05 22:56