<p>The concept is simpler than you think.</p>

<p>Assuming 8 bit words and a bitvector of only one word length,</p>

<pre><code>1 = 00000001  
3 = 00000100  
6 = 00100000
</code></pre>

<p>The collection is the union of the three individual elements, which is to say <code>00100101</code>.</p>

<p>Also, wikipedia: <a href="http://en.wikipedia.org/wiki/Bit_array" rel="nofollow">http://en.wikipedia.org/wiki/Bit_array</a></p>

CC BY-SA 2.5
2011-01-15T18:27:41.937Z
Damn, i was *way* off. As you said, it's really not that hard, thanks for the simple example, i get it now :)
Aerus
CC BY-SA 2.5
2011-01-15T17:51:14.467Z
2011-01-15T17:51:14.467Z
sclv
<p>I'm having trouble understanding a concept in my book which is about finding a good structure to represent a <em>union-find</em> datastructure. Here we define a structure -referred to as collection- $V$ as such a datastructure:</p>

<p>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$.</p>

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

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

<p>[ 1 |  3  |  6  | ... | l  ]</p>

<p>And since:</p>

<pre><code>1 = 001  
3 = 011  
6 = 110
</code></pre>

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

<p>1 * 64 + 1 = 65<br>
3 * 64 + 1 = 193<br>
3 * 64 + 2 = 194<br>
6 * 64 + 2 = 386<br>
6 * 64 + 3 = 387  </p>

<p>are in the collection $V$ ?  </p>

<p>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?</p>

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

<ds.algorithms><ds.data-structures>
Union/find structure implemented by bitvectors
Aerus
# Union/find structure implemented by bitvectors

(Asked by: username_0 on 2011-01-15)

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)

**Tags:** ds.algorithms, ds.data-structures

---

## 1 answers

### Answer by username_1 on 2011-01-15. Score: 1 | Accepted answer

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

> **Comments:**
> **username_0**: Damn, i was *way* off. As you said, it's really not that hard, thanks for the simple example, i get it now :)  

---

