# Union/find structure implemented by bitvectors

I'm having trouble understanding a concept in my book which is about finding a good structure to represent a union-find datastructure. Here we define a structure -referred to as collection- $V$ as such a datastructure:

A collection $V$ is a bitvector (bitvector is an array of $l = (n/b) + 1$ longs) where bit $i$ ($0 \le i \lt b$) of word $j$ ($0 \le j \lt l$) is 1 only if the element $j * b + 1$ is in the collection $V$.

($n$ is the amount of elements, $b$ is how many bits are represented in a long)

So i was thinking of figuring this out with an example, let's say we have collection $V$:

[ 1 | 3 | 6 | ... | l ]

And since:

1 = 001
3 = 011
6 = 110


Does that mean elements with the number (assuming we have given each element a number):

1 * 64 + 1 = 65
3 * 64 + 1 = 193
3 * 64 + 2 = 194
6 * 64 + 2 = 386
6 * 64 + 3 = 387

are in the collection $V$ ?

If this is completely wrong, could someone please give me a decent example of such a collection $V$, or point out where i'm wrong, or why my example can't be such a collection?

(also, i couldn't give this any sensible tag since i can't create tags yet)

The concept is simpler than you think.

Assuming 8 bit words and a bitvector of only one word length,

1 = 00000001
3 = 00000100
6 = 00100000


The collection is the union of the three individual elements, which is to say 00100101.

Also, wikipedia: http://en.wikipedia.org/wiki/Bit_array

• Damn, i was way off. As you said, it's really not that hard, thanks for the simple example, i get it now :) – Aerus Jan 15 '11 at 18:27