Multidimensional Packed Bit Array

[Thomas Bruckner]

Hello,

I've looked online for an implementation of a multidimensional packed
bit array (like BitArray but with more than one dimension), and could
not find any, so I'm trying to create my own. However with limited
success sofar. I'm having troubles with calculating the required size of
the storage and also with the bit shifts... my brain is turning in
circles trying to figure this out ;-)

Anyone want to help with this?

Thomas Bruckner


using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
// new array 4 dimensions each with 2, 2, 4 and 4 elements
MultiBitArray mba = new MultiBitArray(new int[] { 2, 2, 4,
4 });

for (int i = 0; i <= 3; i++)
{
for (int j = 0; j <= 3; j++)
{
for (int k = 0; k < 15; k++)
{
for (int l = 0; l < 15; l++)
{
int[] coord = new int[] { i, j, k, l};

// make sure it is initially false

System.Diagnostics.Debug.Assert(mba.GetValue(coord) == false);

// set to true, and check
mba.SetValue(coord, true);

System.Diagnostics.Debug.Assert(mba.GetValue(coord) == true);

Console.WriteLine(
mba.GetLocation(coord).ToString());
}
}
}
}

Console.ReadKey();
}
}

public class MultiBitArray
{
/// <summary>
/// Number of dimensions.
/// </summary>
private int dimCount;

/// <summary>
/// bite size of each dimension (may be different)
/// </summary>
private int[] bitSize;

/// <summary>
/// storage for bits
/// </summary>
internal byte[] storage;

public MultiBitArray(int[] bitSize)
{
this.dimCount = bitSize.Length;
this.bitSize = bitSize;

AllocStorage();
}

/// <summary>
/// Allocates storage space for bits.
/// </summary>
private void AllocStorage()
{
long storageSize = 1;

for (int i = 0; i < this.dimCount; i++)
{
storageSize *= (this.bitSize * dimCount);
}

// i can't even figure out how to determine the
// amount of memory... so I set it very large for testing
//storageSize *= 4;

this.storage = new byte[storageSize];
}

/// <summary>
/// Gets the location of a bit according to dimension indexes
/// </summary>
internal int GetLocation(int[] coord)
{
int location = 0;
int bitcount = 0;

for (int i = 0; i < dimCount; i++)
{
location = (location << bitcount) | coord;
bitcount = this.bitSize;
}

return location;
}

/// <summary>
/// Read a bit.
/// </summary>
public bool GetValue(int[] coord)
{
int location = GetLocation(coord);
return (this.storage[location / 8] & (byte)(1 << (location
% 8))) != 0;
}

/// <summary>
/// Set a bit.
/// </summary>
public void SetValue(int[] coord, bool value)
{
int location = GetLocation(coord);
this.storage[location / 8] |= (byte)(1 << (location % 8));
}
}
}

 

[colin]

Ive not used it myself but I assume you would just have a BitArray
with enough bits in it to hold all the bits in the entire array.
the amount of memory is just all the dimensions multiplied together.

the offset and multiplier for each dimension is simply the total size of the
lower order dimension.

so for an array a[3,3,3]

would be 27 bits big, a[x,y,z] -> BitArrayStore[x*9+y*3+z]

Colin =^.^=

Hello,

I've looked online for an implementation of a multidimensional packed bit
array (like BitArray but with more than one dimension), and could not find
any, so I'm trying to create my own. However with limited success sofar.
I'm having troubles with calculating the required size of the storage and
also with the bit shifts... my brain is turning in circles trying to
figure this out ;-)

Anyone want to help with this?

Thomas Bruckner


using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
// new array 4 dimensions each with 2, 2, 4 and 4 elements
MultiBitArray mba = new MultiBitArray(new int[] { 2, 2, 4,
4 });

for (int i = 0; i <= 3; i++)
{
for (int j = 0; j <= 3; j++)
{
for (int k = 0; k < 15; k++)
{
for (int l = 0; l < 15; l++)
{
int[] coord = new int[] { i, j, k, l};

// make sure it is initially false

System.Diagnostics.Debug.Assert(mba.GetValue(coord) == false);

// set to true, and check
mba.SetValue(coord, true);

System.Diagnostics.Debug.Assert(mba.GetValue(coord) == true);

Console.WriteLine(
mba.GetLocation(coord).ToString());
}
}
}
}

Console.ReadKey();
}
}

public class MultiBitArray
{
/// <summary>
/// Number of dimensions.
/// </summary>
private int dimCount;

/// <summary>
/// bite size of each dimension (may be different)
/// </summary>
private int[] bitSize;

/// <summary>
/// storage for bits
/// </summary>
internal byte[] storage;

public MultiBitArray(int[] bitSize)
{
this.dimCount = bitSize.Length;
this.bitSize = bitSize;

AllocStorage();
}

/// <summary>
/// Allocates storage space for bits.
/// </summary>
private void AllocStorage()
{
long storageSize = 1;

for (int i = 0; i < this.dimCount; i++)
{
storageSize *= (this.bitSize * dimCount);
}

// i can't even figure out how to determine the
// amount of memory... so I set it very large for testing
//storageSize *= 4;

this.storage = new byte[storageSize];
}

/// <summary>
/// Gets the location of a bit according to dimension indexes
/// </summary>
internal int GetLocation(int[] coord)
{
int location = 0;
int bitcount = 0;

for (int i = 0; i < dimCount; i++)
{
location = (location << bitcount) | coord;
bitcount = this.bitSize;
}

return location;
}

/// <summary>
/// Read a bit.
/// </summary>
public bool GetValue(int[] coord)
{
int location = GetLocation(coord);
return (this.storage[location / 8] & (byte)(1 << (location %
8))) != 0;
}

/// <summary>
/// Set a bit.
/// </summary>
public void SetValue(int[] coord, bool value)
{
int location = GetLocation(coord);
this.storage[location / 8] |= (byte)(1 << (location % 8));
}
}
}

 

[Arne Vajhøj]

I've looked online for an implementation of a multidimensional packed
bit array (like BitArray but with more than one dimension), and could
not find any, so I'm trying to create my own.

What feature do you need that an array of BitArray does not provide ?

Arne

 

[christery]

the offset and multiplier for each dimension is simply the total size of the

lower order dimension.

so for an array a[3,3,3]

would be 27 bits big, a[x,y,z] -> BitArrayStore[x*9+y*3+z]

Colin =^.^=

just dont get it, should be 3*3*3=27,

x*9+y*3+z is what? new mathematics? what is x,y,z? 3*9+3*3+3 != 27

just dont get it *as always*

But u are probably correct...

//CY

 

[Bill Butler]

the offset and multiplier for each dimension is simply the total size
of the
lower order dimension.

so for an array a[3,3,3]

would be 27 bits big, a[x,y,z] -> BitArrayStore[x*9+y*3+z]

Colin =^.^=

just dont get it, should be 3*3*3=27,

x*9+y*3+z is what? new mathematics? what is x,y,z? 3*9+3*3+3 != 27

just dont get it *as always*

But u are probably correct...

He is flattening the 3 dimensional array into a single dimension.
a row has 3 elements {0,1,2}
a plane has 9 elements {0,1,2} X {0,1,2}
the cube has 27 elements {0,1,2} X {0,1,2}X {0,1,2}

so to get the position you have to know:
Which plane? {plane has 9 elements}
Which row within the plane? {row has 3 elements}
Which item within the row?

thus
x*9+y*3+z

x*9 is the plane
y*3 is the row within the plane
z is item within the row

Hope this clears it up some
Bill

 

[christery]

the offset and multiplier for each dimension is simply the total size
of the
lower order dimension.
so for an array a[3,3,3]
would be 27 bits big, a[x,y,z] -> BitArrayStore[x*9+y*3+z]
Colin =^.^=

just dont get it, should be 3*3*3=27,

x*9+y*3+z is what? new mathematics? what is x,y,z? 3*9+3*3+3 != 27

just dont get it *as always*

But u are probably correct...

He is flattening the 3 dimensional array into a single dimension.
a row has 3 elements {0,1,2}
a plane has 9 elements {0,1,2} X {0,1,2}
the cube has 27 elements {0,1,2} X {0,1,2}X {0,1,2}

so to get the position you have to know:
   Which plane?  {plane has 9 elements}
   Which row within the plane?  {row has 3 elements}
   Which item within the row?

thus
x*9+y*3+z

x*9 is the plane
y*3 is the row within the plane
z is  item within the row

Hope this clears it up some
    Bill- Dölj citerad text -

- Visa citerad text -

I'm having troubles with calculating the required size of

the storage


he wanted to know the size, so if I use [2,2]=4bits, [3,3,3]=27bits
[3,3,4]=36 bits then

thus

[2,2] 2*3+2 = 8
[3,3,3] 3*9+3*2+3=36
[3,3,4] 3*9+3*2+4=37

is mathemagical to me..

but as Arne said, why not use an array of...

//CY who stole chr$(12)

 

[Bill Butler]

he wanted to know the size, so if I use [2,2]=4bits, [3,3,3]=27bits
[3,3,4]=36 bits then

Correct, that is how you determine the storage in bits (as Colin said)

thus

[2,2] 2*3+2 = 8
[3,3,3] 3*9+3*2+3=36
[3,3,4] 3*9+3*2+4=37

is mathemagical to me..

That is because x*9+y*3+z is the way to calculate the index into the
storage.

If you have [3,3,3] => size 27
this means that
x={0,1,2}
y={0,1,2}
z={0,1,2}

if you plug each possible combination of x,y,z into the equation you
will get an index that varies from 0 thru 26 (one less than the size of
the storage)
[2,2] 1*2 + 1 = 3 = 4-1
[3,3,3] 2*9+2*3+2 = 26 = 27-1
[3,3,4] 2*12+2*4+3=35 = 36 - 1

or more generally

[a,b,c] ==> b*c*x + c*y + z

and plugging in the max values we get
b*c*(a-1) + c*(b-1) + (c-1) =
b*c*a - b*c + b*c - c + c - 1 = a*b*c - 1

Hopefully I cleared things up a bit (probably just muddied them worse)

Bill

 

[colin]

ok lets put it another way with leters instead of numbers wich might be
clearer...

for an array with dimensions of

a=new MyBitType[n3,n2,n1];

....contains n1*n2*n3 elements

so if you want to map a 3 dim array into a single dim array

MyBitType[] b=new MyBitType[n3*n2*n1];

a[x,y,z]
....becomes
b[x*n2*n1+y*n1+z]

although I warn you ive not finished my first cup of coffee of the morning
yet so
cant garantee its corect.

.... i find the hardest things to explain are the things that seem so obvious
to me.

ofc this is assuming the MyBitType takes care of the actual 1 dimensional
bitfield itself
wich is fairly easy but can be explained if needed.

Colin =^.^=

the offset and multiplier for each dimension is simply the total size of
the
lower order dimension.

so for an array a[3,3,3]

would be 27 bits big, a[x,y,z] -> BitArrayStore[x*9+y*3+z]

Colin =^.^=

just dont get it, should be 3*3*3=27,

x*9+y*3+z is what? new mathematics? what is x,y,z? 3*9+3*3+3 != 27

just dont get it *as always*

But u are probably correct...

//CY

 

[christery]

But u are probably correct...

- Visa citerad text -

So I was trying for the size, and you for the position of the bit in
the array...
think Arne has the right solution an array of arrays...

Think I can follow (draw) your thoughts on 2,2 and 3,3,3 but lost at
(drawing) 4,4,4

No, dont answer that,,, just silly talk

//CY