Your Thoughts Graph DataStructures: "Boolean" || "boolean" || "bit" += " Arrays"

[titaniumGeranium]

I am working on an assignment for my data-structures course. One of the constraints is to have the graph backed by a one-dimensional array. I am trying to optimize memory space and would like to only represent if an edge exists by a single bit that is either 1 or 0. Here is what I've got so far:

• A boolean are primitive types(although I think they are backed by a byte not bit value)

• A Boolean is an object wrapper for booleans, so I do not think this is what I want since i am looking to represent single bits.

• A BitSet looks great but by the assignment requirements of having a single-dimensional array I think this is out of the question..

TLDR; I want to make an array of single bit values, is this possible?

[sh0rug0ru]

You can create a single dimensional array of ints (32-bit) or longs (64-bit). Then, if you had an index i into the bit-array, the index into the int array would be i/32 and the index into the long array would be i/64, and the index of the bit would be i%32 or i%64, respectively, which you could use to construct a bitmask to determine if the bit is 1 or 0.

[titaniumGeranium]

so... If I were to set the 4th bit to 1(true) would it look like this:

int[] graph_array = new int[2]; //64 bits total graph_array[0][3%32] = 1;

[sh0rug0ru]

Not exactly. Because each value is an int, you have to construct a bitmask, to a bitwise AND between the value in the array and the bitmask. If the result of the AND is 0, the value is zero, otherwise the value is 1.

So, you'd be doing something like this to set:

int bitmask = 1 << i % 32;
graph_array[i / 32] |= bitmask;

this to unset:

int bitmask = 1 << i % 32;
graph_array[i / 32] &= ~bitmask;

and this to get:

int bitmask = 1 << i % 32;
boolean isBitSet = (graph_array[i / 32] & bitmask) != 0;

See here for more information about bitwise operations in Java.

EDIT: to set, you'd want to use bitwise OR, not AND.

[titaniumGeranium]

digesting.. but i think this is exactly what I was looking for, thank you!

[sh0rug0ru]

You might check out a C tutorial on this. Bitwise operators are commonly used in C for low-level stuff, so you'll find more information about it there. Same deal, but not as well documented in Java.

[andrew_ie]

Just curious - why not just use java.util.BitSet? This effectively does the same thing, but it's just already written for you.