Defining a bit[] array in C#

Question

currently im working on a solution for a prime-number calculator/checker. The algorythm is already working and verry efficient (0,359 seconds for the first 9012330 primes). Here is a part of the upper region where everything is declared:

const uint anz = 50000000;


uint a = 3, b = 4, c = 3, d = 13, e = 12, f = 13, g = 28, h = 32;
bool[,] prim = new bool[8, anz / 10];
uint max = 3 * (uint)(anz / (Math.Log(anz) - 1.08366));
uint[] p = new uint[max];

Now I wanted to go to the next level and use ulong's instead of uint's to cover a larger area (you can see that already), where i tapped into my problem: the bool-array. Like everybody should know, bool's have the length of a byte what takes a lot of memory when creating the array... So I'm searching for a more resource-friendly way to do that. My first idea was a bit-array -> not byte! <- to save the bool's, but haven't figured out how to do that by now. So if someone ever did something like this, I would appreciate any kind of tips and solutions. Thanks in advance :)

antistar · Accepted Answer · 2014-03-07 15:05:42Z

2

You can use BitArray collection: http://msdn.microsoft.com/en-us/library/system.collections.bitarray(v=vs.110).aspx

MSDN Description: Manages a compact array of bit values, which are represented as Booleans, where true indicates that the bit is on (1) and false indicates the bit is off (0).

answered Mar 7, 2014 at 15:05

antistar

2283 silver badges8 bronze badges

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

Comments

Sten Petrov · Accepted Answer · 2014-03-07 15:50:33Z

You can (and should) use well tested and well known libraries.

But if you're looking to learn something (as it seems to be the case) you can do it yourself.

Another reason you may want to use a custom bit array is to use the hard drive to store the array, which comes in handy when calculating primes. To do this you'd need to further split addr, for example lowest 3 bits for the mask, next 28 bits for 256MB of in-memory storage, and from there on - a file name for a buffer file.

Yet another reason for custom bit array is to compress the memory use when specifically searching for primes. After all more than half of your bits will be 'false' because the numbers corresponding to them would be even, so in fact you can both speed up your calculation AND reduce memory requirements if you don't even store the even bits. You can do that by changing the way addr is interpreted. Further more you can also exclude numbers divisible by 3 (only 2 out of every 6 numbers has a chance of being prime) thus reducing memory requirements by 60% compared to plain bit array.

Notice the use of shift and logical operators to make the code a bit more efficient.

byte mask = (byte)(1 << (int)(addr & 7)); for example can be written as byte mask = (byte)(1 << (int)(addr % 8));

and addr >> 3 can be written as addr / 8

Testing shift/logical operators vs division shows 2.6s vs 4.8s in favor of shift/logical for 200000000 operations.

Here's the code:

void Main()
{
    var barr = new BitArray(10);
    barr[4] = true;
    Console.WriteLine("Is it "+barr[4]);
    Console.WriteLine("Is it Not "+barr[5]);
}

public class BitArray{ 
    private readonly byte[] _buffer; 

    public bool this[long addr]{
      get{

         byte mask = (byte)(1 << (int)(addr & 7));  
         byte val = _buffer[(int)(addr >> 3)];
         bool bit = (val & mask) == mask;
         return bit;
      }
      set{
         byte mask = (byte) ((value ? 1:0) << (int)(addr & 7));
         int offs = (int)addr >> 3;
         _buffer[offs] = (byte)(_buffer[offs] | mask);
      }
    }

    public BitArray(long size){
       _buffer = new byte[size/8 + 1]; // define a byte buffer sized to hold 8 bools per byte. The spare +1 is to avoid dealing with rounding.
    } 
}

Collectives™ on Stack Overflow

Defining a bit[] array in C#

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related