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?

@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
@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
}
```

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

@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 2^{x}-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