Converting a range into a bit array

Question

I'm writing a time-critical piece of code in C# that requires me to convert two unsigned integers that define an inclusive range into a bit field. Ex:

uint x1 = 3;
uint x2 = 9;
  //defines the range [3-9]
  //                              98  7654 3
  //must be converted to:  0000 0011  1111 1000

It may help to visualize the bits in reverse order

The maximum value for this range is a parameter given at run-time which we'll call max_val. Therefore, the bit field variable ought to be defined as a UInt32 array with size equal to max_val/32:

UInt32 MAX_DIV_32 = max_val / 32;
UInt32[] bitArray = new UInt32[MAX_DIV_32];

Given a range defined by the variables x1 and x2, what is the fastest way to perform this conversion?

Do most cases have max_val >= 32? Otherwise it wouldn't make sense to use an array. If yes, then I assume you want to be able to say I need 200 bits set to 1 with a padding of 100 bits set to 0 on the right. — Samuel
– Samuel, Commented Mar 27, 2009 at 3:22
If your max_val is not divisible by 32, your bitArray is going to be missing some bits. — Jim Mischel
– Jim Mischel, Commented Mar 27, 2009 at 4:01
Samuel - not sure what you're getting at. Jim - Yep, I know and that's perfectly fine. — JubJub
– JubJub, Commented Mar 27, 2009 at 4:17
The mods are gone ... you will have to benchmark. I daubt a table lookup will gain significant any speed. — Daniel Brückner
– Daniel Brückner, Commented Mar 27, 2009 at 5:12
Looks beautiful. And I just discovered that the code I offered with table lookups is erroneous anyway. Thanks for the great answer! — JubJub
– JubJub, Commented Mar 27, 2009 at 5:16

Daniel Brückner · Accepted Answer · 2009-03-27 05:09:54Z

2

Try this. Calculate the range of array items that must be filled with all ones and do this by iterating over this range. Finally set the items at both borders.

Int32 startIndex = x1 >> 5;
Int32 endIndex = x2 >> 5;

bitArray[startIndex] = UInt32.MaxValue << (x1 & 31);

for (Int32 i = startIndex + 1; i <= endIndex; i++)
{
   bitArray[i] = UInt32.MaxValue;
}

bitArray[endIndex] &= UInt32.MaxValue >> (31 - (x2 & 31));

May be the code is not 100% correct, but the idea should work.

Just tested it and found three bugs. The calculation at start index required a mod 32 and at end index the 32 must be 31 and a logical and instead of a assignment to handle the case of start and end index being the same. Should be quite fast.

Just benchmarked it with equal distribution of x1 and x2 over the array. Intel Core 2 Duo E8400 3.0 GHz, MS VirtualPC with Server 2003 R2 on Windows XP host.

Array length [bits]           320         160         64
Performance [executions/s]    33 million  43 million  54 million

One more optimazation x % 32 == x & 31 but I am unable to meassure a performance gain. Because of only 10.000.000 iterations in my test the fluctuations are quite high. And I am running in VirtualPC making the situation even more unpredictable.

edited Mar 27, 2009 at 5:09

answered Mar 27, 2009 at 3:58

Daniel Brückner

59.8k16 gold badges103 silver badges144 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Jim Mischel Over a year ago

Setting the value at startIndex is wrong here. You don't want to shift left by x1. I think you want to shift left by (x1 % 32).

Daniel Brückner Over a year ago

You are right ... just started my IDE and trying the code. And there is a special situation currently not handled if all bits to set are within a single array item. I am fixing that now.

JubJub Over a year ago

This looks really good. I wonder if I can optimize out those modulus operators somehow. Actually, I don't even know if a table look-up would be faster.

JubJub Over a year ago

Spoke to soon. If anything, I would be replacing the shift operators... I wonder if that would improve performance at all.

Daniel Brückner Over a year ago

The shift operations are really fast. I would try to get the mods and the subtraction away and may be try replacing the for loop with a while loop. But I am not sure what helps most - did not do assembler optimization for a while.

|

Ronny Heuschkel · Accepted Answer · 2013-01-16 09:23:38Z

My solution for setting a whole range of bits in a BitArray to true or false:

public static BitArray SetRange(BitArray bitArray, Int32 offset, Int32 length, Boolean value)
{

    Int32[] ints = new Int32[(bitArray.Count >> 5) + 1];

    bitArray.CopyTo(ints, 0);

    var firstInt = offset >> 5;
    var lastInt = (offset + length) >> 5;

    Int32 mask = 0;

    if (value)
    {
        // set first and last int
        mask = (-1 << (offset & 31));
        if (lastInt != firstInt)
            ints[lastInt] |= ~(-1 << ((offset + length) & 31));
        else
            mask &= ~(-1 << ((offset + length) & 31));

        ints[firstInt] |= mask;

        // set all ints in between
        for (Int32 i = firstInt + 1; i < lastInt; i++)
            ints[i] = -1;
    }

    else
    {
        // set first and last int
        mask = ~(-1 << (offset & 31));
        if (lastInt != firstInt)
            ints[lastInt] &= -1 << ((offset + length) & 31);
        else
            mask |= -1 << ((offset + length) & 31);

        ints[firstInt] &= mask;

        // set all ints in between
        for (Int32 i = firstInt + 1; i < lastInt; i++)
            ints[i] = 0;

    }

    return new BitArray(ints) { Length = bitArray.Length };

}

Jim H. · Accepted Answer · 2009-03-27 02:43:47Z

0

You could try:

UInt32 x1 = 3;
UInt32 x2 = 9;
UInt32 newInteger = (UInt32)(Math.Pow(2, x2 + 1) - 1) & 
                   ~(UInt32)(Math.Pow(2, x1)-1);

answered Mar 27, 2009 at 2:43

Jim H.

5,5591 gold badge26 silver badges23 bronze badges

2 Comments

JubJub Over a year ago

I could use the left shift operator instead of Math.Pow. ie. ((2 << (x2+1))-1) & ~((2 << x1)-1), but I need to figure out how to do this over an array.

JubJub Over a year ago

perhaps instead of using the shift operator, I could use a table of pre-calculated values to improve performance.

kvb · Accepted Answer · 2009-03-27 04:12:23Z

0

Is there a reason not to use the System.Collections.BitArray class instead of a UInt32[]? Otherwise, I'd try something like this:

int minIndex = (int)x1/32;
int maxIndex = (int)x2/32;
// first handle the all zero regions and the all one region (if any)
for (int i = 0; i < minIndex; i++) {
    bitArray[i] = 0;
}
for (int i = minIndex + 1; i < maxIndex; i++) {
    bitArray[i] = UInt32.MaxValue; // set to all 1s
}
for (int i = maxIndex + 1; i < MAX_DIV_32; i++) {
    bitArray[i] = 0;
}

// now handle the tricky parts
uint maxBits = (2u << ((int)x2 - 32 * maxIndex)) - 1; // set to 1s up to max
uint minBits = ~((1u << ((int)x1 - 32 * minIndex)) - 1); // set to 1s after min

if (minIndex == maxIndex) {
    bitArray[minIndex] = maxBits & minBits;
}
else {
    bitArray[minIndex] = minBits;
    bitArray[maxIndex] = maxBits;
}

edited Mar 27, 2009 at 4:12

answered Mar 27, 2009 at 3:56

kvb

55.2k2 gold badges94 silver badges133 bronze badges

2 Comments

Jim Mischel Over a year ago

System.Collections.BitArray is convenient, but terribly slow. All those range checks can really get in the way.

JubJub Over a year ago

kvb, this looks really good. I'm going to see if I can optimize it a bit.

Samuel · Accepted Answer · 2009-03-27 04:16:04Z

I was bored enough to try doing it with a char array and using Convert.ToUInt32(string, int) to convert to a uint from base 2.

uint Range(int l, int h)
{
  char[] buffer = new char[h];
  for (int i = 0; i < buffer.Length; i++)
  {
    buffer[i] = i < h - l ? '1' : '0';
  }
  return Convert.ToUInt32(new string(buffer), 2);
}

A simple benchmark shows that my method is about 5% faster than Angrey Jim's (even if you replace second Pow with a bit shift.)

It is probably the easiest to convert to producing a uint array if the upper bound is too big to fit into a single int. It's a little cryptic but I believe it works.

uint[] Range(int l, int h)
{
  char[] buffer = new char[h];
  for (int i = 0; i < buffer.Length; i++)
  {
    buffer[i] = i < h - l ? '1' : '0';
  }

  int bitsInUInt = sizeof(uint) * 8;
  int numNeededUInts = (int)Math.Ceiling((decimal)buffer.Length /
                                         (decimal)bitsInUInt);
  uint[] uints = new uint[numNeededUInts];
  for (int j = uints.Length - 1, s = buffer.Length - bitsInUInt;
       j >= 0 && s >= 0;
       j--, s -= bitsInUInt)
  {
    uints[j] = Convert.ToUInt32(new string(buffer, s, bitsInUInt), 2);
  }

  int remainder = buffer.Length % bitsInUInt;
  if (remainder > 0)
  {
    uints[0] = Convert.ToUInt32(new string(buffer, 0, remainder), 2);
  }

  return uints;
}

Nick Borodulin · Accepted Answer · 2009-03-27 04:33:19Z

0

Try this:

uint x1 = 3;
uint x2 = 9;

int cbToShift = x2 - x1; // 6
int nResult = ((1 << cbToShift) - 1) << x1; 

/*
  (1<<6)-1 gives you 63 = 111111, then you shift it on 3 bits left
*/

answered Mar 27, 2009 at 4:33

Nick Borodulin

3,2654 gold badges24 silver badges21 bronze badges

1 Comment

JubJub Over a year ago

the range [3-9] was just a simplified example. This needs to scale up through a range of values > 32 bits using an array.

Collectives™ on Stack Overflow

Converting a range into a bit array

6 Answers 6

9 Comments

Comments

2 Comments

2 Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

9 Comments

Comments

2 Comments

2 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related