2
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Damn, i was way off. As you said, it's really not that hard, thanks for the simple example, i get it now :) $\endgroup$ – Aerus Jan 15 '11 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.